Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# Multiple choice question for engineering

## Set 1

1. What is an in-place sorting algorithm?
a) It needs O(1) or O(logn) memory to create auxiliary locations
b) The input is already sorted and in-place
c) It requires additional storage
d) None of the mentioned

Answer: a [Reason:] Auxiliary memory is required for storing the data temporarily.

2. In the following scenarios, when will you use selection sort?
a) The input is already sorted
b) A large file has to be sorted
c) Large values need to be sorted with small keys
d) Small values need to be sorted with large keys

Answer: c [Reason:] Selection is based on keys, hence a file with large values and small keys can be efficiently sorted with selection sort.

3. What is the worst case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: d [Reason:] Selection sort creates a sub-list, LHS of the ‘min’ element is already sorted and RHS is yet to be sorted. Starting with the first element the ‘min’ element moves towards the final element.

4. Select the appropriate code that performs selection sort.
a)

```        int min;
for(int j=0; j<arr.length-1; j++)
{
min = j;
for(int k=j+1; k<=arr.length-1; k++)
{
if(arr[k] < arr[min])
min = k;
}
int temp = arr[min];
arr[min] = arr[j];
arr[j] = temp;
}```

b)

```        int min;
for(int j=0; j<arr.length-1; j++)
{
min = j;
for(int k=j+1; k<=arr.length; k++)
{
if(arr[k] < arr[min])
min = k;
}
int temp = arr[min];
arr[min] = arr[j];
arr[j] = temp;
}```

c)

```        int min;
for(int j=0; j<arr.length-1; j++)
{
min = j;
for(int k=j+1; k<=arr.length-1; k++)
{
if(arr[k] > arr[min])
min = k;
}
int temp = arr[min];
arr[min] = arr[j];
arr[j] = temp;
}```

d)

```        int min;
for(int j=0; j<arr.length-1; j++)
{
min = j;
for(int k=j+1; k<=arr.length; k++)
{
if(arr[k] > arr[min])
min = k;
}
int temp = arr[min];
arr[min] = arr[j];
arr[j] = temp;
}```

Answer: a [Reason:] Starting with the first element as ‘min’ element, selection sort loops through the list to select the least element which is then swapped with the ‘min’ element.

5. What is the advantage of selection sort over other sorting techniques?
a) It requires no additional storage space
b) It is scalable
c) It works best for inputs which are already sorted
d) It is faster than any other sorting technique

Answer: a [Reason:] Since selection sort is an in-place sorting algorithm, it does not require additional storage.

6. What is the average case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: d [Reason:] In the average case, even if the input is partially sorted, selection sort behaves as if the entire array is not sorted. Selection sort is insensitive to input.

7. What is the disadvantage of selection sort?
a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) None of the mentioned

Answer: b [Reason:] As the input size increases, the performance of selection sort decreases.

8. The given array is arr = {3,4,5,2,1}. The number of iterations in bubble sort and selection sort respectively are,
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5

Answer: a [Reason:] Since the input array is not sorted, bubble sort takes 5 iterations and selection sort takes 4(n-1) iterations.

9. The given array is arr = {1,2,3,4,5}. (bubble sort is implemented with a flag variable)The number of iterations in selection sort and bubble sort respectively are,
a) 5 and 4
b) 1 and 4
c) 0 and 4
d) 4 and 1

Answer: b [Reason:] Selection sort is insensitive to input, hence 4(n-1) iterations. Whereas bubble sort iterates only once to set the flag to 0 as the input is already sorted.

10. What is the best case complexity of selection sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: d [Reason:] The best, average and worst case complexities of selection sort is O(n2). (n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2

## Set 2

1. What is a sparse array?
a) Data structure for representing arrays of records
b) Data structure that compactly stores bits
c) An array in which most of the elements have the same value
d) None of the mentioned

Answer: c [Reason:] They are set to a default value, usually 0 or null.

2. When do you use a sparse array?
a) When there are unique elements in the array
b) When the array has more occurrence of zero elements
c) When the data type of elements differ
d) In all of the mentioned cases

Answer: b [Reason:] It need not necessarily be zero, it could be any default value, usually zero or null.

