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

Answer: a [Reason:] The main use of binomial heap is to unify two different heap efficiently.

2. The number of trees in a binomial heap with n nodes is
a) logn
b) n
c) nlogn
d) n/2

Answer: a [Reason:] At each depth there is a binomial tree in a binomial heap.

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

Answer: b [Reason:] Binomial tree used in making binomial heap follows min heap property.

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
else

a) True
b) False

Answer: a [Reason:] Binomial heap has a property that root value is less than both the child node’s value. So the given function of merging two different heap is correct.

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

Answer: b [Reason:] This could be easily verified by looking at the structure of a binomial heap.

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)

Answer: c [Reason:] Decreasing a node value may result in violating the min property. As a result be there would be exchange in the value of parent and child which at max goes up to height of the heap.

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

Answer: c [Reason:] The function return minimum value in the heap_Array which is equal to the root value of the heap.

8. Which of these operations have same complexities?
a) Insertion, find_min
b) Find_min, union
c) Union, Insertion
d) Deletion, Find _max

Answer: c [Reason:] With proper implementation using link list find_min and find_max operation can be done in O(1), while the remaining takes O(logn) time.

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

Answer: a [Reason:] Overall complexity of insertion, merging, deleting is in order of O((a+b)logn) For Fibonacci the complexity reduces to O(a+ blogn).

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

Answer: a [Reason:] Each node could be seen as a tree with only one node and as a result maximum subtree in the heap is equal to number of nodes in the heap.

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

Answer: a [Reason:] For a fibonacci heap insertion, union take O(1) while remaining take O(logn) time.

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

Answer: c [Reason:] The main characterstics of a fibonacci heap is violated since min[H] must conatin one with smallest value.

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

Answer: a [Reason:] Union of two trees increase the order of the resultant by atmost value 1.

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

Answer: b [Reason:] It compactly stores bits and exploits bit-level parallelism.

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

Answer: a [Reason:] 1 OR 1 = 1, 0 OR 1 = 1, any bit OR’ed with 1 gives 1.

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

Answer: b [Reason:] 1 AND 0 = 0, 0 AND 0 = 0, any bit AND with 0 gives 0.

4. Which of the following bitwise operations will you use to toggle a particular bit?
a) OR
b) AND
c) XOR
d) NOT

Answer: c [Reason:] 1 XOR 1 = 0, 0 XOR 1 = 1, note that NOT inverts all the bits, while XOR toggles only a specified bit.

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

Answer: d [Reason:] Because bit arrays are compact, they outperform many other data structures.

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

Answer: d [Reason:] Without compression, they become sparse in both time and space, also if random access is more common than sequential access, then they have to be compressed to byte/word array.

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

Answer: d [Reason:] Used in priority queues data structure in the Linux kernel, for allocation of memory pages, a bitmap is used.

8. Which class in Java can be used to represent bit array?
a) BitSet
b) BitVector
c) BitArray
d) BitStream

Answer: a [Reason:] The BitSet class creates a special type of array that can hold bit values.

## Set 3

1. Which of the following is the binary representation of 100?
a) 1010010
b) 1110000
c) 1100100
d) 1010101

Answer: c [Reason:] 100 = 64 + 32 + 4 = 26 + 25 + 22 = 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,len = 0,i;
if(n == 0)
{
arr = 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++

Answer: b [Reason:] The line “n /= 2” should be inserted to complete the above code.

3. What is the output of the following code?

```#include<stdio.h>
void dec_to_bin(int n)
{
int arr,len = 0,i;
if(n == 0)
{
arr = 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

Answer: a [Reason:] The program prints the binary equivalent of 63, which is 111111.

4. What is the output of the following code?

```#include<stdio.h>
void dec_to_bin(int n)
{
int arr,len = 0,i;
if(n == 0)
{
arr = 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

Answer: a [Reason:] The program prints the binary equivalent of 0, which is 0.

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(n2)
d) O(logn)

Answer: d [Reason:] The time complexity of the above code used to convert a decimal number to its binary equivalent is O(logn).

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

```#include<stdio.h>
int arr, 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

Answer: c [Reason:] The line “arr[len++] = n % 2” should be inserted to complete the above code.

7. Consider the following code:

```#include<stdio.h>
int arr, 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

Answer: c [Reason:] Both of the above mentioned lines are the base cases for the above code.

8. What is the output of the following code?

a) -1100100
b) 1100100
c) 2’s complement of 1100100
d) Garbage value

