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. Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?
a) Dynamic programming
b) Recursion
c) Brute force
d) All of the mentioned

Answer: d [Reason:] All of the mentioned methods can be used to solve the balanced partition problem.

2. In which of the following cases, it is not possible to have two subsets with equal sum?
a) When the number of elements is odd
b) When the number of elements is even
c) When the sum of elements is odd
d) When the sum of elements is even

Answer: c [Reason:] When the sum of all the elements is odd, it is not possible to have two subsets with equal sum.

3. What is the time complexity of the brute force algorithm used to solve the balanced partition problem?
a) O(1)
b) O(n)
c) O(n2)
d) O(2n)

Answer: d [Reason:] In the brute force implementation, all the possible subsets will be formed. This takes exponential time.

4. Consider a variation of the balanced partition problem in which we find two subsets such that |S1 – S2| is minimum. Consider the array {1, 2, 3, 4, 5}. Which of the following pairs of subsets is an optimal solution for the above problem?
a) {5, 4} & {3, 2, 1}
b) {5} & {4, 3, 2, 1}
c) {4, 2} & {5, 3, 1}
d) {5, 3} & {4, 2, 1}

Answer: d [Reason:] For S1 = {5, 3} and S2 = {4, 2, 1}, sum(S1) – sum(S2) = 1, which is the optimal solution.

5. Consider the following code:

```#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = _______________;
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}```

Which of the following lines should be inserted to complete the above code?
a) ans[i – arr[j – 1]][j – 1].
b) ans[i][j].
c) ans[i][j] || ans[i – arr[j – 1]][j – 1].
d) ans[i][j] && ans[i – arr[j – 1]][j – 1].

Answer: c [Reason:] The line “ans[i][j] || ans[i – arr[j – 1]][j – 1]” completes the above code.

6. What is the time complexity of the above dynamic programming implementation of the balanced partition problem where “n” is the number of elements and “sum” is their sum?
a) O(sum)
b) O(n)
c) O(sum * n)
d) O(sum + n)

Answer: c [Reason:] The time complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).

7. What is the space complexity of the above dynamic programming implementation of the balanced partition problem?
a) O(sum)
b) O(n)
c) O(sum * n)
d) O(sum + n)

Answer: c [Reason:] The space complexity of the above dynamic programming implementation of the balanced partition problem is O(sum * n).

8. What is the output of the following code?

```#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}```

a) True
b) False

Answer: a [Reason:] The partitions are S1 = {6, 7} and S2 = {1, 3, 4, 5} and the sum of each partition is 13. So, the array can be divided into balanced partitions.

9. What is the value stored in ans when the following code is executed?

```#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {3, 4, 5, 6, 7, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}```

a) 0
b) 1

Answer: b [Reason:] The value stored in ans indicates if a sum of 3 can be obtained using a subset of the first 3 elements. Since the sum can be obtained the value stored is 1.

10. What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?
a) 16
b) 32
c) 0
d) None of the mentioned

Answer: a [Reason:] The sum of all the elements of the array is 32. So, the sum of all the elements of each partition should be 16.

11. What is the output of the following code?

```#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {5, 6, 7, 10, 3, 1}, len = 6;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}```

a) True
b) False

Answer: a [Reason:] The array can be divided into two partitions S1 = {10, 6} and S2 = {5, 7, 3, 1} and the sum of all the elements of each partition is 16. So, the answer is true.

12. What is the output of the following code?

```#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 9;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}```

a) True
b) False

Answer: b [Reason:] Since the sum of all the elements of the array is 45, the array cannot be divided into two partitions of equal sum and the answer is false.

## Set 2

1. What is the space complexity of searching in a heap?
a) O(logn)
b) O(n)
c) O(1)
d) O(nlogn)

2. What is the best case complexity in builading a heap?
a) O(nlogn)
b) O(n2)
c) O(n*longn *logn)
d) O(n)

Answer: d [Reason:] The best case compexity occur in botton-up construction when we have a sortes array given.

3. Given the code ,choose the correct option that is consistent with the code

```	build(A,i)
left-> 2*i
right->2*i +1
temp- > i
if(left<= heap_length[A] ans A[left] >A[temp])
temp -> left
if (right = heap_length[A] and A[right] > A[temp])
temp->right
if temp!= i
swap(A[i],A[temp])
build(A,temp)```

Here A is the heap
a) It is the build function of max heap.
b) It is the build function of min heap.
c) It is general build function of any heap.
d) None of the mentioned

Answer: a [Reason:] Since in every condition we are comparing the current value is less than the parent of that node.So this is build function of Max heap.

4. What is the location of parent node for any arbitary node i?
a) (i/2) position
b) (i+1)/ position
c) floor(i/2) position
d) ceil(i/2) position

