Q.1 What is the main goal of constructing an Optimal Binary Search Tree (OBST)?
Minimize height of the tree
Minimize average search cost
Maximize number of nodes
Balance left and right subtrees
Explanation - The primary objective of an OBST is to minimize the expected cost of searching based on key access probabilities.
Correct answer is: Minimize average search cost
Q.2 Which technique is commonly used to solve the OBST problem?
Greedy Algorithm
Divide and Conquer
Dynamic Programming
Backtracking
Explanation - OBST is solved using dynamic programming as it relies on solving overlapping subproblems and using optimal substructure.
Correct answer is: Dynamic Programming
Q.3 The cost of an Optimal BST depends on:
Only the number of nodes
Frequency of access of keys
Tree height only
Insertion order of keys
Explanation - The construction of OBST considers the probability of accessing each key to minimize the weighted search cost.
Correct answer is: Frequency of access of keys
Q.4 If all keys are equally likely, the optimal BST is:
A skewed tree
A balanced tree
A linked list
A heap
Explanation - When all probabilities are equal, the optimal BST resembles a balanced BST to minimize average depth.
Correct answer is: A balanced tree
Q.5 Which of the following is NOT true about OBST?
It uses dynamic programming
It minimizes search cost
It always produces a balanced tree
It considers frequency of access
Explanation - OBST may not always be balanced; it depends on the key access probabilities.
Correct answer is: It always produces a balanced tree
Q.6 The time complexity of constructing an OBST using dynamic programming is:
O(n)
O(n^2)
O(n^3)
O(2^n)
Explanation - The standard DP solution for OBST has O(n^3) time complexity due to three nested loops.
Correct answer is: O(n^3)
Q.7 What does the DP table in OBST store?
Node positions
Subtree heights
Minimum search costs of subproblems
In-order traversals
Explanation - The DP table stores the cost of optimal BSTs for subranges of keys.
Correct answer is: Minimum search costs of subproblems
Q.8 Which values are used to compute the cost of an OBST?
Frequencies
Prefix sums of probabilities
Heights of nodes
Node indices only
Explanation - Prefix sums (weights) are used to efficiently compute subproblem probabilities for OBST cost calculation.
Correct answer is: Prefix sums of probabilities
Q.9 What does the root selection step in OBST depend on?
Random choice
Frequency distribution
Inorder traversal
Heap order property
Explanation - The root is chosen based on minimizing expected cost, which depends on key access frequencies.
Correct answer is: Frequency distribution
Q.10 In OBST, unsuccessful searches are handled by:
Ignoring them
Assigning dummy keys with probabilities
Balancing tree
Using heaps
Explanation - Dummy nodes are introduced to represent unsuccessful searches with their respective probabilities.
Correct answer is: Assigning dummy keys with probabilities
Q.11 Who first proposed the algorithm for constructing OBST?
Cormen
Knuth
Tarjan
Dijkstra
Explanation - Donald Knuth proposed an efficient method for constructing optimal BSTs.
Correct answer is: Knuth
Q.12 OBST is useful in which scenario?
Sorting numbers
Compilers symbol table lookups
Matrix multiplication
Graph traversal
Explanation - OBST is applied in symbol table lookups where access frequencies are known.
Correct answer is: Compilers symbol table lookups
Q.13 Which data structure is directly related to OBST?
Stack
Queue
Binary Search Tree
Heap
Explanation - OBST is a special type of Binary Search Tree constructed based on optimal search costs.
Correct answer is: Binary Search Tree
Q.14 The space complexity of OBST dynamic programming solution is:
O(n)
O(n^2)
O(n^3)
O(1)
Explanation - Two 2D tables (cost and root) are required, giving O(n^2) space complexity.
Correct answer is: O(n^2)
Q.15 In OBST, the cost of a tree is calculated as:
Sum of probabilities
Weighted path length
Number of nodes
Tree height
Explanation - The cost is the sum of probabilities multiplied by their depths (weighted path length).
Correct answer is: Weighted path length
Q.16 If probabilities are skewed towards one key, the OBST will:
Be perfectly balanced
Be skewed toward that key
Have equal depth for all nodes
Ignore frequencies
Explanation - The OBST structure adapts to minimize cost, possibly resulting in skewness.
Correct answer is: Be skewed toward that key
Q.17 Knuth’s optimization reduces OBST complexity from:
O(n^4) to O(n^2)
O(n^3) to O(n^2)
O(n^2) to O(n log n)
O(n^3) to O(n log n)
Explanation - Knuth proposed a monotonicity-based optimization that reduces OBST DP complexity.
Correct answer is: O(n^3) to O(n^2)
Q.18 Which of the following tables is also maintained during OBST computation?
Frequency table
Root table
Hash table
Adjacency matrix
Explanation - A root table is maintained to reconstruct the OBST structure.
Correct answer is: Root table
Q.19 In OBST, dummy nodes represent:
Keys with zero probability
Unsuccessful searches
Deleted keys
Extra balancing nodes
Explanation - Dummy nodes are used to handle unsuccessful searches with their own probabilities.
Correct answer is: Unsuccessful searches
Q.20 Which traversal guarantees sorted order in OBST?
Preorder
Postorder
Inorder
Level order
Explanation - Like any BST, inorder traversal of OBST gives sorted order of keys.
Correct answer is: Inorder
Q.21 Which of the following is NOT needed in OBST computation?
Probabilities of keys
Prefix sums
Height of each node
DP table
Explanation - Node height is not directly required; DP computes costs using weights and roots.
Correct answer is: Height of each node
Q.22 Optimal Binary Search Tree is a generalization of:
Huffman coding
Balanced BST
AVL tree
Greedy selection
Explanation - Both OBST and Huffman coding use frequencies to minimize weighted path length.
Correct answer is: Huffman coding
Q.23 Which of the following operations benefits most from OBST?
Search
Insertion
Deletion
Balancing
Explanation - OBST is designed to minimize the average cost of search operations.
Correct answer is: Search
Q.24 In OBST, if all keys have probability zero, the cost will be:
Zero
One
Infinity
Undefined
Explanation - With zero access probability, no search contributes cost, so the cost is zero.
Correct answer is: Zero
Q.25 The root chosen in OBST dynamic programming is the one that:
Maximizes left subtree size
Minimizes total expected cost
Balances keys equally
Always chooses the median
Explanation - The chosen root minimizes the sum of left and right subproblem costs with weights.
Correct answer is: Minimizes total expected cost