Answer: d [Reason:] The program doesn’t handle negative inputs and so produces a garbage value.

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(n2)
d) O(logn)

Answer: d [Reason:] The time complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

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(n2)
d) O(logn)

Answer: d [Reason:] The space complexity of the recursive implementation used to convert a decimal number to its binary equivalent is O(logn).

11. What is the output of the following code?

a) 1110111
b) 1001111
c) 1101111
d) 1010111

Answer: c [Reason:] The program prints the binary equivalent of 111, which is 1101111.

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

Answer: b [Reason:] The function recursive_dec_to_bin() is called 8 times when the above code is executed.

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

Answer: c [Reason:] A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence. refer below diagram question for clarity.

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

Answer: a [Reason:] A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence is called as a cartesian tree. as the above figure satisies both the properties. note that even min heap tree can be generated. the above is a max heap tree.

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

Answer: a [Reason:] A height balanced cartesian tree is not possible as seen in above question. also any time a unique sequnce possess a unique cartesian tree, this can be proven through induction.

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

Answer: a [Reason:] It can sort a set which requires only some sorting or displacements. for example consider 78, 79, 80, 82, 81, 83, In this only 81 and 82 must be swaped to make it a complete sorted set, in this case cartesian sort comes to the rescue.

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

Answer: a [Reason:] Consider any of the tie breaking rules, for example:-the element which appears first can be taken as small among the same elements and then apply cartesian tree rules.

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

Answer: b [Reason:] The above given steps are for sorting a cartesian tree. cartesian sort is benificial in case of partially sorted set of elements. a cartesian sort can be considered as a selection or heap sort maintaing a priority queue.

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

Answer: c [Reason:] In a cartesian tree minimum value can be found by finding lowest common ancestor for the extreme elements. consider 11,9,19,16 the lowest element is 9 and is a lowest common ancestor for 11 and 16. and by applying few techniques cartesian tree can be used to even find lowest common ancestors efficiently. these can be done in constant time. tree can be constructed in linear time (this is the most efficient time for any tree construction) and takes space as many elements are there.

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

Answer: a [Reason:] A cartesian tree, if feeded with a sorted sequence will generate a straight path (or in tree terminology a skew tree). moreover a cartesian tree basing on same values from the search keys doesnot work well. so a cartesian tree with priority value in addition to search key is called treap.

9. Cartesian trees solve range minimum query problem in constant time
a) true
b) false

Answer: a [Reason:] Range minmum query is finding the minimum element in a given subarray of a array. Constant time is achieved by storing the Cartesian trees for all the blocks in the array. Rmq’s are used in string matchings, computing lowest common ancestor and longest common prefix of a sring.

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)

Answer: d [Reason:] This can be solved efficiently using treap which is a modification of cartesian tree. an attribute like “boolean reverse” can me maintained with every node representing whether to reverse or not.

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

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

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

Answer: b [Reason:] The expression can only be parenthesized as T & (F | T), so that the output is T.

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

Answer: c [Reason:] The expression can be parenthesized as (T & F) ∧ T or T & (F ∧ T), so that the output is T.

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

Answer: b [Reason:] The expression can be parenthesized as (T | F) ∧ T, so that the output is F (false).

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

Answer: d [Reason:] The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.

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

Answer: a [Reason:] The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth catalan number.

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[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];

Answer: d [Reason:] The following lines should be added: 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];

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];

Answer: b [Reason:] The following lines should be added: 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];

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(n2)
d) O(n3)

Answer: d [Reason:] The time complexity of the above dynamic programming implementation is O(n3).

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(n2)
d) O(n3)

Answer: c [Reason:] The space complexity of the above dynamic programming implementation is O(n2).

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