3. What is the difference between a normal(naive) array and a sparse array?
a) Sparse array can hold more elements than a normal array
b) Sparse array is memory efficient
c) Sparse array is dynamic
d) A naive array is more efficient

Answer: b [Reason:] A naive implementation allocates space for the entire size of the array, whereas a sparse array(linked list implementation) allocates space only for the non-default values.

4. Choose the code which performs the store operation in a sparse array.(Linked list implementation)
a)

```public void store(int index, Object val)
{
List cur = this;
List prev = null;

List node = new List(index);
node.val = val;

while (cur != null && cur.index < index)
{
prev = cur;
cur = cur.next;
}

if (cur == null)
{
prev.next = node;
} else
{
if (cur.index == index)
{
System.out.println("DUPLICATE");
return;
}
prev.next = node;
node.next = cur;
}
return;
}```

b)

```public void store(int index, Object val)
{
List cur = this;
List prev = null;

List node = new List(index);
node.val = val;

while (prev != null && prev.index < index)
{
prev = cur;
cur = cur.next;
}

if (cur == null)
{
prev.next = node;
} else
{
if (cur.index == index)
{
System.out.println("DUPLICATE");
return;
}
prev.next = node;
node.next = cur;
}
return;
}```

c)

```public void store(int index, Object val)
{
List cur = this;
List prev = null;

List node = new List(index);
node.val = val;

while (cur != null && cur.index < index)
{
cur = cur.next;
prev = cur;
}

if (cur == null)
{
prev.next = node;
} else
{
if (cur.index == index)
{
System.out.println("DUPLICATE");
return;
}
prev.next = node;
node.next = cur;
}
return;
}```

d) None of the mentioned

Answer: a [Reason:] Create a new node and traverse through the list until you reach the correct position, check for duplicate and nullity of the list and then insert the node.

5. Which of the following performs the fetch operation?
a)

```public Object fetch(int index)
{
List cur = this.next;
Object val = null;
while (cur != null && cur.index != index)
{
cur = cur.next;
}
if (cur != null)
{
val = cur.val;
} else
{
val = null;
}
return val;
}```

b)

```public Object fetch(int index)
{
List cur = this;
Object val = null;
while (cur != null && cur.index != index)
{
cur = cur.next;
}
if (cur != null)
{
val = cur.val;
} else
{
val = null;
}
return val;
}```

c)

```public Object fetch(int index)
{
List cur = this;
Object val = null;
while (cur != null && cur.index != index)
{
cur = cur.index;
}
if (cur != null)
{
val = cur.val;
} else
{
val = null;
}
return val;
}```

d) None of the mentioned

Answer: b [Reason:] You travers through the array until the end is reached or the index is found and return the element at that index, null otherwise.

6. Choose the appropriate code that counts the number of non-zero(non-null) elements in the sparse array.
a)

```public int count()
{
int count = 0;
for (List cur = this.next; (cur != null); cur = cur.next)
{
count++;
}
return count;
}```

b)

```public int count()
{
int count = 0;
for (List cur = this; (cur != null); cur = cur.next)
{
count++;
}
return count;
}```

c)

```public int count()
{
int count = 1;
for (List cur = this.next; (cur != null); cur = cur.next)
{
count++;
}
return count;
}```

d) None of the mentioned

Answer: a [Reason:] A simple ‘for loop’ to count the non-null elements.

7. Suppose the contents of an array A are, A = {1, null, null, null, null, 10};
What would be the size of the array considering it as a normal array and a sparse array?
a) 6 and 6
b) 6 and 2
c) 2 and 6
d) 2 and 2

Answer: b [Reason:] A normal array considers null also as an element, but in the sparse array only a non-zero or a non-null element is considered.

8. What is sparsity of a matrix?
a) The fraction of zero elements over the total number of elements
b) The fraction of non-zero elements over the total number of elements
c) The fraction of total number of elements over the zero elements
d) The fraction of total number of elements over the non-zero elements

Answer: a [Reason:] This is the definition of sparsity(density) of a matrix.

9. How would you store an element in a sparse matrix?
a)

```public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 || row_index > N)
{
System.out.println("row index out of bounds");
return;
}
if (col_index < 0 || col+index > N)
{
System.out.println("column index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}```

b)

```public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 || row_index > N)
{
System.out.println("column index out of bounds");
return;
}
if (col_index < 0 || col+index > N)
{
System.out.println("row index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}```

c)

```public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 && row_index > N)
{
System.out.println("row index out of bounds");
return;
}
if (col_index < 0 && col+index > N)
{
System.out.println("column index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}```

d)

```public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 && row_index > N)
{
System.out.println("column index out of bounds");
return;
}
if (col_index < 0 && col+index > N)
{
System.out.println("row index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}```

Answer: a [Reason:] Each row in a sparse matrix acts as a sparse array, hence this row with the specified col_index is the array and the specified position where the element is stored.

10. What is the functionality of the following piece of code?

```public Object function(int row_index, int col_index)
{
if (row_index < 0 || col_index > N)
{
System.out.println("column index out of bounds");
return;
}
return (sparse_array[row_index].fetch(col_index));
}```

a) Store the element in the specified position
b) Get the element from the specified position
c) Alter the element in the specified position
d) None of the mentioned

Answer: b [Reason:] The fetch method of SparseArray class is called , the row specified by row_index makes it an array and the col_index denotes the specified position.

11. What are the advantages of sparse matrices over normal matrices?
a) Size
b) Speed
c) Easily compressible
d) All of the mentioned

Answer: d [Reason:] As the the matrix is easily compressible by not storing the zero/null elements, they require less memory space, also only the non zero elements have to be computed, hence computational speed increases.

## Set 3

1. Which of the following real world scenarios would you associate with a stack data structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) all of the mentioned

Answer: a [Reason:] Stack follows Last In First Out(LIFO) policy. Piling up of chairs one above the other is based on LIFO, people standing in a line is a queue and if the service is based on priority, then it can be associated with a priority queue.

2. What does the following function check for? (all necessary headers to be included and function is called from main)

```   #define MAX 10

typedef struct stack
{
int top;
int item[MAX];
}stack;

int function(stack *s)
{
if(s->top == -1)
return 1;
else return 0;
}```

a) full stack
b) invalid index
c) empty stack
d) infinite stack

Answer: c [Reason:] An empty stack is represented with the top-of-the-stack(‘top’ in this case) to be equal to -1.

3. What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception

Answer: c [Reason:] Removing items from an empty stack is termed as stack underflow.

4. What is the output of the following program?

```public class Stack
{
protected static final int CAPACITY = 100;
protected int size,top = -1;
protected Object stk[];

public Stack()
{
stk = new Object[CAPACITY];
}

public void push(Object item)
{
if(size_of_stack==size)
{
System.out.println("Stack overflow");
return;
}
else
{
top++;
stk[top]=item;
}
}
public Object pop()
{
if(top<0)
{
return -999;
}
else
{
Object ele=stk[top];
top--;
size_of_stack--;
return ele;
}
}
}

public class StackDemo
{
public static void main(String args[])
{
Stack myStack = new Stack();
myStack.push(10);
Object element1 = myStack.pop();
Object element2 = myStack.pop();
System.out.println(element2);
}
}```

a) stack is full
b) 20
c) 0
d) none of the mentioned

Answer: d [Reason:] The first call to pop() returns 10, whereas the second call to pop() would result in stack underflow and the program returns -999.

5. What is the time complexity of pop() operation when the stack is implemented using an array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)

Answer: a [Reason:] pop() accesses only one end of the structure, and hence constant time.

6. Which of the following array position will be occupied by a new element being pushed for a stack of size N elements(capacity of stack > N).
a) S[N-1].
b) S[N].
c) S.
d) S.

Answer: b [Reason:] Elements are pushed at the end, hence N.

7. What happens when you pop from an empty stack while implementing using the Stack ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown

Answer: c [Reason:] The Stack ADT throws an EmptyStackException if the stack is empty and a pop() operation is tried on it.

8. What is the functionality of the following piece of Java code?
Assume: ‘a’ is a non empty array of integers, the Stack class creates an array of specified size and provides a top pointer indicating TOS(top of stack), push and pop have normal meaning.