Answer: c [Reason:] For any node child nodes are located at either 2*i , 2*i +1 So the parent node could be found by taking the floor of the half of child node.

5. State the complexity of algorithm gien below

```	int function(vector<int> arr)
int len=arr.length();
if(len==0)
return;
temp=arr[len-1];
arr.pop_back();
return temp;```

a) o(n)
b) O(logn)
c) O(1)
d) O(n logn)

Answer: c [Reason:] Deletion in a min-heap is in O(1) time.

6. Given an array of element 5,7,9,1,3,10,8,4. Tick all the correct sequences of elements after inserting all the elements in a min-heap.
a) 1,3,4,7,8,9,10
b) 1,4,3,8,9,5,7,10
c) 1,3,4,5,8,7,9,10
d) None of these

Answer: a [Reason:] Building a min-heap the result will a sorted array so the option a is correct .If we change the implementation strategy option- b is also correct. (First filling the right child rather than left child first).

7. For construction of a binary heap with property that parent node has value less than child node.In reference to that which line is incorrect. Line indexed from 1.

```add(int k)
{
heap_size++;
int i = heap_size - 1;
harr[i] = k;
while (i != 0 && harr[parent(i)] < harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}```

a) Line -3
b) Line – 5
c) Line – 6
d) Line -7

Answer: b [Reason:] The condition under while condition is wrong for a (min) binary heap The correct condition should be while(i!=0 && harr[parent(i)] > harr[i]). Otherwise the constructed heap will be a max-binary heap.

## Set 3

1. Which of the following is false about a binary search tree?
a) The left child is always lesser than its parent
b) The right child is always greater than its parent
c) The left and right sub-trees should also be binary search trees
d) None of the mentioned

Answer: d [Reason:] All the options hold good for a binary search tree and can be considered as a definition for a BST.

2. How to search for a key in a binary search tree?
a)

```public Tree search(Tree root, int key)
{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}```

b)

```public Tree search(Tree root, int key)
{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.left,key);
}
else
return search(root.right,key);
}```

c)

```public Tree search(Tree root, int key)
{
if( root == null)
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}```

d) None of the mentioned

Answer: a [Reason:] As we know that the left child is lesser than the parent, if the root’s key is greater than the given key, we look only into the left sub-tree, similarly for right sub-tree.

3. What is the speciality about the inorder traversal of a binary search tree?
a) It traverses in a non increasing order
b) It traverses in an increasing order
c) It traverses in a random fashion
d) None of the mentioned

Answer: b [Reason:] As a binary search tree consists of elements lesser than the node to the left and the ones greater than the node to the right, an inorder traversal will give the elements in an increasing order.

4. What does the following piece of code do?

```public void func(Tree root)
{
func(root.left());
func(root.right());
System.out.println(root.data());
}```

a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal

Answer: c [Reason:] In a postorder traversal, first the left child is visited, then the right child and finally the parent.

5. What does the following piece of code do?

```public void func(Tree root)
{
System.out.println(root.data());
func(root.left());
func(root.right());
}```

a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal

Answer: a [Reason:] In a preorder traversal, first the parent is visited, then the left child and finally the right child.

6. How will you find the minimum element in a binary search tree?
a)

```public void min(Tree root)
{
while(root.left() != null)
{
root = root.left();
}
System.out.println(root.data());
}```

b)

```public void min(Tree root)
{
while(root != null)
{
root = root.left();
}
System.out.println(root.data());
}```

c)

```public void min(Tree root)
{
while(root.right() != null)
{
root = root.right();
}
System.out.println(root.data());
}```

d)

```public void min(Tree root)
{
while(root != null)
{
root = root.right();
}
System.out.println(root.data());
}```

Answer: a [Reason:] Since all the elements lesser than a given node will be towards the left, iterating to the leftmost leaf of the root will give the minimum element in a binary search tree.

7. How will you find the maximum element in a binary search tree?
a)

```public void max(Tree root)
{
while(root.left() != null)
{
root = root.left();
}
System.out.println(root.data());
}```

b)

```public void max(Tree root)
{
while(root != null)
{
root = root.left();
}
System.out.println(root.data());
}```

c)

```public void max(Tree root)
{
while(root.right() != null)
{
root = root.right();
}
System.out.println(root.data());
}```

d)

```public void max(Tree root)
{
while(root != null)
{
root = root.right();
}
System.out.println(root.data());
}```

Answer: c [Reason:] Since all the elements greater than a given node are towards the right, iterating through the tree to the rightmost leaf of the root will give the maximum element in a binary search tree.

