# Multiple choice question for engineering

## Set 1

1. The main distinguishable characterstic of a binomial heap from a binary heap is that

a) it allows union operations very efficiently

b) it does not allow union operations that could easily be implemented in binary heap

c) the heap structure is not similar to complete binary tree

d) the location of child node is not fixed i.e child nodes could be at level (h-2) or (h-3), where h is height of heap and h>4

### View Answer

2. The number of trees in a binomial heap with n nodes is

a) logn

b) n

c) nlogn

d) n/2

### View Answer

3. In a binomial heap the root value is greater than left child and less than right child.

a) True

b) False

### View Answer

4. Given the pseudo code, state whether the function for merging of two heap is correct or not?

mergeTree(p,q) if p.root.value <= q.root.value return p.addTree(q) else return q.addTree(p)

a) True

b) False

### View Answer

5. What is order of resultant heap after merging two tree of order k?

a) 2*k

b) k+1

c) k*k

d) k+logk

### View Answer

6. Time taken in decreasing the node value in a binomial heap is

a) O(n)

b) O(1)

c) O(logn)

d) O(nlogn)

### View Answer

7. What does this pseudo_code return ?

int myfun(heap_arr[]) { int mini=INF; for(int i=0;i<tot_node;i++) mini=min(mini,heap_arr) return mini; }

a) Last added element to heap

b) First element added to heap

c) Root of the heap

d) Leftmost node of the heap

### View Answer

8. Which of these operations have same complexities?

a) Insertion, find_min

b) Find_min, union

c) Union, Insertion

d) Deletion, Find _max

### View Answer

9. The Statement “Fibonacci heap has better amortized running time in compare to a binomial heap” Choose the correct option:

a) True

b) False

### View Answer

10. Given a heap of n nodes.The maximum number of tree for building the heap is.

a) n

b) n-1

c) n/2

d) logn

### View Answer

11. Choose the option with function having same complexity for a fibonacci heap.

a) Insertion, Union

b) Insertion, Deletion

c) extract_min, insertion

d) Union, delete

### View Answer

12. What is wrong with the following code of insertion in fibonacci heap.

Choose the correct option

FIB-INSERT(H, x) degree[x]= 0 p[x]= NIL child[x] =NIL left[x] =x right[x] =x mark[x] =FALSE concatenate the root list containing x with root list H if min[H] = NIL or key[x] > key[min[H]] then min[H]= x n[H]= n[H] + 1

a) Line -11

b) Line -3

c) Line 9

d) Line 7

### View Answer

13. What will be the order of new heap created after union of heap H1 and H2 when created by the following code.Initially both are of the order n.

FIB_UNION(H1,H2) { H =MAKE_HEAP() min[H]= min[H1] concatenate the root list of H2 with the root list of H if (min[H1] = NIL) or (min[H2]!= NIL and min[H2] < min[H1]) then min[H] = min[H2] n[H]= n[H1] + n[H2] free the objects H1 and H2 return H }

a) n+1

b) n+n/2

c) nlogn

d) 2*n

### View Answer

## Set 2

1. What is a bit array?

a) Data structure for representing arrays of records

b) Data structure that compactly stores bits

c) An array in which most of the elements have the same value

d) None of the mentioned

### View Answer

2. Which of the following bitwise operations will you use to set a particular bit to 1?

a) OR

b) AND

c) XOR

d) NOR

### View Answer

3. Which of the following bitwise operations will you use to set a particular bit to 0?

a) OR

b) AND

c) XOR

d) NAND

### View Answer

4. Which of the following bitwise operations will you use to toggle a particular bit?

a) OR

b) AND

c) XOR

d) NOT

### View Answer

5. Which of the following is an advantage of bit array?

a) Exploit bit level parallelism

b) Maximal use of data cache

c) Can be stored and manipulated in the register set for long periods of time

d) All of the mentioned

### View Answer

6. Identify the disadvantages of bit array.

a) Without compression, they might become sparse

b) Accessing individual bits is expensive

c) Compressing bit array to byte/word array, the machine also has to support byte/word addressing

d) All of the mentioned

### View Answer

7. What are some of the applications of bit arrays?

a) Used by the Linux kernel

b) For the allocation of memory pages

c) Bloom filter

d) All of the mentioned

### View Answer

8. Which class in Java can be used to represent bit array?

a) BitSet

b) BitVector

c) BitArray

d) BitStream

### View Answer

## Set 3

1. Which of the following is the binary representation of 100?

a) 1010010

b) 1110000

c) 1100100

d) 1010101

### View Answer

^{6}+ 2

^{5}+ 2

^{2}= 1100100.

2. Consider the following iterative code used to convert a decimal number to its equivalent binary:

#include<stdio.h> void dec_to_bin(int n) { int arr[31],len = 0,i; if(n == 0) { arr[0] = 0; len = 1; } while(n != 0) { arr[len++] = n % 2; _______; } for(i=len-1; i>=0; i--) printf("%d",arr[i]); } int main() { int n = 10; dec_to_bin(n); return 0; }

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

a) n–

b) n /= 2

c) n /= 10

d) n++

### View Answer

3. What is the output of the following code?

#include<stdio.h> void dec_to_bin(int n) { int arr[31],len = 0,i; if(n == 0) { arr[0] = 0; len = 1; } while(n != 0) { arr[len++] = n % 2; n /= 2; } for(i=len-1; i>=0; i--) printf("%d",arr[i]); } int main() { int n = 63; dec_to_bin(n); return 0; }

a) 111111

b) 111011

c) 101101

d) 101010

### View Answer

4. What is the output of the following code?

#include<stdio.h> void dec_to_bin(int n) { int arr[31],len = 0,i; if(n == 0) { arr[0] = 0; len = 1; } while(n != 0) { arr[len++] = n % 2; n /= 2; } for(i=len-1; i>=0; i--) printf("%d",arr[i]); } int main() { int n = 0; dec_to_bin(n); return 0; }

a) 0

b) 1

c) Runtime error

d) Garbage value

### View Answer

5. What is the time complexity of the above code used to convert a decimal number to its binary equivalent?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(logn)

### View Answer

6. Consider the following recursive implementation used to convert a decimal number to its binary equivalent:

#include<stdio.h> int arr[31], len = 0; void recursive_dec_to_bin(int n) { if(n == 0 && len == 0) { arr[len++] = 0; return; } if(n == 0) return; __________; recursive_dec_to_bin(n/2); } int main() { int n = 100,i; recursive_dec_to_bin(n); for(i=len-1; i>=0; i--) printf("%d",arr[i]); return 0; }

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

a) arr[len] = n

b) arr[len] = n % 2

c) arr[len++] = n % 2

d) arr[len++] = n

### View Answer

7. Consider the following code:

#include<stdio.h> int arr[31], len = 0; void recursive_dec_to_bin(int n) { if(n == 0 && len == 0) { arr[len++] = 0; return; } if(n == 0) return; arr[len++] = n % 2; recursive_dec_to_bin(n/2); }

Which of the following lines is the base case for the above code?

a) if(n ==0 && len == 0)

b) if(n == 0)

c) both of the mentioned

d) none of the mentioned

### View Answer

8. What is the output of the following code?

a) -1100100

b) 1100100

c) 2’s complement of 1100100

d) Garbage value

### View Answer

9. What is the time complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(logn)

### View Answer

10. What is the space complexity of the recursive implementation used to convert a decimal number to its binary equivalent?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(logn)

### View Answer

11. What is the output of the following code?

a) 1110111

b) 1001111

c) 1101111

d) 1010111

### View Answer

12. How many times is the function recursive_dec_to_bin() called when the following code is executed?

a) 7

b) 8

c) 9

d) 10

### View Answer

## Set 4

1. What is a Cartesian tree?

a) a skip list in the form of tree

b) a tree which obeys cartesian product

c) a tree which obeys heap property and whose inorder traversal yields the given sequence

d) a tree which obeys heap property only

### View Answer

2. Is the below tree representation of 50,100,400,300,280 correct way to represent cartesian tree?

a) true

b) false

### View Answer

3. Which of the below statements are true

i.Cartesian tree is not a height balanced tree

ii.Cartesian tree of a sequence of unique numbers can be unique generated

a) both statements are true

b) only i. is true

c) only ii. is true

d) both are untrue

### View Answer

4. What is the speciality of cartesian sorting?

a) it sorts partially sorted set of data quickly

b) it considers cartesian product of elements

c) it sorts elements in less than O(logn)

d) it is a self balancing tree

### View Answer

5. Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?

a) use any tie-breaking rule between repeated elements

b) cartesian tree is impossible when repetitions are present

c) construct a max heap in such cases

d) construct a min heap in such cases

### View Answer

6. After applying the below operations on a input sequence, what happens?

i. construct a cartesian tree for input sequence

ii. put the root element of above tree in a priority queue

iii. if( priority queue is not empty) then

.search and delete minimum value in priority queue

.add that to output

.add cartesian tree children of above node to priority queue

a) constructs a cartesian tree

b) sorts the input sequence

c) does nothing

d) produces some random output

### View Answer

7. Cartesian trees are most suitable for?

a) searching

b) finding nth element

c) minimum range query and lowest common ancestors

d) self balancing a tree

### View Answer

8. A treap is a cartesian tree with

a) additional value, which is a priority value to the key generated randomly

b) additional value, which is a priority value to the key generated sequentially

c) additional heap rule

d) additional operations like remove a range of elements

### View Answer

9. Cartesian trees solve range minimum query problem in constant time

a) true

b) false

### View Answer

10. Consider below sequences

