# Heap Data Structure MCQ

1. In a max-heap, an element with the greatest key is always in which node?

a) Leaf node

b) First node of left subtree

c) root node

d) the First node of the right subtree

Answer: c

In a max-heap, an element with the greatest key is always in the root node. This is one of the properties of max-heap that the root node must have a key greater than its children.

2. Heap exhibits the property of a binary tree?

a) True

b) False

Answer: a

Heap exhibits the property of a binary tree because the leaf nodes are present at height h or h-1, which is a property of a complete binary tree.

3. What is the complexity of adding an element to the heap.

a) O(log n)

b) O(h)

c) O(log n) & O(h)

d) O(n)

Answer: c

The complexity of adding an element to the heap is O(log n) & O(h). The total possible operation in relocating the new location to a new element will be equal to the height of the heap.

4. The worst case complexity of deleting any arbitrary node value element from heap is __________

a) O(logn)

b) O(n)

c) O(nlogn)

d) O(n2)

Answer: a

The total possible operation in deleting the existing node and locating a new position to all its connected nodes will be equal to the height of the heap.

5. Heap can be used as _________

a) Priority queue

b) Stack

c) A decreasing order array

d) Normal Array

Answer: a

The property of the heap that the value of the root must be either greater or less than both of its children makes it work like a priority queue.

6. If we implement heap as min-heap, deleting the root node (value 1)from the heap. What would be the value of the root node after the second iteration if the leaf node (value 100) is chosen to replace the root at the start.

a) 2

b) 100

c) 17

d) 3

Answer: a

As the root is deleted and node with value 100 is used as replaced one. There is a violation of the property that the root node must have a value less than its children.

So there will be shuffling of a node with value 100 with a 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 the root will be 2.

7. If we implement heap as a maximum heap, adding a new node of value 15 to the leftmost node of the right subtree. What value will be at leaf nodes of the right subtree of the heap.

a) 15 and 1

b) 25 and 1

c) 3 and 1

d) 2 and 3

Answer: a

As 15 is less than 25 so there would be no violation and the node will remain at that position. So leaf nodes with values 15 and 1 will be at the position in the right sub-tree.

8. An array consists of n elements. We want to create a heap using the elements. The time complexity of building a heap will be in the order of

a) O(n*n*logn)

b) O(n*logn)

c) O(n*n)

d) O(n *logn *logn)

Answer: b

The total time taken will be N times the complexity of adding a single element to the heap. And adding a single element takes logN time, so That is equal to N*logN.

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

a) O(logn)

b) O(n)

c) O(1)

d) O(nlogn)

Answer: b

The space complexity of searching an element in heap is O (n). Heap consists of n elements and we need to compare every element. Here no addition or deletion of elements takes place. Hence space complexity is O (n).

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: d

O(n) is the best case complexity in building a heap. The best-case complexity occurs in bottom-up construction when we have a sortes array given.

3. 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 the general build function of any heap

d) It is used to search elements in any heap

Answer: a

Since in every condition we are comparing the current value is less than the parent of that node. So this is the build function of Max heap.

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

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 half of the child node.

6. Given an array of elements 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: a

Building a min-heap the result will a sorted array so the 1, 3, 4, 5, 7, 8, 9, and 10 is correct. If we change the implementation strategy 1, 4, 3, 8, 9, 5, 7, and 10 is also correct. (First, fill the right child rather than the left child first).

7. For the construction of a binary heap with a property that the parent node has a value less than the 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: c

The condition under while condition is wrong for a (min) binary heap The correct condition should be while(i!=0 && harr[parent(i)] > harr[i]). Otherwise the constructed heap will be a max-binary heap.

1. Choose the correct properties of the weak heap.

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

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

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

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

Answer: b

According to the weak heap properties, every right child of the node has a greater value than the parent node.

2. Left child of the parent node has a value lesser than the parent node.

a) True

b) False

Answer: b

Weak heap has no left child.

3. What is the other name for weak heap?

a) Min-heap

b) Max-heap

c) Relaxed -heap

d) Leonardo heap

Answer: c

