B CompE Bachelor of Computer Engineering Bachelor of Computer Engineering Data Structure 3

Question 1

Which collision resolution technique for hash tables stores all colliding elements in a linked list at the same bucket?

Accepted Answer

Separate chaining

Answer

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?

Accepted Answer

O(1)

Answer

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:

Accepted Answer

1

Answer

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?

Accepted Answer

Left rotation followed by right rotation

Answer

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?

Accepted Answer

m - 1

Answer

A B-tree node of order m can hold at most m - 1 keys and m children.

B CompE Bachelor of Computer Engineering Practice Test