YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS
Data Structure Questions and Answers-Binomial and Fibonacci Heap
Question 6 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
Time taken in decreasing the node value in a binomial heap is
O(n) | |
O(1) | |
O(logn) | |
O(nlogn) |
Question 6 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.
Question 7 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
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; }
Last added element to heap | |
First element added to heap | |
Root of the heap | |
Leftmost node of the heap |
Question 7 Explanation:
The function return minimum value in the heap....Array which is equal to the root value of the heap.
Question 8 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
Which of these operations have same complexities?
Insertion, find....min | |
Find....min, union | |
Union, Insertion | |
Deletion, Find ....max |
Question 8 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.
Question 9 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
The Statement "Fibonacci heap has better amortized running time in compare to a binomial heap".
True | |
False |
Question 9 Explanation:
Overall complexity of insertion, merging, deleting is in order of O((a+b)logn) For Fibonacci the complexity reduces to O(a+ blogn).
Question 10 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |
Given a heap of n nodes.The maximum number of tree for building the heap is.
n | |
n-1 | |
n/2 | |
logn |
Question 10 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.
There are 10 questions to complete.