# Multiple choice question for engineering

## Set 1

1. For the tree below, write the pre-order traversal.

a) 2, 7, 2, 6, 5, 11, 5, 9, 4

b) 2, 7, 5, 2, 6, 9, 5, 11, 4

c) 2, 5, 11, 6, 7, 4, 9, 5, 2

d) 2, 7, 5, 6, 11, 2, 5, 4, 9

### View Answer

2. For the tree below, write the post-order traversal.

a) 2, 7, 2, 6, 5, 11, 5, 9, 4

b) 2, 7, 5, 2, 6, 9, 5, 11, 4

c) 2, 5, 11, 6, 7, 4, 9, 5, 2

d) 2, 7, 5, 6, 11, 2, 5, 4, 9

### View Answer

3. Select the code snippet which performs pre-order traversal.

a)

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

b)

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

c)

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

d) None of the mentioned

### View Answer

4. Select the code snippet which performs post-order traversal.

a)

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

b)

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

c)

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

d) None of the mentioned

### View Answer

5. Select the code snippet that performs pre-order traversal iteratively.

a)

public void preOrder(Tree root) { if (root == null) return; Stack<Tree> stk = new Stack<Tree>(); st.add(root); while (!stk.empty()) { Tree node = stk.pop(); System.out.print(node.data + " "); if (node.left != null) stk.push(node.left); if (node.right != null) stk.push(node.right); } }

b)

public void preOrder(Tree root) { if (root == null) return; Stack<Tree> stk = new Stack<Tree>(); while (!stk.empty()) { Tree node = stk.pop(); System.out.print(node.data + " "); if (node.right != null) stk.push(node.right); if (node.left != null) stk.push(node.left); } }

c)

public void preOrder(Tree root) { if (root == null) return; Stack<Tree> stk = new Stack<Tree>(); st.add(root); while (!stk.empty()) { Tree node = stk.pop(); System.out.print(node.data + " "); if (node.right != null) stk.push(node.right); if (node.left != null) stk.push(node.left); } }

d) None of the mentioned

### View Answer

6. Select the code snippet that performs post-order traversal iteratively.

a)

public void postorder(Tree root) { if (root == null) return; Stack<Tree> stk = new Stack<Tree>(); Tree node = root; while (!stk.isEmpty() || node != null) { while (node != null) { if (node.right != null) stk.add(node.left); stk.add(node); node = node.right; } node = stk.pop(); if (node.right != null && !stk.isEmpty() && node.right == stk.peek()) { Trees nodeRight = stk.pop(); stk.push(node); node = nodeRight; } else { System.out.print(node.data + " "); node = null; } } }

b)

public void postorder(Tree root) { if (root == null) return; Stack<Tree> stk = new Stack<Tree>(); Tree node = root; while (!stk.isEmpty() || node != null) { while (node != null) { if (node.right != null) stk.add(node.right); stk.add(node); node = node.left; } node = stk.pop(); if (node.right != null && !stk.isEmpty() && node.right == stk.peek()) { Trees nodeRight = stk.pop(); stk.push(node); node = nodeRight; } else { System.out.print(node.data + " "); node = null; } } }

c)

public void postorder(Tree root) { if (root == null) return; Stack<Tree> stk = new Stack<Tree>(); Tree node = root; while (!stk.isEmpty() || node != null) { while (node != null) { if (node.right != null) stk.add(node.right); stk.add(node); node = node.left; } node = stk.pop(); if (node.right != null) { Trees nodeRight = stk.pop(); stk.push(node); node = nodeRight; } else { System.out.print(node.data + " "); node = null; } } }

d) None of the mentioned

### View Answer

7. What is the time complexity of pre-order traversal in the iterative fashion?

a) O(1)

b) O(n)

c) O(logn)

d) O(nlogn)

### View Answer

8. What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)

a) O(1)

b) O(nlogd)

c) O(logd)

d) O(d)

### View Answer

9. To obtain a prefix expression, which of the tree traversals is used?

a) Level-order traversal

b) Pre-order traversal

c) Post-order traversal

d) In-order traversal

### View Answer

## Set 2

1. In which of the following does a Directed Acyclic Word Graph finds its application in?

a) String Matching

b) Number Sorting

c) Manipulations on numbers

d) None of the mentioned

### View Answer

Answer the following questions(2-3) for the given DWAG.

2. What is the number of words that can be formed from the given Directed Acyclic Word Graph?

a) 2

b) 4

c) 12

d) 7

### View Answer

3. Determine the longest string which is described by the given Directed Acyclic Word Graph.

a) BATS

b) BOATS

c) BOT

d) None of the mentioned

### View Answer

4. What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?

a) O(S1)

b) O(S2)

c) O(S1+S2)

d) O(1)

### View Answer