A relaxed heap is just another name for a weak heap.

4. What is the worst-case time in searching for minimum value in a weak -heap?

a) O(log n)

b) O(n)

c) O(n logn)

d) O(1)

Answer: d

A weak heap is an array-based form that supports the operation of finding a minimum in O(1).

5. 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) n^{2}

Answer: b

The total comparisons in finding the smallest and largest elements are n + ((n+1)/2) – 2.

6. What is the complexity of the given function of insertion?

insert(int n) { if(buffer_size()< maxi_biffer_size()) buffer_aar[ind]==n; else move_to_heap(buffer,buffer+maxi_buffer_size()) }

a) O(logn)

b) amortized O(1)

c) O(n)

d) O (n*logn)

Answer: b

Use a buffer array to store a fixed number of elements when the buffer is full the content of the buffer is moved to the heap. As a result the complexity is amortized O(1).

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

The inorder traversal will not give elements in sorted order. As heap is implemented as either min-heap or max-heap, the root will have the highest or lowest value than the remaining values of the nodes. So this traversal will not give a sorted list.

8. 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: c

A complete binary tree is also a heap so by the property of binary tree the leaf nodes will be must at height h or h-1.

1. The main distinguishable characteristic 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 a binary heap

c) the heap structure is not similar to a complete binary tree

d) the location of the child node is not fixed i.e child nodes could be at level (h-2) or (h-3), where h is the height of the heap and h>4

Answer: a

The main distinguishable characteristic of a binomial heap from a binary heap is that it allows union operations very efficiently.

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

a) logn

b) n

c) nlogn

d) n/2

Answer: a

The number of trees in a binomial heap with n nodes is logn. At each depth, there is a binomial tree in a binomial heap.

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

a) True

b) False

Answer: b

The binomial tree used in making a binomial heap follows the min-heap property.

4. Given the pseudo-code, state whether the function for merging two heaps 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

Answer: a

Binomial heap has a property that the root value is less than both the child node’s value. So the given function of merging two different heaps is correct.

5. What is the order of the resultant heap after merging two trees of order k?

a) 2*k

b) k+1

c) k*k

d) k+logk

Answer: b

The order of the resultant heap after merging two trees of order k is k+1. This could be easily verified by looking at the structure of a binomial heap.

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)

Answer: c

Decreasing a node value may result in violating the min property. As a result, there would be an exchange in the value of parent and child which at max goes up to a height of the heap.

8. Which of these operations have the same complexities?

a) Insertion, find_min

b) Find_min, union

c) Union, Insertion

d) Deletion, Find _max

Answer: c

Union, Insertion operations have the same complexities. 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. The Statement “Fibonacci heap has better amortized running time in comparison to a binomial heap”.

a) True

b) False

Answer: a

The overall complexity of insertion, merging, and deleting is in order of O((a+b)logn) For Fibonacci the complexity reduces to O(a+ blogn).

10. Given a heap of n nodes. The maximum number of trees for building the heap is.

a) n

b) n-1

c) n/2

d) logn

Answer: a

Each node could be seen as a tree with only one node and as a result maximum subtree in the heap is equal to the number of nodes in the heap. So for a heap of n nodes. The maximum number of trees for building the heap is n.

11. Choose the option with a function having the same complexity as a Fibonacci heap.

a) Insertion, Union

b) Insertion, Deletion

c) extract_min, insertion

d) Union, delete

Answer: a

For a Fibonacci heap insertion, the union takes O(1) while the remaining takes O(logn) time.

12. What is wrong with the following code of insertion in a 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

Answer: c

The main characteristics of a Fibonacci heap is violated since min[H] must contain one with the smallest value.

13. What will be the order of new heap created after the 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

Answer: a

The union of two trees increases the order of the resultant by at most value 1.

1. d-heap is similar to that of a?

a) binary heap

b) Fibonacci heap

c) leftist heap

d) treap

Answer: a

A d-heap is similar to that of a binary heap except that binary heaps have two children and d-heaps have d children.

2. d-heap is shallower than a binary heap.

a) true

b) false

Answer: a

