# Multiple choice question for engineering

## Set 1

1. Which of the following techniques can be used to search an element in an unsorted array?

a) Iterative linear search

b) Recursive binary search

c) Iterative binary search

d) All of the mentioned

### View Answer

2. Consider the array {1,1,1,1,1}:

Which of the following techniques can be used to search an element in the above array?

a) Iterative linear search

b) Recursive linear search

c) Recursive binary search

d) All of the mentioned

### View Answer

3. What does the following code do?

#include<stdio.h> int search_num(int *arr, int num, int len) { int i; for(i = 0; i < len; i++) if(arr[i] == num) return i; return -1; } int main() { int arr[5] ={1,2,3,4,5},num=3,len = 5; int indx = search_num(arr,num,len); printf("Index of %d is %d",num,indx); return 0; }

a) Finds the index of all the occurrences of the number that is searched

b) Finds the index of the first occurrence of the number that is searched

c) Finds the index of the last occurrence of the number that is searched

d) None of the mentioned

### View Answer

4. What is the output of the following code?

#include<stdio.h> int search_num(int *arr, int num, int len) { int i; for(i = 0; i < len; i++) if(arr[i] == num) return i; return -1; } int main() { int arr[5] ={1,3,3,3,5},num=3,len = 5; int indx = search_num(arr,num,len); printf("Index of %d is %d",num,indx); return 0; }

a) Index of 3 is 0

b) Index of 3 is 1

c) Index of 3 is 2

d) Index of 3 is 3

### View Answer

5. What is the time complexity of the above code used to search an element in an array?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

6. Consider the following recursive implementation of linear search:

#include<stdio.h> int recursive_search_num(int *arr, int num, int idx, int len) { if(idx == len) return -1; if(arr[idx] == num) return idx; return __________; } int main() { int arr[5] ={1,3,3,3,5},num=2,len = 5; int indx = recursive_search_num(arr,num,0,len); printf("Index of %d is %d",num,indx); return 0; }

Which of the following recursive calls should be added to complete the above code?

a) recursive_search_num(arr, num+1, idx, len);

b) recursive_search_num(arr, num, idx, len);

c) recursive_search_num(arr, num, idx+1, len);

d) recursive_search_num(arr, num+1, idx+1, len);

### View Answer

7. What is the output of the following code?

#include<stdio.h> int recursive_search_num(int *arr, int num, int idx, int len) { if(idx == len) return -1; if(arr[idx] == num) return idx; return recursive_search_num(arr, num, idx+1, len); } int main() { int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8; int indx = recursive_search_num(arr,num,0,len); printf("Index of %d is %d",num,indx); return 0; }

a) Index of 5 is 5

b) Index of 5 is 6

c) Index of 5 is 7

d) Index of 5 is 8

### View Answer

8. How many times is the function recursive_search_num() called when the following code is executed?

#include<stdio.h> int recursive_search_num(int *arr, int num, int idx, int len) { if(idx == len) return -1; if(arr[idx] == num) return idx; return recursive_search_num(arr, num, idx+1, len); } int main() { int arr[8] ={1,2,3,3,3,5,6,7},num=5,len = 8; int indx = recursive_search_num(arr,num,0,len); printf("Index of %d is %d",num,indx); return 0; }

a) 5

b) 6

c) 7

d) 8

### View Answer

9. What is the time complexity of the above recursive implementation of linear search?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

## Set 2

1. What is a skip list?

a) a linkedlist with size value in nodes

b) a linkedlist that allows faster search within an ordered sequence

c) a linkedlist that allows slower search within an ordered sequence

d) a tree which is in the form of linked list

### View Answer

2. Consider the 2-level skip list

How to access 38?

a) travel 20-30-35-38

b) travel 20-30-40-38

c) travel 20-38

d) travel 20-40-38

### View Answer

3. Skip lists are similar to which of the following datastructure?

a) stack

b) heap

c) binary search tree

d) balanced binary search tree

### View Answer

4. What is the time complexity improvement of skip lists from linked lists in insertion and deletion?

a) O(n) to O(logn) where n is number of elements

b) O(n) to O(1) where n is number of elements

c) no change

d) O(n) to O(n^{2}) where n is number of elements

### View Answer

5. To which datastructure are skip lists similar to in terms of time complexities in worst and best cases?

a) balanced binary search trees

b) binary search trees

c) binary trees

d) linked lists

### View Answer

6. The nodes in a skip list may have many forward references. their number is determined

a) probabilistically

b) randomly

c) sequentially

d) orthogonally

### View Answer

7. Are the below statements true about skiplists?

In a sorted set of elements skip lists can implement the below operations

i.given a element find closest element to the given value in the sorted set in O(logn)

ii.find the number of elements in the set whose values fall a given range in O(logn)

a) true

b) false

### View Answer

8. How to maintain multi-level skip list properties when insertions and deletions are done?

a) design each level of a multi-level skip list with varied probabilities

b) that cannot be maintained

c) rebalancing of lists

d) reconstruction

### View Answer

9. Is a skip list like balanced tree?

a) true, atleast like a balanced tree with good probabilities

b) false

### View Answer

10. What is indexed skip list?

a) it stores width of link in place of element

b) it stores index values

c) array based linked list

d) indexed tree

### View Answer

## Set 3

1. What are splay trees ?

a) self adjusting binary search trees

b) self adjusting binary trees

c) a tree with strings

d) a tree with probability distributions

### View Answer

2. Which of the following property of splay tree is correct ?

a) it holds probability usage of the respective sub trees

b) any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity

c) sequence of operations with h nodes can take O(logh) time complexity

d) splay trees are unstable trees

### View Answer

3. Why to prefer splay trees ?

a) easier to program

b) space efficiency

c) easier to program and faster access to recently accessed items

d) quick searching

### View Answer

4. Is it true that splay trees have O(logn) amortized complexity ?

a) true

b) false

### View Answer

5. What is a splay operation?

a) moving parent node to down of child

b) moving a node to root

c) moving root to leaf

d) removing leaf node

### View Answer

6. Which of the following options is an application of splay trees ?

a) cache Implementation

b) networks

c) send values

d) receive values

### View Answer

7. When we have red-black trees and AVL trees that can perform most of operations in logarithmic times, then what is the need for splay trees?

a) no there is no special usage

b) In real time it is estimated that 80% access is only to 20% data, hence most used ones must be easily available

c) redblack and avl are not upto mark

d) they are just another type of self balancing binary search trees

### View Answer

8. After the insertion operation, is the resultant tree a splay tee?

a) true

b) false

### View Answer

9. What output does the below pseudo code produces?

Tree_node function(Tree_node x) { Tree_node y = x.left; x.left = y.right; y.right = x; return y; }

a) right rotation of subtree

b) left rotation of subtree

c) zig-zag operation

d) zig-zig operation

### View Answer

10. What is the disadvantage of using splay trees?

a) height of a splay tree can be linear when accessing elements in non decreasing order.

b) splay operations are difficult

c) no significant disadvantage

d) splay tree performs unnecessary splay when a node is only being read

### View Answer

## Set 4

1. To implement a stack using queue(with only enqueue and dequeue operations), how many queues will you need?

a) 1

b) 2

c) 3

d) 4

### View Answer

2. Making the push operation costly, select the code snippet which implements the same.(let q1 and q2 be two queues)

a)

public void push(int x) { if(empty()) { q1.offer(x); } else{ if(q1.size()>0) { q2.offer(x); int size = q1.size(); while(size>0) { q2.offer(q1.poll()); size--; } } else if(q2.size()>0) { q1.offer(x); int size = q2.size(); while(size>0) { q1.offer(q2.poll()); size--; } } } }

b)

public void push(int x) { if(empty()) { q1.offer(x); } else { if(q1.size()>0) { q1.offer(x); int size = q1.size(); while(size>0) { q2.offer(q1.poll()); size--; } } else if(q2.size()>0) { q2.offer(x); int size = q2.size(); while(size>0) { q1.offer(q2.poll()); size--; } } } }

c)

public void push(int x) { if(empty()) { q1.offer(x); } else { if(q1.size()>0) { q2.offer(x); int size = q1.size(); while(size>0) { q1.offer(q2.poll()); size--; } } else if(q2.size()>0) { q1.offer(x); int size = q2.size(); while(size>0) { q2.offer(q1.poll()); size--; } } } }

d) None of the mentioned

### View Answer

3. Making the push operation costly, select the code snippet which implements the pop operation.

a)

public void pop() { if(q1.size()>0) { q2.poll(); } else if(q2.size()>0) { q1.poll(); } }

b)

public void pop() { if(q1.size()>0) { q1.poll(); } else if(q2.size()>0) { q2.poll(); } }

c)

public void pop() { q1.poll(); q2.poll(); }

d) None of the mentioned

### View Answer

4. Select the code snippet which returns the top of the stack.

a)

public int top() { if(q1.size()>0) { return q1.poll(); } else if(q2.size()>0) { return q2.poll(); } return 0; }

b)

public int top() { if(q1.size()==0) { return q1.peek(); } else if(q2.size()==0) { return q2.peek(); } return 0; }

c)

public int top() { if(q1.size()>0) { return q1.peek(); } else if(q2.size()>0) { return q2.peek(); } return 0; }

d) None of the mentioned

### View Answer

5. Select the code snippet which return true if the stack is empty, false otherwise.

a)

public boolean empty() { return q2.isEmpty(); }

b)

public boolean empty() { return q1.isEmpty() || q2.isEmpty(); }

c)

