Data Structure Questions and Answers-Binomial and Fibonacci Heap

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

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
A
O(n)
B
O(1)
C
O(logn)
D
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; 	}
A
Last added element to heap
B
First element added to heap
C
Root of the heap
D
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?
A
Insertion, find....min
B
Find....min, union
C
Union, Insertion
D
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".
A
True
B
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.
A
n
B
n-1
C
n/2
D
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.