5. In which of the following case does a Propositional Directed Acyclic Graph is used for?

a) Representation of Boolean Functions

b) String Matching

c) Searching

d) Sorting of number

### View Answer

For the given symbols answer the following questions.

i) Δ

ii) ◊

iii) ∇

iv) T

v) ⊥

6. Which of the given symbols represent nodes having at least one child?

a) iv) and v)

b) iii) iv) and v)

c) i) and ii)

d) i) and iii)

### View Answer

7. Which of the given symbols represent nodes having exactly one child?

a) iv) and v)

b) v)

c) i) and iii)

d) ii)

### View Answer

8. Which of the given symbols represent may represent leaf nodes?

a) iv) and v)

b) v)

c) i) and iii)

d) ii)

### View Answer

9. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.

a) True

b) False

### View Answer

10. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.

a) True

b) False

### View Answer

## Set 3

1. 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] ={-11,2,-3,0,3,5,-6,7},num = -2,len = 8; int indx = recursive_search_num(arr,num,0,len); printf("Index of %d is %d",num,indx); return 0; }

a) Index of -2 is 1

b) Index of -2 is 0

c) Index of -2 is -1

d) None of the mentioned

### View Answer

2. What does the following code do?

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

a) Adds all the indexes of the number 0

b) Finds the first last occurrence of the number 0

c) Counts the number of occurrences of the number 0

d) None of the mentioned

### View Answer

3. Consider the following recursive implementation of the binary search:

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

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

a) hi = mid – 1

b) mid = (lo + hi)/2

c) mid = lo – 1

d) lo = mid + 1

### View Answer

4. What is the output of the following code?

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

a) Index of 7 is 4

b) Index of 7 is 5

c) Index of 7 is 6

d) Index of 7 is 7

### View Answer

5. What is the output of the following code?

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

a) Index of 0 is 0

b) Index of 0 is 1

c) Index of 0 is 2

d) Index of 0 is 3

### View Answer

6. What is the time complexity of the above recursive implementation of binary search?

a) O(n)

b) O(2^{n})

c) O(logn)

d) O(n!)

### View Answer

7. In which of the below cases will the following code produce a wrong output?

int recursive_binary_search(int *arr, int num, int lo, int hi) { if(lo > hi) return -1; int mid = (lo + hi)/2; if(arr[mid] == num) return mid; else if(arr[mid] < num) lo = mid + 1; else hi = mid - 1; return recursive_binary_search(arr, num, lo, hi); }

a) Array: {0,0,0,0,0,0} Search: -10

b) Array: {1,2,3,4,5} Search: 0

c) Array: {5,4,3,2,1} Search: 1

d) Array: {-5,-4,-3,-2,-1} Search: -1

### View Answer

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

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

a) 0

b) 1

c) 2

d) 3

### View Answer

9. What is the output of the following code?

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

a) Index of 1 is 4

b) Index of 1 is 5

c) Index of 1 is -1

d) Index of 1 is 0

### View Answer

## Set 4

1. Recursion is a method in which the solution of a problem depends on ____________

a) Larger instances of different problems

b) Larger instances of the same problem

c) Smaller instances of the same problem

d) Smaller instances of different problems

### View Answer

2. Which of the following problems can be solved using recursion?

a) Factorial of a number

b) Nth fibonacci number

c) Length of a string

d) All of the mentioned

### View Answer

3. Recursion is similar to which of the following?

a) Switch Case

b) Loop

c) If-else

d) None of the mentioned

### View Answer

4. In recursion, the condition for which the function will stop calling itself is ____________

a) Best case

b) Worst case

c) Base case

d) There is no such condition

### View Answer

5. Consider the following code snippet:

void my_recursive_function() { my_recursive_function(); } int main() { my_recursive_function(); return 0; }

What will happen when the above snippet is executed?

a) The code will be executed successfully and no output will be generated

b) The code will be executed successfully and random output will be generated

c) The code will show a compile time error

d) The code will run for some time and stop when the stack overflows

### View Answer

6.What is the output of the following code?

void my_recursive_function(int n) { if(n == 0) return; printf("%d ",n); my_recursive_function(n-1); } int main() { my_recursive_function(10); return 0; }

a) 10

b) 1

c) 10 9 8 … 1 0

d) 10 9 8 … 1

### View Answer

7. What is the base case for the following code?

void my_recursive_function(int n) { if(n == 0) return; printf("%d ",n); my_recursive_function(n-1); } int main() { my_recursive_function(10); return 0; }

a) return

b) printf(“%d “, n)

c) if(n == 0)

d) my_recursive_function(n-1)

### View Answer

8. How many times is the recursive function called, when the following code is executed?

void my_recursive_function(int n) { if(n == 0) return; printf("%d ",n); my_recursive_function(n-1); } int main() { my_recursive_function(10); return 0; }

