# 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

### View Answer

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

### View Answer

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

d) O(2^{n})

### View Answer

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}

### View Answer

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[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 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].

### View Answer

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)

### View Answer

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)

### View Answer

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[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 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

### View Answer

9. What is the value stored in ans[3][3] 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[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 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

### View Answer

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

### View Answer

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[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 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

### View Answer

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[0][i] = 1; for(i = 1; i <= sm/2; i++) ans[i][0] = 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

### View Answer

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

### View Answer

2. What is the best case complexity in builading a heap?

a) O(nlogn)

b) O(n^{2})

c) O(n*longn *logn)

d) O(n)

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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)

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

3. What must be the ideal size of array if the height of tree is ‘l’?

a) 2^{l}-1

b) l-1

c) l

d) 2l

### View Answer

^{l}-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

### View Answer

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

### View Answer

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

### View Answer

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;

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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