d-heap is much shallower than a binary heap with respect to the performance efficiency of insert and deletes operations.

3. Which operation cannot be directly performed in a d-heap?

a) insert

b) delete

c) find

d) create

Answer: c

Find operation in a d-heap cannot be performed as in other heaps. This is the main weakness of the d-heap.

4. Which operation is not efficiently performed in a d-heap?

a) insert

b) delete

c) find

d) merge

Answer: d

Merge operation is not efficiently performed in a d-heap. Unlike the find operation, which cannot be performed in a d-heap, the task of merging two d-heaps is very difficult.

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

The run-time efficiency of an insertion algorithm in a d-heap is found to be O(log N) where d is the number of children.

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

a) d

b) d-1

c) d+1

d) 1

Answer: b

Since, the delete-min operation is more expensive and the heap is shallow, the minimum of d elements can be found using d-1 comparisons.

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

a) 1

b) 2

c) 3

d) 4

Answer: b

There are two basic operations that can be performed in a d-heap. The two basic operations performed in a d-heap are insert and delete-min operations.

8. 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: c

The run-time efficiency of a delete-min algorithm using d-1 comparisons is mathematically found to be O(d logd N).

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

a) true

b) false

Answer: b

Multiplication and division for finding children and parents can be implemented in a d-heap but d should be a power of 2.

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

a) 1

b) 2

c) 3

d) 4

Answer: d

There are four secondary operations are performed in a d-heap. The other operations that can be performed in a d-heap are increase key, decrease key, buildheap, and delete.

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

a) stack

b) queue

c) linked list

d) priority queue

Answer: d

d-ary heap is a priority queue-based data structure that is a generalization of binary heaps.

1. What is the smallest element of the given minimum ternary heap?

a) 1

b) 10

c) 18

d) 20

Answer: a

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. The minimum ternary heap has the smallest element as its root node. The parent node is all either equal to or less than the children node in a minimum ternary heap.

2. What is the highest element of the given maximum ternary heap?

a) 31

b) 10

c) 18

d) 20

Answer: a

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. The maximum ternary heap has the highest element as its root node. The parent node is all either equal to or greater than the children node in a maximum ternary heap.

3. What is the child of the smallest element of the given minimum ternary heap?

a) 1

b) 10

c) 22

d) 24

Answer: b

The minimum ternary heap has the smallest element as its root node. The parent node is all either equal to or less than the children node in a minimum ternary heap. In the above minimum ternary heap, the smallest element is 1 and its children are 10, 18, and 20.

4. What are the siblings of the smallest element of the given maximum ternary heap?

a) 31

b) 12

c) 18

d) 22

Answer: c

The maximum ternary heap has the highest element as its root node. The parent node is all either equal to or greater than the children node in a maximum ternary heap. The smallest element in the maximum ternary heap is 10 and its siblings are 18, and 20.

5. What is the height of a given minimum ternary heap?

a) 1

b) 10

c) 2

d) 24

Answer: a

The minimum ternary heap has the smallest element as its root node. The parent node is all either equal to or less than the children node in a minimum ternary heap. Height is the total length from the root node to the leaf node. So the height of the minimum ternary heap is 1.

6. What is the ancestor of the leaf node in a given minimum ternary heap?

a) 1

b) 10

c) 18

d) 20

Answer: a

The minimum ternary heap has the smallest element as its root node. The parent node is all either equal to or less than the children node in a minimum ternary heap. Ancestor is the node falling on the path from that node to the root node. So here ancestor of all leaf nodes is 1.

7. Which property should the ternary heap hold for execution?

a) Associative

b) Commutative

c) Tree

d) Heap

Answer: d

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. So, it should hold all the properties of the Heap that is all the levels of the heap has to be filled from left to right.

8. Should leave in ternary heap be distributed from left to right.

a) True

b) False

Answer: a

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. So, it should hold all the properties of the Heap that is all the levels of the heap has to be filled from left to right.

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

a) Heapify

b) Hashing

c) Linking

d) Merging

Answer: a

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. So, the process of building a ternary heap is known as Heapify.

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

a) Array