How to achieve the above operation efficiently?

a) use linked lists

b) use avl trees

c) use red-black trees

d) use treaps (cartesian trees)

### View Answer

## Set 5

1. You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?

a) Dynamic programming

b) Recursion

c) Brute force

d) All of the mentioned

### View Answer

2. Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

a) 0

b) 1

c) 2

d) 3

### View Answer

3. Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

a) 0

b) 1

c) 2

d) 3

### View Answer

4. Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?

a) 0

b) 1

c) 2

d) 3

### View Answer

5. Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

a) n factorial

b) n square

c) n cube

d) nth catalan number

### View Answer

6. What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?

a) nth catalan number

b) n factorial

c) n cube

d) n square

### View Answer

7. Consider the following dynamic programming implementation of the boolean parenthesization problem:

int count_bool_parenthesization(char *sym, char *op) { int str_len = strlen(sym); int True[str_len][str_len],False[str_len][str_len]; int row,col,length,l; for(row = 0, col = 0; row < str_len; row++,col++) { if(sym[row] == 'T') { True[row][col] = 1; False[row][col] = 0; } else { True[row][col] = 0; False[row][col] = 1; } } for(length = 1; length < str_len; length++) { for(row = 0, col = length; col < str_len; col++, row++) { True[row][col] = 0; False[row][col] = 0; for(l = 0; l < length; l++) { int pos = row + l; int t_row_pos = True[row][pos] + False[row][pos]; int t_pos_col = True[pos+1][col] + False[pos+1][col]; if(op[pos] == '|') { _______________; } if(op[pos] == '&') { _______________; } if(op[pos] == '^') { _______________; } } } } return True[0][str_len-1]; }

Which of the following lines should be added to complete the “if(op[pos] == ‘|’)” part of the code?

a) False[row][col] += True[row][pos] * False[pos+1][col];

True[row][col] += t_row_pos * t_pos_col + False[row][pos] * False[pos+1][col];

b) False[row][col] += False[row][pos] * True[pos+1][col];

True[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

c) False[row][col] += True[row][pos] * True[pos+1][col];

True[row][col] += t_row_pos * t_pos_col + True[row][pos] * True[pos+1][col];

d) False[row][col] += False[row][pos] * False[pos+1][col];

True[row][col] += t_row_pos * t_pos_col – False[row][pos] * False[pos+1][col];

### View Answer

8. Which of the following lines should be added to complete the “if(op[k] == ‘&’)” part of the above code?

a) True[row][col] += False[row][pos] * False[pos+1][col];

False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

b) True[row][col] += True[row][pos] * True[pos+1][col];

False[row][col] += t_row_pos * t_pos_col – True[row][pos] * True[pos+1][col];

c) True[row][col] += True[row][pos] * False[pos+1][col];

False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

d) True[row][col] += False[row][pos] * True[pos+1][col];

False[row][col] += t_row_pos * t_pos_col – False[row][pos] * True[pos+1][col];

### View Answer

9. What is the time complexity of the above dynamic programming implementation of the boolean parenthesization problem?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

^{3}).

10. What is the space complexity of the above dynamic programming implementation of the boolean parenthesization problem?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n^{3})

### View Answer

^{2}).

11. What is the output of the following code?

#include<stdio.h> #include<string.h> int count_bool_parenthesization(char *sym, char *op) { int str_len = strlen(sym); int True[str_len][str_len],False[str_len][str_len]; int row,col,length,l; for(row = 0, col = 0; row < str_len; row++,col++) { if(sym[row] == 'T') { True[row][col] = 1; False[row][col] = 0; } else { True[row][col] = 0; False[row][col] = 1; } } for(length = 1; length < str_len; length++) { for(row = 0, col = length; col < str_len; col++, row++) { True[row][col] = 0; False[row][col] = 0; for(l = 0; l < length; l++) { int pos = row + l; int t_row_pos = True[row][pos] + False[row][pos]; int t_pos_col = True[pos+1][col] + False[pos+1][col]; if(op[pos] == '|') { False[row][col] += False[row][pos] * False[pos+1][col]; True[row][col] += t_row_pos * t_pos_col - False[row][pos] * False[pos+1][col]; } if(op[pos] == '&') { True[row][col] += True[row][pos] * True[pos+1][col]; False[row][col] += t_row_pos * t_pos_col - True[row][pos] * True[pos+1][col]; } if(op[pos] == '^') { True[row][col] += True[row][pos] * False[pos+1][col] + False[row][pos] * True[pos + 1][col]; False[row][col] += True[row][pos] * True[pos+1][col] + False[row][pos] * False[pos+1][col]; } } } } return True[0][str_len-1]; } int main() { char sym[] = "TTTT"; char op[] = "|^^"; int ans = count_bool_parenthesization(sym,op); printf("%d",ans); return 0; }

a) 1

b) 2

c) 3

d) 4