8. What are the worst case and average case complexities of a binary search tree?
a) O(n), O(n)
b) O(logn), O(logn)
c) O(logn), O(n)
d) O(n), O(logn)

Answer: d [Reason:] Worst case arises when the tree is skewed(either to the left or right) in which case you have to process all the nodes of the tree giving O(n) complexity, otherwise O(logn) as you process only the left half or the right half of the tree.

9. Given that 2 elements are present in the tree, write a function to find the LCA(Least Common Ancestor) of the 2 elements.
a)

```public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.right();
else if (root.data() < n1 && root.data() < n2)
root = root.left();
else break;
}
System.out.println(root.data());
}```

b)

```public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() < n2)
root = root.left();
else if (root.data() < n1 && root.data() > n2)
root = root.right();
else break;
}
System.out.println(root.data());
}```

c)

```public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.left();
else if (root.data() < n1 && root.data() < n2)
root = root.right();
else break;
}
System.out.println(root.data());
}```

d) None of the mentioned

Answer: c [Reason:] The property of a binary search tree is that the lesser elements are to the left and greater elements are to the right, we use this property here and iterate through the tree such that we reach a point where the 2 elements are on 2 different sides of the node, this becomes the least common ancestor of the 2 given elements.

10. What are the conditions for an optimal binary search tree and what is its advantage?
a) The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost
b) You should know the frequency of access of the keys, improves the lookup time
c) The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time
d) None of the mentioned

Answer: a [Reason:] By definition.

## Set 4

1. Binary trees can have how many children?
a) 2
b) any number of children
c) 0 or 1 or 2
d) 0 or 1

Answer: c [Reason:] Can have atmost 2 nodes.

2. Disadvantage of using array representation for binary trees is?
a) difficulty in knowing children nodes of a node
b) difficult in finding the parent of a node
c) have to know the maximum number of nodes possible before creation of trees
d) difficult to implement

Answer: c [Reason:] The array is fixed size (may be dynamic array or static array) but size is fixed.

3. What must be the ideal size of array if the height of tree is ‘l’?
a) 2l-1
b) l-1
c) l
d) 2l

Answer: a [Reason:] Since maximum elements in a tree (complete binary tree) of height l will be 2l-1 so a good array size must be that (since a binary tree node may not always have 2 children but for safety a is correct).

4. What are the children for node ‘w’ of a complete-binary tree in an array representation ?
a) 2w and 2w+1
b) 2+w and 2-w
c) w+1/2 and w/2
d) w-1/2 and w+1/2

Answer: a [Reason:] Since each node has 2 children and so counting from beginning, a particular node will have children as option a.

5. What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?
a) floor(w-1/2)
b) ceil(w-1/2)
c) w-1/2
d) w/2

Answer: a [Reason:] Floor of w-1/2 because we can’t miss a node.

6. If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array ?
a) every node stores data saying which of its children exist in the array
b) no need of any changes continue with 2w and 2w+1, if node is at i
c) keep a seperate table telling children of a node
d) use another array parallel to the array with tree

Answer: a [Reason:] Array cannot represent arbitrary shaped trees it can only be used in case of complete trees hence option a must be done which is one of several ways to use array in such situations.

7. What must be the missing logic in place of missing lines for finding sum of nodes of binary tree in alternate levels?

```  //e.g:-consider -complete binary tree:-height-3, [1,2,3,4,5,6,7]-answer must be 23
n=power(2,height)-1; //assume input is height and a[i] contains tree elements
for(i=1;i<=n;)
{
for(j=1;j<=pow(2,currentlevel-1);j++) //present level is initialized to 1 and sum is initialized to  0
{
sum=sum+a[i];
i=i+1;
}
//missing logic
}```

a)

```   i=i+pow(2,currentlevel);
currentlevel=currentlevel+2;
j=1;```

b)

```   i=i+pow(2,currentlevel);
currentlevel=currentlevel+2;
j=0;```

c)

```   i=i-pow(2,currentlevel);
currentlevel=currentlevel+2;
j=1;```

d)

```   i=i+pow(2,currentlevel);
currentlevel=currentlevel+1;
j=1;```

Answer: a [Reason:] The i value must skip through all nodes in the next level and current level must be one+next level.

8. Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of tree is good ?
a) yes because we are overcoming the need of pointers and so space efficiency
b) yes because array values are indexable
c) No it is not efficient in case of sparse trees and remaning cases it is fine
d) No linked list representation of tree is only fine

Answer: c [Reason:] In case of sparse trees(where one node per level in worst cases), the array size (2^h)-1 where h is height but only h indexes will be filled and (2^h)-1-h nodes will be left unused leading to space wastage which was actually main theme of question.

9. Why is heap implemented using array representations than tree(linked list) representations though both tree representations and heaps have same complexities ?