b) Hash

c) Priority Queue

d) Priority Stack

Answer: c

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. It is a priority queue type of data structure that follows all the properties of the heap.

11. Is the priority queue abstract data type.

a) True

b) False

Answer: a

A priority queue is an abstract data type. It is also the extension of the Queue data structure where all the elements have been assigned some priority and on the basis of this priority, the elements are dequeued from the structure.

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

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. So, it follows all the properties of the heap. Therefore, all the nodes in the ternary heap have 3 nodes.

13. Who invented the d-ary heap?

a) Carl Rick

b) Alan Turing

c) Donald Johnson

d) Euclid

Answer: c

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. The d-ary heap was invented by Donald Johnson in the year 1975.

1. 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: a

In order to insert a new item in a ternary heap data structure having n elements, the heap has great efficiency for inserting them. So the time complexity for the worst case is found to be O (log n/ log 3).

2. Is decreased priority operation performed more quickly in a ternary heap with respect to the binary heap.

a) True

b) False

Answer: a

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. Due to the swapping process, the decreased priority operation performs more quickly in a ternary heap.

3. What is the time complexity for decreasing the 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: a

In order to decrease the priority of an item in a ternary heap data structure having n elements, the heap has great efficiency for decreasing them. So the time complexity for the worst case is found to be O (log n/ log 3). This is due to the upwards swapping process.

4. What is the time complexity for increasing the 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: a

In order to increase the priority of an item in a ternary heap data structure having n elements, it performs upwards swapping. So the time complexity for the worst case is found to be O (log n/ log 3).

5. What is the time complexity for deleting the 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: b

In order to delete a root key in a ternary heap data structure having n elements, it performs downward swapping. So the time complexity for the worst case is found to be O (3log n/ log 3).

6. What is the time complexity for increasing the 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: b

In order to the increasing the priority of key in a minimum ternary heap data structure having n elements, it performs downward swapping. So the time complexity for the worst case is found to be O (3log n/ log 3).

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

a) O (log n/ log 3)

b) O (3log n/ log 3)

c) O (n)

d) O (1)

Answer: b

In order to decrease the priority of key in a maximum ternary heap data structure having n elements, it performs downward swapping. So the time complexity for the worst case is found to be O (3log n/ log 3).

8. Do ternary heap has better memory cache behavior than binary heap.

a) True

b) False

Answer: a

Ternary heap is a type of data structure in the field of computer science. It is a part of the Heap data structure family. Due to the swapping process, they have better memory cache behavior.

9. What is the time complexity for creating a ternary heap using swapping?

a) O (log n/ log 3)

b) O (n!)

c) O (n)

d) O (1)

Answer: c

Ternary Heap can be formed by two swapping operations. Therefore, the time complexity for creating a ternary heap using two swapping operations is found to be O (n).

10. Which of the following is the application of minimum ternary heap?

a) Prim’s Algorithm

b) Euclid’s Algorithm

c) Eight Queen Puzzle

d) Tree

Answer: a

When working on the graph in the computer science field, Prim’s Algorithm for spanning trees uses a minimum ternary heap as there are delete operations equal to a number of edges and decrease priority operations equal to the number of vertices associated with the graph.

1. What is the reason for the efficiency of a pairing heap?

a) simplicity

b) time-efficient

c) space-efficient

d) advanced

Answer: a

The reason for the simplicity of a pairing heap is its simplicity as it is simpler and outperforms other heap structures.

2. How is a pairing heap represented?

a) binary tree

b) Fibonacci tree

c) heap ordered tree

d) treap

Answer: c

A pairing heap is represented as a heap-ordered tree and the analysis of the pairing heap is open.

3. The actual pairing heap implementation uses the right child and left child representation.

a) true

b) false

Answer: b

The actual pairing heap implementation uses a left child and right sibling representation since it follows heap order property.

4. Which node contains a pointer to its parent?

a) root node

b) right most child

c) left most child

d) left sibling

Answer: c

A node that is a leftmost node contains a pointer to its parent, otherwise, the node is a right sibling.

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

