M.Tech Weekend Quiz-1 (Hashing and tree)

What is the primary purpose of a hash function in a hash table?

• To sort elements

• To compute the index for storage or retrieval

• To eliminate duplicate elements

• To generate unique values for each key

Which of the following collision resolution techniques uses linked lists to handle collisions?

• Linear Probing

• Double Hashing

• Separate Chaining

• Quadratic Probing

What is the main disadvantage of Linear Probing in Open Addressing?

• High memory usage

• Difficult to implement

• Primary clustering

• High computational cost

Which of the following is not a form of open addressing?

• Linear Probing

• Separate Chaining

• Quadratic Probing

• Double Hashing

Suppose you are using Linear Probing with a hash table of size 11. You insert the following keys: 21, 32, 46, 39. If the hash function is ℎ(𝑘)=𝑘%11, at which index will the key 39 be placed?

• Index 2

• Index 7

• Index 3

• Index 6

Open Addressing resolves hash collisions by:

• Chaining with a linked list

• Finding another empty slot using a probe sequence

• Using a second hash function to find a slot

• Ignoring collisions

Rehashing is required when:

• The load factor exceeds a threshold

• The hash function has too many collisions

• You are adding more keys than the table size

• All of the above

What is the time complexity of inserting an element in a Binary Search Tree (BST) in the worst case?

• O(log n)

• O(n)

• O(1)

• O(n^2)

Which of the following is true about Binary Search Trees (BSTs)?

• The left subtree contains nodes with values greater than the root

• The right subtree contains nodes with values smaller than the root

• Both subtrees must also be binary search trees

• All nodes have exactly two children

Given a Binary Search Tree with the following elements inserted in order: 20, 10, 25, 5, 15, 22, 30, what will be the preorder traversal of the tree?

• 5, 10, 15, 20, 22, 25, 30

• 20, 5, 10, 15, 25, 22, 30

• 20, 10, 5, 15, 25, 22, 30

• 10, 5, 15, 20, 22, 25, 30