a) 9

b) 10

c) 11

d) 12

### View Answer

9. What does the following recursive code do?

void my_recursive_function(int n) { if(n == 0) return; my_recursive_function(n-1); printf("%d ",n); } int main() { my_recursive_function(10); return 0; }

a) Prints the numbers from 10 to 1

b) Prints the numbers from 10 to 0

c) Prints the numbers from 1 to 10

d) Prints the numbers from 0 to 10

### View Answer

10. Which of the following statements is true?

a) Recursion is always better than iteration

b) Recursion uses more memory compared to iteration

c) Recursion uses less memory compared to iteration

d) Iteration is always better and simpler than recursion

### View Answer

11. What will be the output of the following code?

int cnt=0; void my_recursive_function(int n) { if(n == 0) return; cnt++; my_recursive_function(n/10); } int main() { my_recursive_function(123456789); printf("%d",cnt); return 0; }

a) 123456789

b) 10

c) 0

d) 9

### View Answer

12. What will be the output of the following code?

void my_recursive_function(int n) { if(n == 0) { printf("False"); return; } if(n == 1) { printf("True"); return; } if(n%2==0) my_recursive_function(n/2); else { printf("False"); return; } } int main() { my_recursive_function(100); return 0; }

a) True

b) False

### View Answer

13. What is the output of the following code?

int cnt = 0; void my_recursive_function(char *s, int i) { if(s[i] == ' ') return; if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') cnt++; my_recursive_function(s,i+1); } int main() { my_recursive_function("thisisrecursion",0); printf("%d",cnt); return 0; }

a) 6

b) 9

c) 5

d) 10

### View Answer

14. What is the output of the following code?

void my_recursive_function(int *arr, int val, int idx, int len) { if(idx == len) { printf("-1"); return ; } if(arr[idx] == val) { printf("%d",idx); return; } my_recursive_function(arr,val,idx+1,len); } int main() { int array[10] = {7, 6, 4, 3, 2, 1, 9, 5, 0, 8}; int value = 2; int len = 10; my_recursive_function(array, value, 0, len); return 0; }

a) 3

b) 4

c) 5

d) 6

### View Answer

## Set 5

1. What is the special property of red-black trees and what root should always be?

a) a color which is either red or black and root should always be black color only

b) height of the tree

c) pointer to next node

d) a color which is either green or black

### View Answer

2. Why do we impose restrictions like

. root property is black

. every leaf is black

. children of red node are black

. all leaves have same black

a) to get logarithm time complexity

b) to get linear time complexity

c) to get exponential time complexity

d) to get constant time complexity

### View Answer

3. Cosider the below formations of red-black tree.

All the above formations are incorrect for it to be a redblack tree. then what may be the correct order?

a) 50-black root, 18-red left subtree, 100-red right subtree

b) 50-red root, 18-red left subtree, 100-red right subtree

c) 50-black root, 18-black left subtree, 100-red right subtree

d) 50-black root, 18-red left subtree, 100-black right subtree

### View Answer

4. What are the operations that could be performed in O(logn) time complexity by red-black tree?

a) insertion, deletion, finding predecessor, successor

b) only insertion

c) only finding predecessor, successor

d) for sorting

### View Answer

5. Which of the following is an application of Red-black trees and why?

a) used to store strings efficiently

b) used to store integers efficiently

c) can be used in process schedulers, maps, sets

d) for efficient sorting

### View Answer

6. When it would be optimal to prefer Red-black trees over AVL trees?

a) when there are more insertions or deletions

b) when more search is needed

c) when tree must be balanced

d) when log(nodes) time complexity is needed

### View Answer

7. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

a) no they are not preferred

b) because of resizing issues of hash table and better ordering in redblack trees

c) because they can be implemented using trees

d) because they are balanced

### View Answer

8. How can you save memory when storing color information in Red-Black tree?

a) using least significant bit of one of the pointers in the node for color information

b) using another array with colors of each node

c) storing color information in the node structure

d) using negative and positive numbering

### View Answer

9. When to choose Red-Black tree, AVL tree and B-trees?

a) many inserts, many searches and when managing more items respectively

b) many searches, when managing more items respectively and many inserts respectively

c) sorting, sorting and retrieval respectively

d) retrieval, sorting and retrieval respectively

### View Answer

10. What is the below pseudo code trying to do, where pt is a node pointer and root pointer

redblack(Node root, Node pt) : if (root == NULL) return pt if (pt.data < root.data) { root.left = redblack(root.left, pt); root.left.parent = root } else if (pt.data > root.data) { root.right = redblackt(root.right, pt) root.right.parent = root } return root

a) insert a new node

b) delete a node

c) search a node

d) count the number of nodes