# 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

### View Answer

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

### View Answer

3. What is the worst case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

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; }

### View Answer

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

### View Answer

6. What is the average case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

10. What is the best case complexity of selection sort?

a) O(nlogn)

b) O(logn)

c) O(n)

d) O(n^{2})

### View Answer

^{2}). (n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n

^{2})/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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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); }

### View Answer

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

### View Answer

11. What are the advantages of sparse matrices over normal matrices?

a) Size

b) Speed

c) Easily compressible

d) All of the mentioned

### View Answer

## 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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

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[1].

d) S[0].

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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].

### View Answer

## 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

### View Answer

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

### View Answer

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; } }

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

9. Which of the following data structures can be used for parentheses matching?

a) n-ary tree

b) queue

c) priority queue

d) stack

### View Answer

10. Minimum number of queues to implement stack is,

a) 3

b) 4

c) 1

d) 2

### View Answer

## Set 5

1. Process of inserting an element in stack is called ____________

a) Create

b) Push

c) Evaluation

d) Pop

### View Answer

2. Process of removing an element from stack is called __________

a) Create

b) Push

c) Evaluation

d) Pod

### View Answer

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

### View Answer

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

### View Answer

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.

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

10. Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation.

The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?

a) 1

b) 2

c) 3

d) 4