public boolean empty() { return q1.isEmpty(); }

d)

public boolean empty() { return q1.isEmpty() & q2.isEmpty(); }

### View Answer

6. Making the pop operation costly, select the code snippet which implements the same.

a)

public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q1.size(); while(count>0) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0) { count = q2.size(); while(count>0) q1.offer(q2.poll()); res = q2.poll(); } return res; }

b)

public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q1.size(); while(count>1) q2.offer(q1.poll()); res = q2.poll(); } if(q2.size()>0) { count = q2.size(); while(count>1) q1.offer(q2.poll()); res = q1.poll(); } return res; }

c)

public int pop() { int res=-999,count=0; if(q1.size()>0) { count = q1.size(); while(count>1) q2.offer(q1.poll()); res = q1.poll(); } if(q2.size()>0) { count = q2.size(); while(count>1) q1.offer(q2.poll()); res = q2.poll(); } return res; }

d) None of the mentioned

### View Answer

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

public void fun(int x) { q1.offer(x); }

a) Perform push() with push as the costlier operation

b) Perform push() with pop as the costlier operation

c) Perform pop() with push as the costlier operation

d) Perform pop() with pop as the costlier operation

### View Answer

## Set 5

1. Consider the following iterative implementation used to reverse a string:

#include<stdio.h> #include<string.h> void reverse_string(char *s) { int len = strlen(s); int i,j; i=0; j=len-1; while(______) { char tmp = s[i]; s[i] = s[j]; s[j] = tmp; i++; j--; } }

Which of the following lines should be inserted to complete the above code?

a) i > j

b) i < len

c) j > 0

d) i < j

### View Answer

2. What is the output of the following code?

#include<stdio.h> #include<string.h> void reverse_string(char *s) { int len = strlen(s); int i,j; i=0; j=len-1; while(i < j) { char tmp = s[i]; s[i] = s[j]; s[j] = tmp; i++; j--; } } int main() { char s[100] = "reverse"; reverse_string(s); printf("%s",s); return 0; }

a) ersevre

b) esrever

c) eserver

d) eresevr

### View Answer

3. What is the time complexity of the above code used to reverse a string?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

4. What does the following code do?

#include<stdio.h> #include<string.h> void reverse_string(char *s) { int len = strlen(s); int i,j; i=0; j=len-1; while(i < j) { char tmp = s[i]; s[i] = s[j]; s[j] = tmp; i++; j--; } } int main() { char s[100] = "abcdefg"; char t[100]; strcpy(t,s); reverse_string(s); if(strcmp(t,s) == 0) printf("Yes"); else printf("No"); return 0; }

a) Copies a string to another string

b) Compares two strings

c) Reverses a string

d) Checks if a string is a palindrome

### View Answer

5. What is the output of the following code?

#include<stdio.h> #include<string.h> void reverse_string(char *s) { int len = strlen(s); int i,j; i=0; j=len-1; while(i < j) { char tmp = s[i]; s[i] = s[j]; s[j] = tmp; i++; j--; } } int main() { char s[100] = "rotator"; char t[100]; strcpy(t,s); reverse_string(s); if(strcmp(t,s) == 0) printf("Yes"); else printf("No"); return 0; }

a) Yes

b) No

c) Runtime error

d) Compile time error

### View Answer

6. Consider the following recursive implementation used to reverse a string:

void recursive_reverse_string(char *s, int left, int right) { if(left < right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; _________; } }

Which of the following lines should be inserted to complete the above code?

a) recursive_reverse_string(s, left+1, right+1)

b) recursive_reverse_string(s, left-1, right-1)

c) recursive_reverse_string(s, left+1, right-1)

d) recursive_reverse_string(s, left-1, right+1)

### View Answer

7. What is the output of the following code?

#include<stdio.h> #include<string.h> void recursive_reverse_string(char *s, int left, int right) { if(left < right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; recursive_reverse_string(s, left+1, right-1); } } int main() { char s[100] = "recursion"; int len = strlen(s); recursive_reverse_string(s,0,len-1); printf("%s",s); return 0; }

a) recursion

b) nsoirucer

c) noisrcuer

d) noisrucer

### View Answer

8. How many times is the function recursive_reverse_string() called when the following code is executed?

#include<stdio.h> #include<string.h> void recursive_reverse_string(char *s, int left, int right) { if(left < right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; recursive_reverse_string(s, left+1, right-1); } } int main() { char s[100] = "madam"; int len = strlen(s); recursive_reverse_string(s,0,len-1); printf("%s",s); return 0; }

a) 3

b) 4

c) 5

d) 6

### View Answer

9. What is the time complexity of the above recursive implementation used to reverse a string?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

10. For which of the following cases will the reversal of a string be equal to the original string?

a) Palindromic strings

b) Strings of length 1

c) Empty String

d) All of the mentioned