The run-time efficiency of an insertion algorithm in a pairing heap is mathematically found to be O(N).

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

a) merge

b) deletion

c) insertion

d) swapping

Answer: a

The basic operation performed in a pairing heap is merging. Insertion is also done by merging.

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

a) c

b) c+1

c) c-1

d) 1

Answer: c

If there are c children of the root, then the c-1 merges procedure is required to reassemble the pairing heap.

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

a) binary heap

b) d-heap

c) treap

d) pairing heap

Answer: d

Pairing heap is the best choice for complex applications because it is simple and better than the others.

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

a) splay tree

b) treap

c) red-black tree

d) AVL tree

Answer: a

The pairing heaps insertion, deletion, and search time complexity were initially inspired by that of splay trees.

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

a) True

b) False

Answer: b

The heap ordering property requires that all the root elements of the subtrees in the list are not smaller than the root element of the heap.

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

The amortized time efficiency for performing deletion of a minimum element is mathematically found to be O(log N).

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

Although the pairing heap is an efficient algorithm, it is worse than the Fibonacci heap. Also, the pairing heap is faster than the d-ary heap and binary heap.

1. Pointer manipulation is generally more time-consuming than multiplication and division.

a) true

b) false

Answer: a

The use of pointers for merging reduces the speed of other operations. This is the main drawback of all advanced data structures.

2. How many properties does the leftist heap support?

a) 1

b) 2

c) 3

d) 4

Answer: c

A leftist heap supports two properties- structural property, ordering property, and a heap order property.

3. In a leftist heap, the null path length of a null node is defined as?

a) 0

b) 1

c) null

d) -1

Answer: d

In a leftist heap tree, the null path length of a null node with no children is defined as -1.

4. How many nodes does a leftist tree with r nodes must have?

a) 2r

b) 2r-1

c) 2r

d) 2r-1

Answer: b

A leftist tree with r nodes on the right path is proved to have at least 2r-1 nodes. This theorem is proved by induction.

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

a) insert

b) merge

c) delete

d) swap

Answer: c

Performing insert and merge operations on the right path could destroy the leftist heap property. It is extremely easy to restore that property.

6. What is the fundamental operation on the leftist heap?

a) insertion

b) merging

c) deletion

d) swapping

Answer: b

The fundamental operation on leftist heaps is to merge. Insertion operation is a merge of a one-node heap with a larger heap.

7. A leftist heap is also said to be a binary heap.

a) true

b) false

Answer: a

A leftist heap has a structural property and an ordering property that is similar to that of a binary heap. Hence, the leftist heap is also said to be a binary heap.

8. 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: d

The efficiency of merge operations in the leftist heap is mathematically found to be O( log N) which is the same in binary heaps.

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

a) 1

b) -1

c) 0

d) null

Answer: c

The length of the shortest path from a node to a node without two children is defined as 0.

10. Why is this heap named leftist heap?

a) only left subtrees to exist

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

c) it is balanced

d) right trees are unbalanced

Answer: b

The heap is named as leftist heap because it tends to have deep left paths. It follows that the right path ought to be short.

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

a) left path

b) center path

c) the right path

d) root

Answer: c

All the operations are performed on the right path because the right paths are short. However, insertion and merges cannot be performed on the right path.

12. 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 the left subtree

c) violation at the right subtree

d) violation at the root

Answer: d

When two leftist heaps are merged, 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, the leftist property is violated at the root.

13. 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: b

While performing insertion via merge operation in a leftist heap, if the null path length is not updated, all null path lengths will be 0.

14. What is the time taken to delete a minimum element in a leftist heap?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(M log N)

Answer: c

The time taken to delete a minimum element in a leftist heap is mathematically found to be O(log N).

15. At what time can a leftist heap be built?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(M log N)

Answer: a

The mathematical calculation yields a result that, a leftist heap can be built in O(N) time by building a binary heap.

1. ___________ is a self-adjusting version of a leftist heap.

a) Rightist heap

b) Skew heap

c) d-heap

d) Binary heap

Answer: b

A skew heap is a self-adjusting version of a leftist heap and it is simpler to implement.