```for binary heap
-insert: O(log n)
-delete min: O(log n)

for a tree
-insert: O(log n)
-delete: O(log n)```

Then why go with array representation when both are having same values ?
a) arrays can store trees which are complete and heaps are by it’s property are complete
b) lists representation takes more memory hence memory efficiency is less and go with arrays
c) array have better caching
d) all of the mentioned

Answer: d [Reason:] In memory the pointer address for next node may not be adjacent or nearer to each other and also array have wonderful caching power from os and manipulating pointers is a overhead.

10. Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed ?
a) yes just traverse through the array and form the tree
b) No we need one more traversal to form a tree
c) No in case of sparse trees
d) None of the mentioned

Answer: b [Reason:] we need any two traversals for tree formation but if some additional stuff or techniques are used while storing a tree in an array then one traversal can facilitate like also storing null values of a node in array.

## Set 5

1. Advantages of linked list representation of binary trees over arrays?
a) dynamic size
b) ease of insertion/deletion
c) ease in randomly accessing a node
d) both dynamic size and ease in insertion/deletion

Answer: d [Reason:] It has both dynamic size and ease in insertion and deletion as advantages.

2. Disadvantages of linked list representation of binary trees over arrays ?
a) Randomly accessing is not possible
b) Extra memory for a pointer is needed with every element in the list
c) Difficulty in deletion
d) Random access is not possible and extra memory with every element

Answer: d [Reason:] Random access is not possible with linked lists.

3. How to travel a tree in linkedlist representation ?
a) using post order traversing
b) using pre order traversing
c) using post order traversing
d) all of the mentioned

Answer: d [Reason:] Also level order traversing is possible.

4. Level order traversal of a tree is formed with the help of
a) breadth first search
b) depth first search
c) dijkstra’s algorithm
d) prims algorithm

Answer: a [Reason:] Level order is similar to bfs.

5. Why we prefer threaded binary trees ?
a) storage required by stack and queue is more
b) pointers in most of nodes of a binary tree are NULL
c) difficult to find a successor node
d) all of the mentioned

Answer: d [Reason:] All the given options are properties for a threaded tree.

6. The following lines talks about deleting a node in a binary tree.(the tree property must not be violated after deletion)
i) from root search for the node to be deleted
ii)
iii) delete the node at
what must be statement ii) and fill up statement iii)
a) ii)-find random node,replace with node to be deleted. iii)- delete the node
b) ii)-find node to be deleted. iii)- delete the node at found location
c) ii)-find deepest node,replace with node to be deleted. iii)- delete a node
d) ii)-find deepest node,replace with node to be deleted. iii)- delete the deepest node

Answer: d [Reason:] We just replace a to be deleted node with last leaf node of a tree. this must not be done in case of BST or heaps.

7. What may be the psuedo code for finding the size of a tree?
a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)
b) find_size(root_node–>left_node) + find_size(root_node–>right_node)
c) find_size(root_node–>right_node) – 1
d) find_size(root_node–>left_node + 1

Answer: a [Reason:] Draw a tree and analyze the expression. we are always taking size of left subtree and right subtree and adding root value(1) to it and finally printing size.

8. What is missing in this logic of finding a path in the tree for a given sum (i.e checking whether there will be a path from roots to leaf nodes with given sum) ?

```checkSum(struct bin-treenode *root , int sum) :
if(root==null)
return sum as 0
else :
leftover_sum=sum-root_node-->value
//missing```

a) code for having recursive calls to either only left tree or right trees or to both subtrees depending on their existence
b) code for having recursive calls to either only left tree or right trees
c) code for having recursive calls to either only left tree
d) code for having recursive calls to either only right trees

Answer: a [Reason:] if(left subtree and right subtree) then move to both subtrees else if only left subtree then move to left subtree carrying leftover_sum parameter else if only right subtree then move to right subtree carrying leftover_sum parameter.

9. What must be the missing logic below so as to print mirror of a tree as below as an example? ```if(rootnode):
mirror(rootnode-->left)
mirror(rootnode-->right)

//missing

end```

a) swapping of left and right nodes is missing
b) swapping of left with root nodes is missing
c) swapping of right with root nodes is missing
d) nothing is missing

Answer: a [Reason:] Mirror is another tree with left and right children of nodes are interchanged as shown in the figure.

10. What is the code below trying to print ?

```void print(tree *root,tree *node)
{
if(root ==null) return 0
if(root-->left==node || root-->right==node || print(root->left,node)||printf(root->right,node)
{
print(root->data)
}
}```

a) just printing all nodes
b) not a valid logic to do any task
c) printing ancestors of a node passed as argument
d) printing nodes from leaf node to a node passed as argument