```public void some_function(int[] a)
{
Stack S=new Stack(a.length);
int[] b=new int[a.length];
for(int i=0;i<a.length;i++)
{
S.push(a[i]);
}
for(int i=0;i<a.length;i++)
{
b[i]=(int)(S.pop());
}
System.out.println("output :");
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}```

a) print alternate elements of array
b) duplicate the given array
c) parentheses matching
d) reverse the array

Answer: d [Reason:] Every element from the given array ‘a’ is pushed into the stack, and then the elements are popped out into the array ‘b’. Stack is a LIFO structure, this results in reversing the given array.

9. ‘Array implementation of Stack is not dynamic’, which of the following statements supports this argument?
a) space allocation for array is fixed and cannot be changed during run-time
b) user unable to give the input for stack operations
c) a runtime exception halts execution
d) all of the mentioned

Answer: a [Reason:] You cannot modify the size of an array once the memory has been allocated, adding fewer elements than the array size would cause wastage of space, and adding more elements than the array size at run time would cause Stack Overflow.

10. Which of the following array element will return the top-of-the-stack-element for a stack of size N elements(capacity of stack > N).
a) S[N-1].
b) S[N].
c) S[N-2].
d) S[N+1].

Answer: a [Reason:] Array indexing start from 0, hence N-1 is the last index.

## Set 4

1. What is the complexity of searching for a particular element in a Singly Linked List?
a) O(n)
b) O(1)
c) logn
d) nlogn

Answer: a [Reason:] Singly Linked List allows you to traverse in one direction only, hence if the element to be found is at the tail of the list, the complexity of searching is O(n) to traverse the entire list.

2. Which of the following statements are correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)?
a) Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL
b) SLL uses lesser memory per node than DLL
c) DLL has more searching power than SLL
d) All of the mentioned

Answer: d [Reason:] To insert and delete at known positions requires complete traversal of the list in worst case in SLL, SLL consists of an item and a node field, while DLL has an item and two node fields, hence SLL occupies lesser memory, DLL can be traversed both ways(left and right), while SLL can traverse in only one direction, hence more searching power of DLL.

3. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor.
Select from the options the appropriate pop() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.

```class Node
{
protected Node next;
protected Object ele;
Node()
{
this(null,null);
}
Node(Object e,Node n)
{
ele=e;
next=n;
}
public void setNext(Node n)
{
next=n;
}
public void setEle(Object e)
{
ele=e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}

class Stack
{
Node first;
int size=0;
Stack()
{
first=null;
}
}```

a)

```public Object pop()
{
if(size == 0)
System.out.println("underflow");
else
{
Object o = first.getEle();
first = first.getNext();
size--;
return o;
}
}```

b)

```public Object pop()
{
if(size == 0)
System.out.println("underflow");
else
{
Object o = first.getEle();
first = first.getNext().getNext();
size--;
return o;
}
}```

c)

```public Object pop()
{
if(size == 0)
System.out.println("underflow");
else
{
first = first.getNext();
Object o = first.getEle();
size--;
return o;
}
}```

d)

```public Object pop()
{
if(size == 0)
System.out.println("underflow");
else
{
first = first.getNext().getNext();
Object o = first.getEle();
size--;
return o;
}
}```

Answer: a [Reason:] pop() should return the Object pointed to by the node ‘first’. The sequence of operations is, first, get the element stored at node ‘first’ using getEle(), and second, make the node point to the next node using getNext().

4. What does the following function do?

```public Object some_func()throws emptyStackException
{
if(isEmpty())
throw new emptyStackException("underflow");
return first.getEle();
}```

a) pop
b) delete the top-of-the-stack element
c) retrieve the top-of-the-stack element
d) none of the mentioned

Answer: c [Reason:] This code is only retrieving the top element, note that it is not equivalent to pop operation as you are not setting the ‘next’ pointer point to the next node in sequence.

5. What is the functionality of the following piece of code?

```public void display()
{
if(size == 0)
System.out.println("underflow");
else
{
Node current = first;
while(current != null)
{
System.out.println(current.getEle());
current = current.getNext();
}
}
}```

a) reverse the list
b) display the list
c) display the list excluding top-of-the-stack-element
d) reverse the list excluding top-of-the-stack-element

Answer: b [Reason:] An alias of the node ‘first’ is created which traverses through the list and displays the elements.