2. 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: a

The worst-case running time of all operations in a skew heap is mathematically found to be O(N).

3. What is the amortized cost per operation of a skew heap?

a) O(N)

b) O(N log N)

c) O(N2)

d) O(log N)

Answer: d

The amortized cost per operation of a skew heap is O(log N) since the worst-case analysis of the skew heap is O(N) and the splay tree is O(M log N).

4. The relationship of skew heaps to leftist heaps is analogous to that of?

a) Splay tree and AVL tree

b) Red-black tree and AVL tree

c) Binary tree and Splay tree

d) Binary tree and Red-black tree

Answer: a

The splay tree is a self-adjusting version of the AVL tree. Similarly, the skew heap is a self-adjusting version of the leftist heap.

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

a) intersection

b) difference

c) merging

d) sorting

Answer: c

The fundamental operation of skew heaps is merging. Hence, it is similar to that of a leftist heap.

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

Skew heaps support merging, insertion and deletion all effectively in O(log N) time per operation.

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

In skew heaps, a recursive implementation could fail because of a lack of stack space even though performance is acceptable.

8. 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: a

It is an open problem to determine precisely the expected right path length of both leftist and skew heaps and comparatively, the latter is difficult.

9. 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: a

The worst-case analysis for the naïve merge is an insertion in a right heavy tree. So, insertion takes O(N).

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

a) 1

b) 2

c) 3

d) 4

Answer: b

Two kinds of merge are available in skew heaps- naïve merge and skew merge.

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

a) true

b) false

Answer: b

One way of doing a skew merge is, to begin with, a naïve merge and then swap the left and right children of the tree.

12. What is the amortized efficiency of skew merge?

a) O(N)

b) O( log N)

c) O( N log N)

d) O(N2)

Answer: b

The amortized efficiency of a skew heap is mathematically found to be O( log N).

13. In skew heaps, certain constraints are to be met in order to perform swapping.

a) true

b) false

Answer: b

In skew heaps, swaps are unconditional. It is done with the exception that the largest of all nodes does not have its children swapped.

1. Descending priority queue can be implemented using ______

a) max heap

b) min-heap

c) min-max heap

d) trie

Answer: a

Descending priority queue arranges the elements based on their priority or value and allows removing the elements in descending order. So, it can be efficiently implemented using a max heap.

2. Min heap can be used to implement selection sort.

a) True

b) False

Answer: a

In min-heap, the insertion and deletion operation takes O(logn) time. Therefore, a selection sort with n insertions and n deletions can be implemented using a min-heap in O(nlogn) operations.

5. The ascending heap property is ___________

a) A[Parent(i)] =A[i]

b) A[Parent(i)] <= A[i]

c) A[Parent(i)] >= A[i]

d) A[Parent(i)] > 2 * A[i]

Answer: b

The ascending heap property is A[Parent(i)] <= A[i]. The min-heap is also known as ascending heap. Min heap of size n is an almost complete binary tree of n nodes such that the element at each node is greater than or equal to the element at its parent node.

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

In the min-heap, the root is the maximum element in the tree. So, locating it takes constant time, but deleting it takes logarithmic time. Because after deleting it, the root is replaced with the last element and then the procedure to maintain the min order is invoked.

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

8 10 12 25 14 17 array elements represent a binary min-heap.

8. 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: a

In the min-heap, the smallest is located at the root and the largest elements are located at the leaf nodes. So, all leaf nodes need to be checked to find the largest element. Thus, worst case time will be O (n).

9. Min heap is a complete binary tree.

a) True

b) False

Answer: a

A tree, in which all levels are fully filled, except possibly the last level, is called as the complete binary tree. And min-heap maintains shape property, so it is a complete binary tree. The shape property ensures that all levels in the min-heap are fully filled, except the last one, and, if the last level is not filled completely, then fill the elements from left to right.

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

b) 5 will be at the last level

c) 5 will be at the second level

d) 5 can be anywhere in the heap

Answer: b

In the max heap the greatest element is at the root and the smallest elements are at the last level. As 5 is the smallest input element, it will be at the last level.