Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Binomial and Fibonacci Heap

1 - Question

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

Answer: a
Explanation: The main use of binomial heap is to unify two different heap efficiently.




2 - Question

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

View Answer

Answer: a
Explanation: At each depth there is a binomial tree in a binomial heap.




3 - Question

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

View Answer

Answer: b
Explanation: Binomial tree used in making binomial heap follows min heap property.




4 - Question

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

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

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

Answer: b
Explanation: This could be easily verified by looking at the structure of a binomial heap.




6 - Question

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

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

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

Answer: c
Explanation: The function return minimum value in the heap_Array which is equal to the root value of the heap.




8 - Question

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

View Answer

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

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

View Answer

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

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

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

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

Answer: a
Explanation: For a fibonacci heap insertion, union take O(1) while remaining take O(logn) time.




12 - Question

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

Answer: c
Explanation: The main characterstics of a fibonacci heap is violated since min[H] must conatin one with smallest value.




13 - Question

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

Answer: a
Explanation: Union of two trees increase the order of the resultant by atmost value 1.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners