Data Structure Questions and Answers – Binomial and Fibonacci Heap

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Binomial and Fibonacci Heap”.

1. Which of these operations have same complexities?
A) Insertion, find_min
B) Find_min, union
C) Union, Insertion
D) Deletion, Find _max

Explanation: The find min and find max operations can be performed in O(1) with proper connection list implementation, while the rest takes O(logn) time.

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

Explanation: The overall difficulty of addition, combining, and deleting is in the order of O((a+b)logn) for Fibonacci.

3. 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

Explanation: Since each node can be viewed as a single-node tree, the maximum subtree in the heap is equal to the number of nodes in the heap.

4. 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

Explanation: Union takes O(1) time for a fibonacci heap addition, while remaining takes O(logn) time.

5. 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

Explanation: Since min[H] must contain one with the smallest value, the key characteristics of a fibonacci heap are violated.

6. 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

Explanation: When two trees are joined, the resultant’s order is increased by at least one.

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

Explanation: The main purpose of a binomial heap is to effectively combine two separate heaps.

8. The number of trees in a binomial heap with n nodes is
A) logn
B) n
C) nlogn
D) n/2

Explanation: In a binomial heap, there is a binomial tree at each depth.

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

Explanation: The binomial tree that is used to create the binomial heap follows the min heap property.

10. 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

Explanation: The root value of a binomial heap is less than the value of both child nodes. As a result, the given function of merging two heaps is right.

11. 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

Explanation: By examining the composition of a binomial heap, this can be easily checked.

12. Time taken in decreasing the node value in a binomial heap is
a) O(n)
b) O(1)
c) O(logn)
d) O(nlogn)

Explanation: When a node’s value is reduced, the min property can be violated. As a result, the worth of the parent and child will be exchanged, reaching the maximum height of the heap.

13. 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
Explanation: The function returns the heap Array’s minimum value, which is equal to the heap’s root value.

A Fibonacci heap is a data structure made up of heap-ordered trees that is used for priority queue operations. Many other priority queue data structures, such as the binary heap and binomial heap, have a longer amortised running time. Fibonacci heaps were invented by Michael L. Fredman and Robert E. Tarjan in 1984 and published in a scientific journal in 1987. Fibonacci heaps get their name from the Fibonacci numbers, which are used to calculate their running time.

Leave a Reply

Your email address will not be published. Required fields are marked *