Data Structure Questions and Answers – Binomial and Fibonacci Heap

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses 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
View Answer

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

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

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
View Answer

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
View Answer

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)
View Answer

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
View Answer

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

9. The Statement “Fibonacci heap has better amortized running time in compare to a binomial heap”.
a) True
b) False
View Answer

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
View Answer

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
View Answer

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
View Answer

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
View Answer

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]