Data Structure Multiple Choice Questions on “Binomial and Fibonacci Heap”.
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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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
Clarification: 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