6. What does ‘stack overflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception

Answer: b [Reason:] Adding items to a full stack is termed as stack underflow.

7. Given below is the Node class to perform basic list operations and a Stack class with a no arg constructor. Select from the options the appropriate push() operation that can be included in the Stack class. Also ‘first’ is the top-of-the-stack.

```class Node
{
protected Node next;
protected Object ele;
Node()
{
this(null,null);
}
Node(Object e,Node n)
{
ele=e;
next=n;
}
public void setNext(Node n)
{
next=n;
}
public void setEle(Object e)
{
ele=e;
}
public Node getNext()
{
return next;
}
public Object getEle()
{
return ele;
}
}

class Stack
{
Node first;
int size=0;
Stack()
{
first=null;
}
}```

a)

```public void push(Object item)
{
Node temp = new Node(item,first);
first = temp;
size++;
}```

b)

```public void push(Object item)
{
Node temp = new Node(item,first);
first = temp.getNext();
size++;
}```

c)

```public void push(Object item)
{
Node temp = new Node();
first = temp.getNext();
first.setItem(item);
size++;
}```

d) none of the mentioned

Answer: a [Reason:] To push an element into the stack, first create a new node with the next pointer point to the current top-of-the-stack node, then make this node as top-of-the-stack by assigning it to ‘first’.

8. Consider these functions:
push() : push an element into the stack
pop() : pop the top-of-the-stack element
top() : returns the item stored in top-of-the-stack-node
What will be the output after performing these sequence of operations

```push(20);
push(4);
top();
pop();
pop();
pop();
push(5);
top();```

a) 20
b) 4
c) stack underflow
d) 5

Answer: d [Reason:] 20 and 4 which were pushed are popped by the two pop() statements, the recent push() is 5, hence top() returns 5.

9. Which of the following data structures can be used for parentheses matching?
a) n-ary tree
b) queue
c) priority queue
d) stack

Answer: d [Reason:] For every opening brace, push it into the stack, and for every closing brace, pop it off the stack. Do not take action for any other character. In the end, if the stack is empty, then the input has balanced parentheses.

10. Minimum number of queues to implement stack is,
a) 3
b) 4
c) 1
d) 2

Answer: c [Reason:] Use one queue and one counter to count the number of elements in the queue.

## Set 5

1. Process of inserting an element in stack is called ____________
a) Create
b) Push
c) Evaluation
d) Pop

Answer: b [Reason:] Self Explanatory.

2. Process of removing an element from stack is called __________
a) Create
b) Push
c) Evaluation
d) Pod

Answer: d [Reason:] Self Explanatory.

3. In a stack, if a user tries to remove an element from empty stack it is called _________
a) Underflow
b) Empty collection
c) Overflow
d) Garbage Collection

Answer: a [Reason:] Self Explanatory.

4. Pushing an element into stack already having five elements and stack size of 5 , then stack becomes
a) Overflow
b) Crash
c) Underflow
d) User flow

Answer: a [Reason:] Self Explanatory.

5. Entries in a stack are “ordered”. What is the meaning of this statement?
a) A collection of stacks is sortable.
b) Stack entries may be compared with the ‘<‘ operation.
c) The entries are stored in a linked list.
d) There is a Sequential entry that is one by one.

Answer : d [Reason:] Self Explanatory.

6. Which of the following applications may use a stack?
a) A parentheses balancing program.
b) Tracking of local variables at run time.
c) Compiler Syntax Analyzer.
d) All of the mentioned

Answer: d [Reason:] All are applications of stack.

7. Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(())) are:
a) 1
b) 2
c) 3
d) 4 or more

Answer: c [Reason:] Applying the postfix expression evaluation.

8. Consider the usual algorithm for determining whether a sequence of parentheses is balanced.
Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order).
The maximum number of parentheses that appear on the stack AT ANY ONE TIME during the computation?
a) 1
b) 2
c) 3
d) 4 or more

Answer: b [Reason:] Applying the postfix expression evaluation.

9. What is the value of the postfix expression 6 3 2 4 + – *:
a) Something between -5 and -15
b) Something between 5 and -5
c) Something between 5 and 15
d) Something between 15 and 100