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 the advantage of recursive approach than an iterative approach?
a) Consumes less memory
b) Less code and easy to implement
c) Consumes more memory
d) All of the mentioned

Answer: b [Reason:] A recursive approach is easier to understand and contains fewer lines of code.

2. Choose the appropriate code that does binary search using recursion.
a)

```public static int recursive(int arr[], int low, int high, int key)
{
int mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
return recursive(arr,mid+1,high,key);
}
else
{
return recursive(arr,low,mid-1,key);
}
}```

b)

```public static int recursive(int arr[], int low, int high, int key)
{
int mid = low + (high + low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
return recursive(arr,mid-1,high,key);
}
else
{
return recursive(arr,low,mid+1,key);
}
}```

c)

```public static int recursive(int arr[], int low, int high, int key)
{
int mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
return recursive(arr,mid,high,key);
}
else
{
return recursive(arr,low,mid-1,key);
}
}```

d) None of the mentioned

Answer: a [Reason:] Calculate the ‘mid’ value, and check if that is the key, if not, call the function again with 2 sub arrays, one with till mid-1 and the other starting from mid+1.

3. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
a) 5
b) 2
c) 3
d) 4

Answer: c [Reason:] level 1: mid = 7 level 2: mid = 99 level 3: mid = 899(this is the key)

4. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
a) 90 and 99
b) 90 and 94
c) 89 and 99
d) 89 and 94

Answer: a [Reason:] Trace the input with the binary search recursive code.

5. What is the worst case complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: b [Reason:] Using the divide and conquer master theorem.

6. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: b [Reason:] T(n) = T(n/2) + 1, Using the divide and conquer master theorem.

7. What are the applications of binary search?
a) To find the lower/upper bound in an ordered sequence
b) Union of intervals
c) Debugging
d) All of the mentioned

Answer: d [Reason:] All of the mentioned can be realized by binary search.

8. Choose among the following code for an iterative binary search.
a)

```public static int iterative(int arr[], int key)
{
int low = 0;
int mid = 0;
int high = arr.length-1;
while(low <= high)
{
mid = low + (high + low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
low = mid - 1;
}
else
{
high = mid + 1;
}
}
return -1;
}```

b)

```public static int iterative(int arr[], int key)
{
int low = 0;
int mid = 0;
int high = arr.length-1;
while(low <= high)
{
mid = low + (high - low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}```

c)

```public static int iterative(int arr[], int key)
{
int low = 0;
int mid = 0;
int high = arr.length-1;
while(low <= high)
{
mid = low + (high + low)/2;
if(arr[mid] == key)
{
return mid;
}
else if(arr[mid] < key)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return -1;
}```

d) None of the mentioned

Answer: b [Reason:] Find the ‘mid’, check if it equals the key, if not, continue the iterations until low <= high.

9. Binary Search can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming

Answer: b [Reason:] Since ‘mid’ is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.

10. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
a) 1
b) 3
c) 4
d) 2

Answer: d [Reason:] Iteration1 : mid = 77; Iteration2 : mid = 88;

11. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations?
a) 90 and 99
b) 90 and 100
c) 89 and 94
d) 94 and 99

Answer: a [Reason:] Trace the input with the binary search iterative code.

12. What is the time complexity of binary search with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: b [Reason:] T(n) = T(n/2) + theta(1) Using the divide and conquer master theorem, we get the time complexity as O(logn).

## Set 2

1. The number of edges from the root to the node is called __________ of the tree.
a) Height
b) Depth
c) Length
d) None of the mentioned

Answer: b [Reason:] By definition.

2. The number of edges from the node to the deepest leaf is called _________ of the tree.
a) Height
b) Depth
c) Length
d) None of the mentioned

Answer: a [Reason:] By definition.

3. What is a full binary tree?
a) Each node has exactly zero or two children
b) Each node has exactly two children
c) All the leaves are at the same level
d) Each node has exactly one or two children

Answer: a [Reason:] By definition.

4. What is a complete binary tree?
a) Each node has exactly zero or two children
b) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left
c) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right
d) None of the mentioned

Answer: c [Reason:] By definition.

5. What is the time complexity for finding the height of the binary tree?
a) h = O(loglogn)
b) h = O(nlogn)
c) h = O(n)
d) h = O(log n)

Answer: d [Reason:] The nodes are either a part of left sub tree or the right sub tree, so we don’t have to traverse all the nodes, this means the complexity is lesser than n, in the average case, assuming the nodes are spread evenly, the time complexity becomes O(n).

6. Which of the following is not an advantage of trees?
a) Hierarchical structure
b) Faster search
c) Router algorithms
d) Undo/Redo operations in a notepad

Answer: d [Reason:] This is an application of stack.

