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

**Explanation: **

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

**Explanation: **

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

**Explanation:**

** 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
return p.addTree(q)
else
return q.addTree(p)

**a) True****b) False**

**Answer: a**

**Explanation: **

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

**Explanation:**

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

**Explanation:**

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

**Explanation:**

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

**Explanation:**

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

**a) True****b) False**

**Answer: a**

**Explanation:**

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

**Explanation:**

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

**Explanation:**

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

**Explanation:**

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

**Explanation:**

** Union of two trees increase the order of the resultant by atmost value 1.**

## 14. Who invented k-d trees?

**a) Arne Andersson****b) Jon Bentley****c) Jon Von Newmann****d) Rudolf Bayer**

**Answer: b**

**Explanation:**

** Jon Bentley found k-d trees. Rudolf Bayer found red black trees. Arne Andersson found AA- trees.**

## 15. What is the condition for an equivalence relation if two cities are related within a country?

**a) the two cities should have a one-way connection****b) the two cities should have a two-way connection****c) the two cities should be in different countries****d) no equivalence relation will exist between two cities**

**Answer: b**

**Explanation:**

** If the two towns are in the same country and have a two-way road connection between them, it satisfies equivalence property.**

## 16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.

**a) True****b) False**

**Answer: a**

**Explanation:**

** Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity**

- Top Stories About Minajhola Shiva Temple, Chandrapur, Rayagada [new]
- Avoid Top 5 Major Mistakes While Changing Careers
- Top 100+ Python Interview Questions and Answers For 2023
- Private Limited Company- Documents and Process of Registration
- TOP MCQs on Bit Array Data Structure with Answers
- TOP MCQs on Number of Jumps to Reach End-array Operation Data Structure with Answers
- TOP MCQs on Skip List Data Structure with Answers
- TOP MCQs on Binary Tree Properties Data Structure with Answers