500+ Heap (Data Structure) MCQs with FREE PDF

These Heap (Data Structure) MCQs contain questions and answers on heap, binary and weak heap, binomial and fibonacci heap, d ary heap, ternary heap, pairing and leftlist heap, skew heap, min and max heap. We have the best collection of Heap (Data Structure) MCQs and answer with FREE PDF. These Heap (Data Structure) MCQs will help you to prepare for any competitive exams like: BCA, MCA, GATE, GRE, IES, PSC, UGC NET, DOEACC Exams at all levels – you just have to practice regularly.

1. For construction of a binary heap with property that parent node has value less than child node. In reference to that which line is incorrect. Line indexed from 1.

1. add(int k)
2. {
3.     heap_size++;
4.     int i = heap_size - 1;
5.     harr[i] = k;
6.     while (i != 0 && harr[parent(i)] < harr[i])
7.     {
8.             swap(&harr[i], &harr[parent(i)]);
9.             i = parent(i);
10.    }
11. }

a) Line – 3

b) Line – 5

c) Line – 6

d) Line – 7

Answer: Line – 6

2. What is the best case complexity in building a heap?

a) O(nlogn)

b) O(n2)

c) O(n*longn *logn)

d) O(n)

Answer: O(n)

3. Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following are the correct sequences of elements after inserting all the elements in a min-heap?

a) 1,3,4,5,7,8,9,10

b) 1,4,3,9,8,5,7,10

c) 1,3,4,5,8,7,9,10

d) 1,3,7,4,8,5,9,10

Answer: 1,3,4,5,7,8,9,10

4. State the complexity of algorithm given below.

	int function(vector<int> arr)
	int len=arr.length();
	if(len==0)
	return;
	temp=arr[len-1];
	arr.pop_back();
	return temp;

a) o(n)

b) O(logn)

c) O(1)

d) O(n logn)

Answer: O(n logn)

5. What is the location of a parent node for any arbitary node i?

a) (i/2) position

b) (i+1)/ position

c) floor(i/2) position

d) ceil(i/2) position

Answer: floor(i/2) position

6. Given the code, choose the correct option that is consistent with the code. (Here A is the heap)

	build(A,i)
	left-> 2*i
	right->2*i +1
	temp- > i
	if(left<= heap_length[A] ans A[left] >A[temp])
	temp -> left
	if (right = heap_length[A] and A[right] > A[temp])
	temp->right
	if temp!= i
	swap(A[i],A[temp])
	build(A,temp)

a) It is the build function of max heap

b) It is the build function of min heap

c) It is general build function of any heap

d) It is used to search element in any heap

Answer: It is the build function of max heap

7. What is the space complexity of searching in a heap?

a) O(logn)

b) O(n)

c) O(1)

d) O(nlogn)

Answer: O(n)

8. Which of these operations have same complexities?

a) Insertion, find_min

b) Find_min, union

c) Union, Insertion

d) Deletion, Find _max

Answer: Union, Insertion

9. The Statement “Fibonacci heap has better amortized running time in compare to a binomial heap”.

a) True

b) False

Answer: True

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

Answer: n

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

Answer: Insertion, Union

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

Answer: it allows union operations very efficiently

13. The number of trees in a binomial heap with n nodes is

a) logn

b) n

c) nlogn

d) n/2

Answer: logn

14. In a binomial heap the root value is greater than left child and less than right child.

a) True

b) False

Answer: False

50+ Binary Heap MCQs with FREE PDF

15. What is the basic operation performed in a pairing heap?

a) merge

b) deletion

c) insertion

d) swapping

Answer: merge

16. If there are c children of the root, how many calls to the merge procedure is required to reassemble the heap?

a) c

b) c+1

c) c-1

d) 1

Answer: c-1

17. Which of the following methods is the best choice for complex applications?

a) binary heap

b) d-heap

c) treap

d) pairing heap

Answer: pairing heap

18. Pairing heaps time complexity was inspired by that of?

a) splay tree

b) treap

c) red-black tree

d) avl tree

Answer: splay tree

19. The roots of the elements of the subtrees are smaller than the root of the heap.

a) True

b) False

Answer: False

20. The amortized time efficiency for performing deletion of a minimum element is?

a) O(N)

b) O(log N)

c) O(N2)

d) O(M log N)

Answer: O(log N)

21. Out of the following given options, which is the fastest algorithm?

a) fibonacci heap

b) pairing heap

c) d-ary heap

d) binary heap

Answer: fibonacci heap

22. What is the run time efficiency of an insertion algorithm?

a) O(N)

b) O(log N)

c) O(N2)

d) O(M log N)

Answer: O(N)

50+ Pairing Heap MCQs with FREE PDF

23. The procedure FindMin() to find the minimum element and the procedure DeleteMin() to delete the minimum element in min heap take _________

a) logarithmic and linear time constant respectively

b) constant and linear time respectively

c) constant and quadratic time respectively

d) constant and logarithmic time respectively

Answer: constant and logarithmic time respectively

24. Which one of the following array elements represents a binary min heap?

a) 12 10 8 25 14 17

b) 8 10 12 25 14 17

c) 25 17 14 12 10 8

d) 14 17 25 10 12 8

Answer: 8 10 12 25 14 17

25. In a binary min heap containing n elements, the largest element can be found in __________ time.

a) O(n)

b) O(nlogn)

c) O(logn)

d) O(1)

Answer: O(n)

26. Min heap is a complete binary tree.

a) True

b) False

Answer: True

27. What will be the position of 5, when a max heap is constructed on the input elements 5, 70, 45, 7, 12, 15, 13, 65, 30, 25?

a) 5 will be at root

b) 5 will be at last level

c) 5 will be at second level

d) 5 can be anywhere in heap

Answer: 5 will be at last level

28. Descending priority queue can be implemented using ______

a) max heap

b) min heap

c) min-max heap

d) trie

Answer: max heap

50+ Min/Max Heap MCQs with FREE PDF

29. Which of the following operations does not destroy the leftist heap property?

a) insert

b) merge

c) delete

d) swap

Answer: delete

30. What is the fundamental operation on leftist heap?

a) insertion

b) merging

c) deletion

d) swapping

Answer: merging

31. What is the efficiency of merge used in leftist heaps?

a) O(N)

b) O(N log N)

c) O(M log N)

d) O(log N)

Answer: O(log N)

32. What is the node path length of a node with 0 or 1 child?

a) 1

b) -1

c) 0

d) null

Answer: 0

33. Why is this heap named leftist heap?

a) only left subtrees exist

b) the tree is biased to get deep down the left

c) it is balanced

d) right trees are unbalanced

Answer: the tree is biased to get deep down the left

34. In a leftist heap, all the operations should be performed on?

a) left path

b) centre path

c) right path

d) root

Answer: right path

35. What would be the result if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2?

a) merge occurs without violation

b) violation at left subtree

c) violation at right subtree

d) violation at the root

Answer: violation at the root

36. What happens if the null path length is not updated?

a) error occurs

b) all null path lengths will be 0

c) all null path lengths will be -1

d) all null path lengths will be 1

Answer: all null path lengths will be 0

50+ Leftlist Heap MCQs with FREE PDF

37. What is the fundamental operation performed in skew heaps?

a) intersection

b) difference

c) merging

d) sorting

Answer: merging

38. What is the time per operation of merging, insertion and deletion operations in a skew heap?

a) O(N)

b) O(log N)

c) O(N log N)

d) O(N2)

Answer: O(log N)

39. Why would a recursive implementation fail in skew heaps?

a) skew heaps are self adjusting

b) efficiency gets reduced

c) lack of stack space

d) time complexity

Answer: lack of stack space

40. Which of the following is difficult to determine the right path length?

a) Skew heaps

b) Binomial tree

c) Leftist heap

d) d-heap

Answer: Skew heaps

41. The worst case analysis for a naïve merge is given as?

a) O(N)

b) O( log N)

c) O( N log N)

d) O(N2)

Answer: O(N)

42. How many types of the merge are available in skew heaps?

a) 1

b) 2

c) 3

d) 4

Answer: 2

43. Naïve merge cannot be done in a skew merge.

a) true

b) false

Answer: false

44. What is the amortized efficiency of skew merge?

a) O(N)

b) O( log N)

c) O( N log N)

d) O(N2)

Answer: O( log N)

45. The worst case running time of all operations in a skew heap is given as?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(M log N)

Answer: O(N)

50+ Skew Heap MCQs with FREE PDF

46. What is the process of building a ternary heap called?

a) Heapify

b) Hashing

c) Linking

d) Merging

Answer: Heapify

47. Which type of data structure is a ternary heap?

a) Array

b) Hash

c) Priority Queue

d) Priority Stack

Answer: Priority Queue

48. What is a ternary heap?

a) An array with three elements

b) Linked list with three elements

c) Tree with three children

d) Heap with all nodes having three children

Answer: Heap with all nodes having three children

49. Who invented d-ary heap?

a) Carl Rick

b) Alan Turing

c) Donald Johnson

d) Euclid

Answer: Donald Johnson

50. What is the time complexity for inserting a new item in a ternary heap of n elements?

a) O (log n/ log 3)

b) O (n!)

c) O (n)

d) O (1)

Answer: O (log n/ log 3)

51. What is the time complexity for decreasing priority of key in a minimum ternary heap of n elements?

a) O (log n/ log 3)

b) O (n!)

c) O (n)

d) O (1)

Answer: O (log n/ log 3)

52. What is the time complexity for increasing priority of key in a maximum ternary heap of n elements?