7. In a full binary tree if number of internal nodes is I, then number of leaves L are?
a) L = 2I
b) L = I + 1
c) L = I – 1
d) L = 2I – 1

Answer: b [Reason:] Trace with respect to the diagram.

8. In a full binary tree if number of internal nodes is I, then number of nodes N are?
a) N = 2I
b) N = I + 1
c) N = I – 1
d) N = 2I + 1

Answer: d [Reason:] Trace with respect to the diagram.

9. In a full binary tree if there are L leaves, then total number of nodes N are?
a) N = 2L
b) N = L + 1
c) N = L – 1
d) N = 2L – 1

Answer: d [Reason:] Trace with respect to the diagram.

10. Which of the following is correct with respect to binary trees?
a) Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k
b) Let T be a binary tree with λ levels. Then T has no more than 2λ – 1 nodes
c) Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))
d) All of the mentioned

Answer: d [Reason:] Refer the diagram.

## Set 3

1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
a) Pre-order Traversal
b) Post-order Traversal
c) Level-order Traversal
d) In-order Traversal

Answer: c [Reason:] The Breadth First Search Algorithm searches the nodes on the basis of level. It takes a node (level 0), explores it’s neighbors (level 1) and so on.

2. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)
a) O(V + E)
b) O(V)
c) O(E)
d) None of the mentioned

Answer: a [Reason:] The Breadth First Search explores every node once and every edge once (in worst case), so it’s time complexity is O(V + E).

3. The Data structure used in standard implementation of Breadth First Search is?
a) Stack
b) Queue
d) None of the mentioned

Answer: b [Reason:] The Breadth First Search explores every node once and put that node in queue and then it takes out nodes from the queue and explores it’s neighbors.

4. The Breadth First Search traversal of a graph will result into?
b) Tree
c) Graph with back edges
d) All of the mentioned

Answer: b [Reason:] The Breadth First Search will make a graph which don’t have back edges (a tree) which is known as Breadth First Tree.

5. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?
a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) None of the mentioned

Answer: b [Reason:] This is the definition of the Breadth First Search. Exploring a node, then it’s neighbors and so on.

6. What can be the applications of Breadth First Search?
a) Finding shortest path between two nodes
b) Finding bipartiteness of a graph
c) GPS navigation system
d) All of the mentioned

Answer: d [Reason:] Breadth First Search can be applied to all of the mentioned problems. Bipartiteness of a graph means that a graph can be divided into two disjoint sets such that every edge connects a vertex in to one in.

7. When the Breadth First Search of a graph is unique?
a) When the graph is a Binary Tree
b) When the graph is a Linked List
c) When the graph is a n-ary Tree
d) None of the mentioned

Answer: b [Reason:] When Every node will have one successor then the Breadth First Search is unique. In all other cases, when it will have more than one successor, it can choose any of them in arbitrary order.

8. Regarding implementation of Breadth First Search using queues, what is the maximum distance between two nodes present in the queue? (considering each edge length 1)
a) Can be anything
b) 0
c) At most 1
d) Insufficient Information

Answer: c [Reason:] In the queue, at a time, only those nodes will be there whose difference among levels is 1. Same as level order traversal of the tree.

9. In BFS, how many times a node is visited?
a) Once
b) Twice
c) equivalent to number of indegree of the node
d) None of the mentioned

Answer: c [Reason:] In Breadth First Search, we have to see whether the node is visited or not by it’s ancestor. If it is visited, we won’t let it enter it in the queue.

## Set 4

1. What is an external sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’

Answer: a [Reason:] As the name suggests, external sorting algorithm uses external memory like tape or disk.

2. What is an internal sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’

Answer: b [Reason:] As the name suggests, internal sorting algorithm uses internal main memory.

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

Answer: d [Reason:] Bubble sort works by starting from the first element and swapping the elements if required in each iteration.

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

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

b)

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

c)

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

d) None of the mentioned

Answer: a [Reason:] The outer loop keeps count of number of iterations, and the inner loop checks to see if swapping is necessary.

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

Answer: d [Reason:] Bubble sort works by starting from the first element and swapping the elements if required in each iteration even in the average case.

6. What is the advantage of bubble sort over other sorting techniques?
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) All of the mentioned

Answer: c [Reason:] Bubble sort is one of the simplest sorting techniques and perhaps the only advantage it has over other techniques is that it can detect whether the input is already sorted.

7. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array?
a) 4
b) 2
c) 1
d) 0

Answer: a [Reason:] Even though the first two elements are already sorted, bubble sort needs 4 iterations to sort the given array.

8. How can you improve the best case efficiency in bubble sort? (The input is already sorted)
a)

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

b)

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

c)

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

d)

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

