ADVANCED DATA STRUCTURES AND
SEARCH ALGORITHMS QUESTIONS
WITH VERIFIED ANSWERS 2026/2027
1. What is the strict upper bound on the height of an AVL tree with n nodes?
A. 1.618 log2(n)
B. 2 log2(n + 1)
C. log2(n)
D. 1.44 log2(n + 2) - 1.328
Answer: D
Conceptual Explanation: The height of an AVL tree is bounded by approximately 1.44 log
n, which is derived from the relation between AVL trees and Fibonacci numbers.
2. In a Red-Black Tree, what is the maximum possible ratio between the longest path and the
shortest path from the root to a leaf?
A. 2:1
B. 1:1
C. 3:1
,D. Log n : 1
Answer: A
Conceptual Explanation: Due to the properties that no red node has a red child and every
path has the same number of black nodes, the longest path (alternating red-black) can be at
most twice the length of the shortest path (all black).
3. Which operation in a Fibonacci Heap has a worst-case time complexity of O(n) but an
amortized complexity of O(log n)?
A. Extract Minimum
B. Insert
C. Find Minimum
D. Decrease Key
Answer: A
Conceptual Explanation: Extract Minimum involves a consolidation step that can take
O(n) in the worst case, but through potential functions, its amortized cost is shown to be
O(log n).
4. In a Splay Tree, what is the amortized cost of any M access operations on a tree of N
nodes?
A. O(M log N)
B. O(M + N)
, C. O(N log M)
D. O(M N)
Answer: A
Conceptual Explanation: Splay trees guarantee an amortized time complexity of O(log N)
per operation using the splaying heuristic, even though individual operations can be O(N).
5. What is the minimum number of keys in a non-root internal node of a B-tree of order m?
A. m - 1
B. ceil(m/2)
C. ceil(m/2) - 1
D. floor(m/2)
Answer: C
Conceptual Explanation: By definition, every internal node except the root must have at
least ceil(m/2) children, which corresponds to ceil(m/2) - 1 keys.
6. Which rotation is required when a node is inserted into the right subtree of the left child of
a node, causing an imbalance in an AVL tree?
A. Left-Left Rotation
B. Right-Right Rotation
C. Left-Right Rotation
SEARCH ALGORITHMS QUESTIONS
WITH VERIFIED ANSWERS 2026/2027
1. What is the strict upper bound on the height of an AVL tree with n nodes?
A. 1.618 log2(n)
B. 2 log2(n + 1)
C. log2(n)
D. 1.44 log2(n + 2) - 1.328
Answer: D
Conceptual Explanation: The height of an AVL tree is bounded by approximately 1.44 log
n, which is derived from the relation between AVL trees and Fibonacci numbers.
2. In a Red-Black Tree, what is the maximum possible ratio between the longest path and the
shortest path from the root to a leaf?
A. 2:1
B. 1:1
C. 3:1
,D. Log n : 1
Answer: A
Conceptual Explanation: Due to the properties that no red node has a red child and every
path has the same number of black nodes, the longest path (alternating red-black) can be at
most twice the length of the shortest path (all black).
3. Which operation in a Fibonacci Heap has a worst-case time complexity of O(n) but an
amortized complexity of O(log n)?
A. Extract Minimum
B. Insert
C. Find Minimum
D. Decrease Key
Answer: A
Conceptual Explanation: Extract Minimum involves a consolidation step that can take
O(n) in the worst case, but through potential functions, its amortized cost is shown to be
O(log n).
4. In a Splay Tree, what is the amortized cost of any M access operations on a tree of N
nodes?
A. O(M log N)
B. O(M + N)
, C. O(N log M)
D. O(M N)
Answer: A
Conceptual Explanation: Splay trees guarantee an amortized time complexity of O(log N)
per operation using the splaying heuristic, even though individual operations can be O(N).
5. What is the minimum number of keys in a non-root internal node of a B-tree of order m?
A. m - 1
B. ceil(m/2)
C. ceil(m/2) - 1
D. floor(m/2)
Answer: C
Conceptual Explanation: By definition, every internal node except the root must have at
least ceil(m/2) children, which corresponds to ceil(m/2) - 1 keys.
6. Which rotation is required when a node is inserted into the right subtree of the left child of
a node, causing an imbalance in an AVL tree?
A. Left-Left Rotation
B. Right-Right Rotation
C. Left-Right Rotation
