B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 3 ā Questions and Answers
Question 1: Which collision resolution technique for hash tables stores all colliding elements in a linked list at the same bucket?
- Open addressing
- Linear probing
- Separate chaining (Correct answer)
- Double hashing
Correct answer: Separate chaining
Separate chaining stores multiple elements mapping to the same hash value in a linked list at that index.
Question 2: What is the average-case time complexity for insertion in a hash table with a good hash function?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(nĀ²)
Correct answer: O(1)
With a good hash function and low load factor, hash table insertion averages O(1) time.
Question 3: An AVL tree is a self-balancing BST where the height difference between left and right subtrees of any node is at most:
- 0
- 1 (Correct answer)
- 2
- log n
Correct answer: 1
AVL trees maintain the invariant that the balance factor (height difference) of any node is -1, 0, or +1.
Question 4: Which rotation is applied to fix a Left-Right (LR) imbalance in an AVL tree?
- Single right rotation
- Single left rotation
- Left rotation followed by right rotation (Correct answer)
- Right rotation followed by left rotation
Correct answer: Left rotation followed by right rotation
An LR imbalance is fixed with a left rotation on the left child followed by a right rotation on the unbalanced node.
Question 5: In a B-tree of order m, what is the maximum number of keys a single node can hold?
- m
- m - 1 (Correct answer)
- 2m
- m + 1
Correct answer: m - 1
A B-tree node of order m can hold at most m - 1 keys and m children.
Question 6: Which data structure allows efficient insertion and deletion at both ends in O(1) time?
- Stack
- Queue
- Deque (double-ended queue) (Correct answer)
- Binary heap
Correct answer: Deque (double-ended queue)
A deque supports O(1) push and pop operations at both the front and back ends.
Question 7: What is the main advantage of a skip list over a balanced BST?
- Lower memory usage
- Simpler concurrent implementation (Correct answer)
- Better worst-case time complexity
- No need for comparison operations
Correct answer: Simpler concurrent implementation
Skip lists are easier to implement in concurrent settings because they don't require complex rebalancing operations.
B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 3
Which collision resolution technique for hash tables stores all colliding elements in a linked list at the same bucket?