/* */ Click to Join Live Class with Shankar sir Call 9798158723

Heap Data Structure MCQ

Q1.What is the location of parent node for any arbitary node i?
  1. (i/2) position
  2. (i+1)/ position
  3. floor(i/2) position
  4. ceil(i/2) position

Answer:- (C).
Explanations :For any node child nodes are located at either 2*i , 2*i +1 So the parent node could be found by taking the floor of the half of child node.
Q2.State the complexity of algorithm given below
int function(vector arr)

int len=arr.length();





return temp;
  1. o(n)
  2. O(logn)
  3. O(1)
  4. O(n logn)

Answer:- (C).
Explanations :Deletion in a min-heap is in O(1) time.
Q3.Time taken in decreasing the node value in a binomial heap is
  1. O(n)
  2. O(1)
  3. O(logn)
  4. O(nlogn)

Answer:- (C).
Explanations :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.
Q4.What does this pseudo_code return ?
int myfun(heap_arr[])


	int mini=INF;

	for(int i=0;i


	return mini;

  1. Last added element to heap
  2. First element added to heap
  3. Root of the heap
  4. Leftmost node of the heap

Answer:- (C).
Explanations :The function return minimum value in the heap_Array which is equal to the root value of the heap.
Q5.Heap can be used as¦
  1. Priority queue
  2. Stack
  3. A decreasing order array
  4. None of the mentioned

Answer:- (A).
Explanations :The property of heap that the value of root must be either greater or less than both of its children makes it work like a priority queue.
Q6. Does there exist a heap with seven distinct elements so that the In order traversal gives the element in sorted order.
  1. Yes
  2. No
  3. Both 1and2
  4. None of these

Answer:- (B).
Explanations :No, The inorder traversal will not give elements in sorted order. As heap is implemented as either min-heap or max-heap ,the root will be have highest or lowest value than remaining values of the nodes .So this traversal will not give a sorted list.
Q7. What is wrong with the following code of insertion in fibonacci heap. Choose the correct option

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
  1. Line -11
  2. Line -3
  3. Line -9
  4. Line -7

Answer:- (C).
Explanations :The main characteristics of a Fibonacci heap is violated since min[H] must contain one with smallest value.
Q8. 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.



	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

  1. n+1
  2. n+n/2
  3. nlogn
  4. 2*n

Answer:- (A).
Explanations :Union of two trees increase the order of the resultant by atmost value 1.
Q9.What is the complexity of adding an element to the heap.
  1. O(log n)
  2. O(h)
  3. O(log n) & O(h)
  4. None of the mentioned

Answer:- (C).
Explanations :The total possible operation in re locating the new location to a new element will be equal to height of the heap.
Q10.If we implement heap as min-heap, deleting root node (value 1)from the heap. What would be the value of root node after second iteration if leaf node (value 100) is chosen to replace the
  1. 2
  2. 100
  3. 17
  4. 3

Answer:- (A).
Explanations :As the root is deleted and node with value 100 is used as replaced one. There is a violation of property that root node must have value less than its children. So there will be shuffling of node with value 100 with node of value 2. And thus 2 becomes root. And it will remain to be at root after all the possible operations . So the value at root will be 2. If we implement heap as maximum heap, adding a new node of value 15 to the left most node of right subtree . What value will be at leaf nodes of the right subtree of the heap. correctchoice 15 and 1 25 and 1