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

Answer: a [Reason:] Iterative linear search can be used to search an element in an unsorted array. Note: Binary search can be used only when the array is sorted.

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

Answer: d [Reason:] All of the above mentioned techniques can be used to search an element in the above array.

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 ={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

Answer: b [Reason:] The code finds the index of the first occurrence of the number that is searched.

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 ={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

Answer: b [Reason:] The program prints the index of the first occurrence of 3, which is 1.

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(n2)
d) O(n3)

Answer: b [Reason:] The time complexity of the above code used to search an element in an array is O(n).

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 ={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);

Answer: c [Reason:] The recursive call “recursive_search_num(arr, num, idx+1, len)” should be added to complete the above code.

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 ={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

Answer: a [Reason:] The program prints the index of 5, which is 5.

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 ={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

Answer: b [Reason:] The function recursive_search_num() is called 6 times when the above code is executed.

9. What is the time complexity of the above recursive implementation of linear search?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b [Reason:] The time complexity of the above recursive implementation of linear search is O(n).

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

Answer: b [Reason:] It is a datastructure, which can make search in sorted linked list faster in the same way as binary search tree and sorted array (using binary search) are faster.

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

Answer: a [Reason:] Let us call the nodes 20, 30, 40 as top lines and the nodes between them as normal lines. the advantage of skip lists is we can skip all the elements between the top line elements as required.

3. Skip lists are similar to which of the following datastructure?
a) stack
b) heap
c) binary search tree
d) balanced binary search tree

Answer: d [Reason:] As all elements lesser than the top line elements are placed infront of it and greater ones after it. please refer question for clarity. skip lists have the same asymptotic time complexities as balanced trees.

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(n2) where n is number of elements

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

Answer: a [Reason:] Skip lists are similar to any randomly built binary search tree. a BST is balanced because to avoid skew tree formations in case of sequential input and hence achieve O(logn) in all 3 cases. now skip lists can gurantee that O(logn) complexity for any input.

6. The nodes in a skip list may have many forward references. their number is determined
a) probabilistically
b) randomly
c) sequentially
d) orthogonally

Answer: a [Reason:] The number of forward references are determined probabilistically, that is why skip list is a probabilistic algorithm.

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

Answer: a [Reason:] To achieve above operations augment with few additional stuff like partial counts.

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

Answer: a [Reason:] for example consider a 2 level skip list. the level-2 skip list can skip one node on a average and at some places may skip 2 nodes, depending on probabilities. this ensures O(logn).

9. Is a skip list like balanced tree?
a) true, atleast like a balanced tree with good probabilities
b) false

Answer: a [Reason:] Skip list behaves as a balanced tree with high probability and can be commented as such because nodes with different heights are mixed up evenly.

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

Answer: a [Reason:] The width is defined as number of bottom layer links that are being traversed by each of higher layer elements. e.g: for a level-2 skip lists, all level-1 nodes have 1 as width, for level-2 width will be 2.

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

Answer: a [Reason:] Splay trees are height balanced, self adjusting BST’s.

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

Answer: b [Reason:] This is a property of splay tree that ensures faster access. we push the most recently used nodes to top which leads to faster access to recently used values.

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

Answer: c [Reason:] Whenever you insert an element or remove or read an element that will be pushed or stored at the top which facilitates easier access or recently used stuff.

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

Answer: a [Reason:] We go with amortized time complexity when we feel that not all operations are worst and some can be efficiently done. in splay trees not all splay operations will lead to O(logn) worst case complexity.

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

Answer: b [Reason:] Splay trees mainly work using splay operations. wheneve we insert, delete and search for a node we splay the respective nodes to root. we have zig-zag and zig-zig operations.

6. Which of the following options is an application of splay trees ?
a) cache Implementation
b) networks
c) send values

Answer: a [Reason:] Splay trees can be used for faster access to recently accessed items and hence used for cache implementations.

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

Answer: b [Reason:] May be the stats showing 80-20% may be not accurate, but in real time that is the widely spread scenario seen. If you are into this type of situation, you must choose implementing splay trees.

8. After the insertion operation, is the resultant tree a splay tee? a) true
b) false

Answer: a [Reason:] There is a zig-zag and right operation(zig) which gives the right hand side tree. refer splay operations for insertion in splay tree.

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

Answer: a [Reason:] When a right rotation is done the parent of the rotating node becomes it’s right node and it’s child becomes it’s left child.

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

Answer: a [Reason:] This will be the case after accessing all n elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be high. However the amortized access cost of this worst case is logarithmic O(log n).

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

Answer: b [Reason:] Either the push or the pop has to be a costly operation, and the costlier operation requires two queues.

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

Answer: a [Reason:] Stack follows LIFO principle, hence a new item added must be the first one to exit, but queue follows FIFO principle, so when a new item is entered into the queue, it will be at the rear end of the queue. If the queue is initially empty, then just add the new element, otherwise add the new element to the second queue and dequeue all the elements from the second queue and enqueue it to the first one, in this way, the new element added will be always in front of the queue. Since two queues are needed to realize this push operation, it is considered to be costlier.

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

Answer: b [Reason:] As the push operation is costly, it is evident that the required item is in the front of the queue, so just dequeue the element from the queue.

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

Answer: c [Reason:] Assuming its a push costly implementation, the top of the stack will be in the front end of the queue, note that peek() just returns the front element, while poll() removes the front element from the queue.

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

Answer: d [Reason:] If both the queues are empty, then the stack also is empty.

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

Answer: c [Reason:] Here the pop operation is costly, hence we need two queues, other than the first element, all the the elements from one queue are dequeued and enqueued to the second queue, hence only one element remains in the first queue which is the item we want, so dequeue it and return the result.

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

Answer: b [Reason:] offer() suggests that it is a push operation, but we see that it is performed with only one queue, hence the pop operation is costlier.

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

Answer: d [Reason:] The line “i < j” should be inserted to complete the above code.

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 = "reverse";
reverse_string(s);
printf("%s",s);
return 0;
}```

a) ersevre
b) esrever
c) eserver
d) eresevr

Answer: b [Reason:] The program reverses the string “reverse” and prints “esrever”.

3. What is the time complexity of the above code used to reverse a string?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

Answer: b [Reason:] The time complexity of the above code used to reverse a string is O(n).

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 = "abcdefg";
char t;
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

Answer: d [Reason:] The main purpose of the above code is to check if a string is a palindrome.

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 = "rotator";
char t;
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

Answer: a [Reason:] The program checks if a string is a palindrome. Since the string rotator is a palindrome, it prints “yes”.

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)

Answer: c [Reason:] The line “recursive_reverse_string(s, left+1, right-1)” should be inserted to complete the above code.

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 = "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

Answer: d [Reason:] The program prints the reversed string of “recursion”, which is “noisrucer”.

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 = "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

Answer: a [Reason:] The function recursive_reverse_string() is called 3 times when the above code is executed.

9. What is the time complexity of the above recursive implementation used to reverse a string?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)