Test on Hash Tables: Efficient Dictionary Data Structures

Question 1: In open addressing, the hash table design prevents it from ever reaching a state where no further insertions can be made.

A. Yes

B. No

Explanation: In open addressing, the hash table can 'fill up' so that no further insertions can be made, leading to a 'hash table overflow' error as described in the HASH-INSERT procedure. This means the load factor cannot exceed 1.

Question 2: According to Theorem 11.6, what is the upper bound for the expected number of probes in an unsuccessful search in an open-address hash table with load factor "alpha", assuming uniform hashing?

A. 1 / (1 + alpha)

B. alpha / (1 - alpha)

C. 1 / (1 - alpha)

D. alpha * (1 - alpha)

Explanation: Theorem 11.6 states that the expected number of probes for an unsuccessful search is at most 1 / (1 - alpha). This bound indicates that if the load factor (alpha) is a constant, an unsuccessful search runs in O(1) time.

Question 3: Secondary clustering in quadratic probing occurs when different initial probe positions lead to identical probe sequences for two distinct keys.

A. Yes

B. No

Explanation: Secondary clustering in quadratic probing arises when two keys have the same initial probe position, which then causes their entire probe sequences to be the same, as h(k1, 0) = h(k2, 0) implies h(k1, i) = h(k2, i). The given statement describes the opposite scenario.

Question 4: Which formula correctly represents the hash function used in quadratic probing, where h_0 is an auxiliary hash function, c_1 and c_2 are positive auxiliary constants, and i is the probe number?

A. (h_0(k) + c_1 * i + c_2 * i^2) mod m

B. (h_0(k) + i) mod m

C. (h_0(k) - c_1 * i + c_2 * i^2) mod m

D. (h_0(k) + c_1 * i + c_2 * i) mod m

Explanation: According to the study materials, quadratic probing uses a hash function of the form h(k, i) = (h_0(k) + c_1 * i + c_2 * i^2) mod m, where h_0 is an auxiliary hash function, c_1 and c_2 are positive auxiliary constants, and i is the probe number.

Question 5: In an unsuccessful search using open-address hashing, the last slot probed is empty.

A. Yes

B. No

Explanation: The study materials state: "In an unsuccessful search, every probe but the last accesses an occupied slot that does not contain the desired key, and the last slot probed is empty."