Question 1:
What is the main advantage of using a binary heap for implementing a priority queue?
A.
It provides efficient insertions and deletions.
B.
It maintains elements in sorted order.
C.
It allows quick search operations.
D.
It uses less memory.
Answer: _________
Question 2:
In a min-heap, what happens when you decrease the value of a node?
A.
The heap property is maintained by moving the node up the tree.
B.
The node is removed and the heap is restructured.
C.
The node is placed at the end of the heap.
D.
The heap property is maintained by moving the node down the tree.
Answer: _________
Question 3:
Which operation is used to extract the minimum element from a min-heap?
A.
Extract-Min
B.
Extract-Max
C.
Remove-Root
D.
Delete-Min
Answer: _________
Question 4:
What is the time complexity of extracting the maximum element from a max-heap?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 5:
How are heaps commonly used in algorithms?
A.
For implementing priority queues and heapsort.
B.
For managing hierarchical data.
C.
For balancing binary search trees.
D.
For efficient searching.
Answer: _________
Question 6:
In a binary heap, which of the following operations is O(log n) in time complexity?
A.
Insert
B.
Find minimum
C.
Delete minimum
D.
Both Insert and Delete minimum
Answer: _________
Question 7:
What is the main difference between a binary heap and a binary search tree?
A.
A binary heap does not maintain a sorted order while a binary search tree does.
B.
A binary heap maintains a sorted order while a binary search tree does not.
C.
Binary heaps are always balanced while binary search trees are not.
D.
Binary heaps have only one child per node, binary search trees have two.
Answer: _________
Question 8:
How do you restore the heap property after extracting the maximum element from a max-heap?
A.
By performing a heapify operation.
B.
By reordering the entire heap.
C.
By inserting a new maximum element.
D.
By balancing the tree manually.
Answer: _________
Question 9:
Which property does not apply to a min-heap?
A.
The root is the smallest element.
B.
Each parent node is less than or equal to its children.
C.
All levels of the heap are completely filled except possibly the last.
D.
The root is the largest element.
Answer: _________
Question 10:
What is the time complexity of decreasing a key value in a min-heap?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 11:
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: _________
Question 12:
Left child of parent node has value lesser than the parent node.
A.
True
B.
False
Answer: _________
Question 13:
What is the run time efficiency of an insertion algorithm in d-heap?
A.
O(N)
B.
O(log N)
C.
O(log d N)
D.
O(N d )
Answer: _________
Question 14:
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: _________
Question 15:
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.
A.
15 and 1
B.
25 and 1
C.
3 and 1
D.
2 and 3
Answer: _________
Question 16:
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 order of
A.
O(n*n*logn)
B.
O(n*logn)
C.
O(n*n)
D.
O(n *logn *logn)
Answer: _________
Question 17:
How is a pairing heap represented?
A.
binary tree
B.
fibonacci tree
C.
heap ordered tree
D.
treap
Answer: _________
Question 18:
What is the fundamental operation performed in skew heaps?
A.
intersection
B.
difference
C.
merging
D.
sorting
Answer: _________
Question 19:
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: _________
Question 20:
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: _________
Question 21:
What is the process of building a ternary heap called?
A.
Heapify
B.
Hashing
C.
Linking
D.
Merging
Answer: _________
Question 22:
Which operation is not efficiently performed in a d-heap?
A.
insert
B.
delete
C.
find
D.
merge
Answer: _________
Question 23:
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: _________
Question 24:
What is the worst case time in searching minimum value in weak -heap?
A.
O(log n)
B.
O(n)
C.
O(n logn)
D.
O(1)
Answer: _________
Question 25:
Pairing heaps time complexity was inspired by that of?
A.
splay tree
B.
treap
C.
red-black tree
D.
avl tree
Answer: _________
Question 26:
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: _________
Question 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: _________
Question 28:
What are the siblings of smallest element of the given maximum ternary heap?
A.
31
B.
12
C.
18
D.
22
Answer: _________
Question 29:
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: _________
Question 30:
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: _________
Question 31:
How many secondary operations are performed in a d-heap?
A.
1
B.
2
C.
3
D.
4
Answer: _________
Question 32:
The number of trees in a binomial heap with n nodes is
A.
logn
B.
n
C.
nlogn
D.
n/2
Answer: _________
Question 33:
The worst case analysis for a naive merge is given as?
A.
O(N)
B.
O( log N)
C.
O( N log N)
D.
O(N 2 )
Answer: _________
Question 34:
What is the run time efficiency of delete-min operation?
A.
O(log N)
B.
O(log d N)
C.
O(d log d N)
D.
O(d)
Answer: _________
Question 35:
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: _________
Question 36:
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: _________
Question 37:
What is the result of an inorder traversal of a binary heap?
A.
The elements are not in any specific order.
B.
The elements are sorted in ascending order.
C.
The elements are sorted in descending order.
D.
The elements follow the heap property.
Answer: _________
Question 38:
Which of the following is not a type of heap?
A.
Binary heap
B.
Fibonacci heap
C.
Binomial heap
D.
AVL heap
Answer: _________
Question 39:
What is the time complexity of building a binary heap using a sequence of insertions?
A.
O(log n)
B.
O(n log n)
C.
O(n)
D.
O(n 2 )
Answer: _________
Question 40:
What is the typical use case for a min-heap in algorithms?
A.
To find the minimum element efficiently.
B.
To find the maximum element efficiently.
C.
To sort elements in descending order.
D.
To balance binary search trees.
Answer: _________
Question 41:
In a binary heap, how do you locate the right child of a node at index i?
A.
2 * i + 2
B.
2 * i + 1
C.
(i - 1) / 2
D.
2 * i
Answer: _________
Question 42:
Which property is common to both max-heaps and min-heaps?
A.
They both maintain a complete binary tree.
B.
They both ensure a sorted order of elements.
C.
They both allow easy insertion and deletion.
D.
They both balance themselves automatically.
Answer: _________
Question 43:
What is the typical time complexity of decreasing a key in a min-heap?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 44:
How is the structure of a binary heap affected when you increase the size of the heap?
A.
The heap grows by adding nodes to the end.
B.
The heap automatically rebalances itself.
C.
The heap elements are sorted.
D.
The heap size must be manually adjusted.
Answer: _________
Question 45:
In a binary heap stored as an array, what is the index of the parent node for the node at index i?
A.
(i - 1) / 2
B.
(i + 1) / 2
C.
(i + 2) / 2
D.
(i - 2) / 2
Answer: _________
Question 46:
What is the time complexity of extracting the minimum element from a min-heap?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 47:
In a binary heap, what is the typical time complexity of deleting an arbitrary element?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 48:
What is the primary use of heaps in graph algorithms?
A.
For implementing priority queues.
B.
For managing hierarchical data.
C.
For sorting elements.
D.
For balancing search trees.
Answer: _________
Question 49:
How is the parent node index computed in a zero-based indexed binary heap array?
A.
(i - 1) / 2
B.
(i + 1) / 2
C.
(i - 1) / 2 if i is even, else (i - 1) / 2
D.
(i - 1) / 2 for i > 0
Answer: _________
Question 50:
What happens if you increase the value of a node in a max-heap?
A.
The heap property is restored by moving the node down.
B.
The node is removed, and a new node is added.
C.
The heap property is restored by moving the node up.
D.
The heap becomes unbalanced.
Answer: _________
Question 51:
Which of the following operations is not directly supported by a binary heap?
A.
Searching for an arbitrary element
B.
Inserting an element
C.
Extracting the maximum/minimum
D.
Building a heap
Answer: _________
Question 52:
In a binary heap represented as an array, what is the index of the left child of the node at index i?
A.
2 * i + 1
B.
2 * i
C.
2 * i + 2
D.
2 * i - 1
Answer: _________
Question 53:
What is the space complexity of a binary heap when stored in an array?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 54:
Which operation involves moving a node to maintain the heap property after insertion in a binary heap?
A.
Bubble-up or Percolate-up
B.
Bubble-down or Percolate-down
C.
Heapify
D.
Restructure
Answer: _________
Question 55:
In a max-heap, what is the time complexity to find the second largest element?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 56:
What kind of binary heap is used to efficiently support priority queues with the smallest element at the root?
A.
Min-heap
B.
Max-heap
C.
Fibonacci heap
D.
Binomial heap
Answer: _________
Question 57:
The procedure given below is used to maintain min-order in the min heap. Find out the missing statements, represented as X. procedure TrickleDownMin(i)
if A[i] has children then
m := index of smallest of the children
or grandchildren (if any) of A[i]
if A[m] is a grandchild of A[i] then
if A[m] < A[i] then
swap A[i] and A[m]
X: _______________________
____________________
endif
TrickleDownMin(m)
endif
else //{A[m] is a child of A[i]}
if A[m] << A[i] then
swap A[i] and A[m]
endif
endif
A.
if A[m] > A[parent(m)] then swap A[m] and A[parent(m)]
B.
if A[m] > A[parent(m)] then swap A[i] and A[parent(m)]
C.
if A[m] < A[parent(m)] then swap A[m] and A[parent(m)]
D.
if A[m] > A[parent(m)] then swap A[i] and A[parent(m)]
Answer: _________
Question 58:
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: _________
Question 59:
What is the space complexity of searching in a heap?
A.
O(logn)
B.
O(n)
C.
O(1)
D.
O(nlogn)
Answer: _________
Question 60:
Which of the following operations does not destroy the leftist heap property?
A.
insert
B.
merge
C.
delete
D.
swap
Answer: _________
Question 61:
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: _________
Question 62:
How many basic operations can be performed in a d-heap?
A.
1
B.
2
C.
3
D.
4
Answer: _________
Question 63:
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: _________
Question 64:
What is the reason for the efficiency of a pairing heap?
A.
simplicity
B.
time-efficient
C.
space-efficient
D.
advanced
Answer: _________
Question 65:
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: _________
Question 66:
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
Answer: _________
Question 67:
What operation is performed to convert a binary heap into a sorted array?
A.
Heapsort
B.
Merge sort
C.
Quick sort
D.
Insertion sort
Answer: _________
Question 68:
In which situation would you prefer using a Fibonacci heap over a binary heap?
A.
When frequent decrease-key operations are required.
B.
When constructing a priority queue with constant time insertions.
C.
When needing to maintain a sorted order.
D.
When requiring simple implementation.
Answer: _________
Question 69:
Which algorithm uses a binary heap to improve its performance?
A.
Dijkstra's algorithm for shortest paths.
B.
Kruskal's algorithm for minimum spanning tree.
C.
Prim's algorithm for minimum spanning tree.
D.
Merge sort algorithm.
Answer: _________
Question 70:
What is the maximum number of children a node can have in a binary heap?
A.
2
B.
3
C.
4
D.
No fixed limit
Answer: _________
Question 71:
How do you ensure that a binary heap remains a valid heap after multiple insertions?
A.
By performing a heapify operation after each insertion.
B.
By performing a sort operation.
C.
By rebalancing the tree manually.
D.
By ensuring nodes are inserted in sorted order.
Answer: _________
Question 72:
Multiplication and division to find children and parents cannot be implemented in a d-heap.
A.
true
B.
false
Answer: _________
Question 73:
A leftist heap is also said to be a binary heap.
A.
true
B.
false
Answer: _________
Question 74:
Who invented d-ary heap?
A.
Carl Rick
B.
Alan Turing
C.
Donald Johnson
D.
Euclid
Answer: _________
Question 75:
What is the child of smallest element of the given minimum ternary heap?
A.
1
B.
10
C.
22
D.
24
Answer: _________
Question 76:
Heap can be used as . . . . . . . .
A.
Priority queue
B.
Stack
C.
A decreasing order array
D.
Normal Array
Answer: _________
Question 77:
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: _________
Question 78:
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: _________
Question 79:
Which property should ternary heap hold for execution?
A.
Associative
B.
Commutative
C.
Tree
D.
Heap
Answer: _________
Question 80:
What is the basic operation performed in a pairing heap?
A.
merge
B.
deletion
C.
insertion
D.
swapping
Answer: _________
Question 81:
On which data structure is a d-ary heap based?
A.
stack
B.
queue
C.
linked list
D.
priority queue
Answer: _________
Question 82:
The actual pairing heap implementation uses the right child and left child representation.
A.
true
B.
false
Answer: _________
Question 83:
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: _________
Question 84:
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: _________
Question 85:
Which of these operations have same complexities?
A.
Insertion, find_min
B.
Find_min, union
C.
Union, Insertion
D.
Deletion, Find _max
Answer: _________
Question 86:
d-heap is shallower than a binary heap.
A.
true
B.
false
Answer: _________
Question 87:
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: _________
Question 88:
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
Answer: _________
Question 89:
What is the run time efficiency of an insertion algorithm?
A.
O(N)
B.
O(log N)
C.
O(N 2 )
D.
O(M log N)
Answer: _________
Question 90:
In a leftist heap, all the operations should be performed on?
A.
left path
B.
centre path
C.
right path
D.
root
Answer: _________
Question 91:
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: _________
Question 92:
Should leaves in ternary heap be distributed from left to right.
A.
True
B.
False
Answer: _________
Question 93:
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 root at start.
A.
2
B.
100
C.
17
D.
3
Answer: _________
Question 94:
Heap exhibits the property of a binary tree?
A.
True
B.
False
Answer: _________
Question 95:
Pointer manipulation is generally more time-consuming than multiplication and division.
A.
true
B.
false
Answer: _________
Question 96:
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: _________
Question 97:
Min heap can be used to implement selection sort.
A.
True
B.
False
Answer: _________
Question 98:
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: _________
Question 99:
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
Answer: _________
Question 100:
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: _________
Question 101:
Is decrease priority operation performed more quickly in a ternary heap with respect to the binary heap.
A.
True
B.
False
Answer: _________
Question 102:
Do ternary heap have better memory cache behavior than binary heap.
A.
True
B.
False
Answer: _________
Question 103:
d-heap is similar to that of a?
A.
binary heap
B.
fibonacci heap
C.
leftist heap
D.
treap
Answer: _________
Question 104:
What is the fundamental operation on leftist heap?
A.
insertion
B.
merging
C.
deletion
D.
swapping
Answer: _________
Question 105:
What is the smallest element of the given minimum ternary heap?
A.
1
B.
10
C.
18
D.
20
Answer: _________
Question 106:
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: _________
Question 107:
How many types of the merge are available in skew heaps?
A.
1
B.
2
C.
3
D.
4
Answer: _________
Question 108:
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: _________
Question 109:
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: _________
Question 110:
What is the amortized efficiency of skew merge?
A.
O(N)
B.
O( log N)
C.
O( N log N)
D.
O(N 2 )
Answer: _________
Question 111:
Which node contains a pointer to its parent?
A.
root node
B.
right most child
C.
left most child
D.
left sibling
Answer: _________
Question 112:
What is the other name of weak heap?
A.
Min-heap
B.
Max-heap
C.
Relaxed -heap
D.
Leonardo heap
Answer: _________
Question 113:
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(N 2 )
Answer: _________
Question 114:
What is the highest element of the given maximum ternary heap?
A.
31
B.
10
C.
18
D.
20
Answer: _________
Question 115:
What is the node path length of a node with 0 or 1 child?
A.
1
B.
-1
C.
0
D.
null
Answer: _________
Question 116:
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: _________
Question 117:
How many properties does a leftist heap support?
A.
1
B.
2
C.
3
D.
4
Answer: _________
Question 118:
Min heap is a complete binary tree.
A.
True
B.
False
Answer: _________
Question 119:
The Statement "Fibonacci heap has better amortized running time in compare to a binomial heap".
A.
True
B.
False
Answer: _________
Question 120:
Which of the following methods is the best choice for complex applications?
A.
binary heap
B.
d-heap
C.
treap
D.
pairing heap
Answer: _________
Question 121:
Is the priority queue abstract data type.
A.
True
B.
False
Answer: _________
Question 122:
What is the amortized cost per operation of a skew heap?
A.
O(N)
B.
O(N log N)
C.
O(N 2 )
D.
O(log N)
Answer: _________
Question 123:
What is the best case complexity in building a heap?
A.
O(nlogn)
B.
O(n 2 )
C.
O(n*longn *logn)
D.
O(n)
Answer: _________
Question 124:
The following figure is an example for
A.
d-heap
B.
binary heap
C.
leftist heap
D.
skew heap
Answer: _________
Question 125:
What is the time complexity for decreasing 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: _________
Question 126:
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: _________
Question 127:
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: _________
Question 128:
In a max-heap, element with the greatest key is always in the which node?
A.
Leaf node
B.
First node of left sub tree
C.
root node
D.
First node of right sub tree
Answer: _________
Question 129:
Descending priority queue can be implemented using . . . . . . . .
A.
max heap
B.
min heap
C.
min-max heap
D.
trie
Answer: _________
Question 130:
How many nodes does a leftist tree with r nodes must have?
A.
2 r
B.
2 r -1
C.
2r
D.
2r-1
Answer: _________
Question 131:
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
Answer: _________
Question 132:
In skew heaps, certain constraints are to be met in order to perform swapping.
A.
true
B.
false
Answer: _________
Question 133:
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: _________
Question 134:
. . . . . . . . is a self-adjusting version of a leftist heap.
A.
Rightist heap
B.
Skew heap
C.
d-heap
D.
Binary heap
Answer: _________
Question 135:
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: _________
Question 136:
What is the height of a given minimum ternary heap?
A.
1
B.
10
C.
2
D.
24
Answer: _________
Question 137:
In a leftist heap, the null path length of a null node is defined as?
A.
0
B.
1
C.
null
D.
-1
Answer: _________
Question 138:
The roots of the elements of the subtrees are smaller than the root of the heap.
A.
True
B.
False
Answer: _________
Question 139:
In a binomial heap the root value is greater than left child and less than right child.
A.
True
B.
False
Answer: _________
Question 140:
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(n 2 )
Answer: _________
Question 141:
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(N 2 )
D.
O(M log N)
Answer: _________
Question 142:
In 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: _________
Question 143:
What is the time complexity of inserting an element into a binary heap?
A.
O(1)
B.
O(log n)
C.
O(n)
D.
O(n log n)
Answer: _________
Question 144:
Which of the following is true for a min-heap?
A.
The root node is the smallest element, and every parent node is smaller than its children.
B.
The root node is the largest element, and every parent node is larger than its children.
C.
All nodes are arranged in a complete binary tree.
D.
The tree is always balanced.
Answer: _________
Question 145:
In a max-heap, which node property is true?
A.
Every parent node is greater than or equal to its children.
B.
Every parent node is less than or equal to its children.
C.
All nodes have the same value.
D.
The root node is always the smallest element.
Answer: _________
Question 146:
How do you maintain the heap property after deleting the root node?
A.
By performing a heapify operation.
B.
By reordering the entire heap.
C.
By inserting a new element at the root.
D.
By performing an inorder traversal.
Answer: _________
Question 147:
Which data structure is commonly used to implement priority queues?
A.
Heap
B.
Binary Search Tree
C.
AVL Tree
D.
Red-Black Tree
Answer: _________
Question 148:
What is the height of a complete binary heap with n nodes?
A.
⌈log2(n + 1)⌉
B.
⌈log2(n)⌉
C.
⌈n / 2⌉
D.
log2(n) + 1
Answer: _________
Question 149:
What is the primary operation performed when adjusting a heap after insertion or deletion?
A.
Heapify
B.
Sorting
C.
Searching
D.
Balancing
Answer: _________
Question 150:
In a binary heap, how is the parent node index calculated from a child node index i?
A.
(i - 1) / 2
B.
(i + 1) / 2
C.
2 * i + 1
D.
2 * i - 1
Answer: _________
Question 151:
What is the time complexity of building a heap from an unsorted array?
A.
O(log n)
B.
O(n log n)
C.
O(n)
D.
O(n 2 )
Answer: _________
Question 152:
How do you find the maximum element in a max-heap?
A.
The root node contains the maximum element.
B.
The maximum element is always the leftmost leaf.
C.
By performing an inorder traversal.
D.
By searching the entire heap.
Answer: _________
Question 153:
Which operation cannot be directly performed in a d-heap?
A.
insert
B.
delete
C.
find
D.
create
Answer: _________
Question 154:
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: _________
Question 155:
The amortized time efficiency for performing deletion of a minimum element is?
A.
O(N)
B.
O(log N)
C.
O(N 2 )
D.
O(M log N)
Answer: _________
Question 156:
How many comparisons will occur while performing a delete-min operation?
A.
d
B.
d-1
C.
d+1
D.
1
Answer: _________
Question 157:
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: _________
Question 158:
Which type of data structure is a ternary heap?
A.
Array
B.
Hash
C.
Priority Queue
D.
Priority Stack
Answer: _________
Question 159:
Naive merge cannot be done in a skew merge.
A.
true
B.
false
Answer: _________
Question 160:
Which of the heaps is implemented by the following figure?
A.
fibonacci heaps
B.
pairing heap
C.
skew heap
D.
leftist heap
Answer: _________
Question 161:
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: _________
Question 162:
What is the ancestor of the leaf node in a given minimum ternary heap?
A.
1
B.
10
C.
18
D.
20
Answer: _________
Question 163:
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
Answer: _________
Question 164:
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(↔[i], ↔[parent(i)])
9. i = parent(i)
10. }
11. }
A.
Line - 3
B.
Line - 5
C.
Line - 6
D.
Line - 7
Answer: _________
Question 165:
What is the complexity of 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: _________
Question 166:
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: _________
Answer Key
1:
A
2:
A
3:
A
4:
B
5:
A
6:
A
7:
A
8:
A
9:
D
10:
B
11:
A
12:
B
13:
C
14:
A
15:
A
16:
B
17:
C
18:
C
19:
C
20:
D
21:
A
22:
D
23:
A
24:
D
25:
A
26:
A
27:
B
28:
C
29:
A
30:
B
31:
D
32:
A
33:
A
34:
C
35:
B
36:
B
37:
A
38:
D
39:
C
40:
A
41:
A
42:
A
43:
B
44:
A
45:
A
46:
B
47:
C
48:
A
49:
A
50:
A
51:
A
52:
A
53:
C
54:
A
55:
B
56:
A
57:
A
58:
B
59:
B
60:
C
61:
A
62:
B
63:
B
64:
A
65:
C
66:
B
67:
A
68:
A
69:
C
70:
A
71:
A
72:
B
73:
A
74:
C
75:
B
76:
A
77:
C
78:
C
79:
D
80:
A
81:
D
82:
B
83:
C
84:
D
85:
C
86:
A
87:
A
88:
A
89:
A
90:
C
91:
A
92:
A
93:
A
94:
A
95:
A
96:
B
97:
A
98:
D
99:
A
100:
C
101:
A
102:
A
103:
A
104:
B
105:
A
106:
A
107:
B
108:
B
109:
D
110:
B
111:
C
112:
C
113:
B
114:
A
115:
C
116:
A
117:
C
118:
A
119:
A
120:
D
121:
A
122:
D
123:
D
124:
A
125:
B
126:
C
127:
A
128:
C
129:
A
130:
B
131:
C
132:
B
133:
B
134:
B
135:
C
136:
A
137:
D
138:
B
139:
B
140:
A
141:
A
142:
A
143:
B
144:
A
145:
A
146:
A
147:
A
148:
A
149:
A
150:
A
151:
C
152:
A
153:
C
154:
A
155:
B
156:
B
157:
A
158:
C
159:
B
160:
B
161:
B
162:
A
163:
C
164:
C
165:
B
166:
C