Answer: c [Reason:] A boolean variable ‘swapped’ determines whether any swapping has happened in a particular iteration, if no swapping has occurred, then the given array is sorted and no more iterations are required.

9. What is the best case efficiency of bubble sort in the improvised version?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

Answer: c [Reason:] Some iterations can be skipped if the list is sorted, hence efficiency improves to O(n).

10. The given array is arr = {1,2,4,3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array with improvised version?
a) 4
b) 2
c) 1
d) 0

Answer: 2 [Reason:] Only 2 elements in the given array are not sorted, hence only 2 iterations are required to sort them.

## Set 5

1. What differentiates a circular linked list from a normal linked list?
a) You cannot have the ‘next’ pointer point to null in a circular linked list
b) It is faster to traverse the circular linked list
c) You may or may not have the ‘next’ pointer point to null in a circular linked list
d) All of the mentioned

Answer: c [Reason:] The ‘next’ pointer points to null only when the list is empty, otherwise it points to the head of the list.

2. How do you count the number of elements in the circular linked list?
a)

```public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
{
temp = temp.getNext();
length++;
}
return length;
}```

b)

```public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
while(temp != null)
{
temp = temp.getNext();
length++;
}
return length;
}```

c)

```public int length(Node head)
{
int length = 0;
if( head == null)
return 0;
Node temp = head.getNext();
while(temp != head && temp != null)
{
length++;
}
return length;
}```

d) None of the mentioned

Answer: a [Reason:] If the head is null, it means that the list is empty. Otherwise, traverse the list until the head of the list is reached.

3. What is the functionality of the following piece of code? Select the most appropriate

```public void function(int data)
{
int flag = 0;
if( head != null)
{
Node temp = head.getNext();
while((temp != head) && (!(temp.getItem() == data)))
{
temp = temp.getNext();
flag = 1;
break;
}
}
if(flag)
System.out.println("success");
else
System.out.println("fail");
}```

a) Print success if a particular element is not found
b) Print fail if a particular element is not found
c) Print success if a particular element is equal to 1
d) Print fail if the list is empty

Answer: b [Reason:] The function prints fail if the given element is not found. Note that this option is inclusive of option d, the list being empty is one of the cases covered.

4. What is the time complexity of searching for an element in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) None of the mentioned

Answer: a [Reason:] In the worst case, you have to traverse through the entire list of n elements.

5. Which of the following application makes use of a circular linked list?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) All of the mentioned

Answer: c [Reason:] Generally, round robin fashion is employed to allocate CPU time to resources which makes use of the circular linked list data structure.

6. Choose the code snippet which inserts a node to the head of the list?
a)

```public void insertHead(int data)
{
Node temp = new Node(data);
Node cur = head;
cur = cur.getNext()
{
}
else
{
cur.setNext(temp);
}
size++;
}```

b)

```public void insertHead(int data)
{
Node temp = new Node(data);
cur = cur.getNext()
{
}
else
{
cur.setNext(temp);
}
size++;
}```

c)

```public void insertHead(int data)
{
Node temp = new Node(data);
{
}
else
{
}
size++;
}```

d)

```public void insertHead(int data)
{
Node temp = new Node(data);
{
}
else
{
}
size++;
}```

Answer: a [Reason:] If the list is empty make the new node as ‘head’, otherwise traverse the list to the end and make its ‘next’ pointer point to the new node, set the new node’s next point to the current head and make the new node as the head.

7. What is the functionality of the following code? Choose the most appropriate answer.

```public int function()
{
return Integer.MIN_VALUE;
int var;
Node temp = head;
temp = temp.getNext();
{
return var;
}
return var;
}```

a) Return data from the end of the list
b) Returns the data and deletes the node at the end of the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the beginning of the list

Answer: d [Reason:] First traverse through the list to find the end node, then manipulate the ‘next’ pointer such that it points to the current head’s next node, return the data stored in head and make this next node as the head.

8. What is the functionality of the following code? Choose the most appropriate answer.

```public int function()
{
return Integer.MIN_VALUE;
int var;
Node temp = head;
Node cur;
{
cur = temp;
temp = temp.getNext();
}
{
return var;
}
var = temp.getItem();
return var;
}```

a) Return data from the end of the list
b) Returns the data and deletes the node at the end of the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the beginning of the list

Answer: b [Reason:] First traverse through the list to find the end node, also have a trailing pointer to find the penultimate node, make this trailing pointer’s ‘next’ point to the head and return the data stored in the ‘temp’ node.

9. Which of the following is false about a circular linked list?
a) Every node has a successor
b) Time complexity of inserting a new node at the head of the list is O(1)
c) Time complexity for deleting the last node is O(n)
d) None of the mentioned