a) O (log n/ log 3)

b) O (n!)

c) O (n)

d) O (1)

Answer: O (log n/ log 3)

53. What is the time complexity for deleting root key in a ternary heap of n elements?

a) O (log n/ log 3)

b) O (3log n/ log 3)

c) O (n)

d) O (1)

Answer: O (3log n/ log 3)

54. What is the time complexity for increasing priority of key in a minimum ternary heap of n elements?

a) O (log n/ log 3)

b) O (3log n/ log 3)

c) O (n)

d) O (1)

Answer: O (3log n/ log 3)

50+ Ternary Heap MCQs with FREE PDF

55. Which of these operations have same complexities?

a) Insertion, find_min

b) Find_min, union

c) Union, Insertion

d) Deletion, Find _max

Answer: Union, Insertion

56. The Statement “Fibonacci heap has better amortized running time in compare to a binomial heap”.

a) True

b) False

Answer: True

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

Answer: n

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

Answer: Insertion, Union

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

Answer: it allows union operations very efficiently

60. The number of trees in a binomial heap with n nodes is

a) logn

b) n

c) nlogn

d) n/2

Answer: logn

61. In a binomial heap the root value is greater than left child and less than right child.

a) True

b) False

Answer: False

50+ Binomial and Fibonacci Heap MCQs with FREE PDF

62. The total comparisons in finding both smallest and largest elements are

a) 2*n +2

b) n + ((n+1)/2) -2

c) n+logn

d) n2

Answer: n + ((n+1)/2) -2

63. Does there exist a heap with seven distinct elements so that the Inorder traversal gives the element in sorted order.

a) Yes

b) No

Answer: No

64. The leaf node for a heap of height h will be at which position.

a) h

b) h-1

c) h or h-1

d) h-2

Answer: h or h-1

65. Choose the correct properties of weak-heap.

a) Every node has value greater than the value of child node

b) Every right child of node has greater value than parent node

c) Every left child of node has greater value than parent node

d) Every left and right child of node has same value as parent node

Answer: Every right child of node has greater value than parent node

66. Left child of parent node has value lesser than the parent node.

a) True

b) False

Answer: False

67. What is the other name of weak heap?

a) Min-heap

b) Max-heap

c) Relaxed -heap

d) Leonardo heap

Answer: Relaxed -heap

50+ Weak Heap MCQs with FREE PDF

68. What is the fundamental operation performed in skew heaps?

a) intersection

b) difference

c) merging

d) sorting

Answer: merging

69. What is the time per operation of merging, insertion and deletion operations in a skew heap?

a) O(N)

b) O(log N)

c) O(N log N)

d) O(N2)

Answer: O(log N)

70. Why would a recursive implementation fail in skew heaps?

a) skew heaps are self adjusting

b) efficiency gets reduced

c) lack of stack space

d) time complexity

Answer: lack of stack space

71. Which of the following is difficult to determine the right path length?

a) Skew heaps

b) Binomial tree

c) Leftist heap

d) d-heap

Answer: Skew heaps

72. The worst case analysis for a naïve merge is given as?

a) O(N)

b) O( log N)

c) O( N log N)

d) O(N2)

Answer: O(N)

73. How many types of the merge are available in skew heaps?

a) 1

b) 2

c) 3

d) 4

Answer: 2

74. Naïve merge cannot be done in a skew merge.

a) true

b) false

Answer: false

75. What is the amortized efficiency of skew merge?

a) O(N)

b) O( log N)

c) O( N log N)

d) O(N2)

Answer: O( log N)

50+ Skew Heap MCQs with FREE PDF

76. What is the run time efficiency of an insertion algorithm in d-heap?

a) O(N)

b) O(log N)

c) O(logd N)

d) O(Nd)

Answer: O(logd N)

77. How many comparisons will occur while performing a delete-min operation?

a) d

b) d-1

c) d+1

d) 1

Answer: d-1

78. How many basic operations can be performed in a d-heap?

a) 1

b) 2

c) 3

d) 4

Answer: 2

79. What is the run time efficiency of delete-min operation?

a) O(log N)

b) O(logd N)

c) O(d logd N)

d) O(d)

Answer: O(d logd N)

80. Multiplication and division to find children and parents cannot be implemented in a d-heap.

a) true

b) false

Answer: false

81. How many secondary operations are performed in a d-heap?

a) 1

b) 2

c) 3

d) 4

Answer: 4

82. On which data structure is a d-ary heap based?

a) stack

b) queue

c) linked list

d) priority queue

Answer: priority queue

50+ D-ary Heap MCQs with FREE PDF

Heap (Data Structure) MCQs PDF Download

1000+ Data Structure MCQs

Abstract Data Types
Application of Stacks
Arrays Types
Types of Lists
Binary Trees
B Trees
Trees
Heap
Trie
Hash Tables
Graph

Comments