Question

Suppose we have a separate chaining hash table as given in the figure below, where the hash function is h(K) = K mod 12. Fill in your answers with a single integer (e.g. 6) or a decimal number (e.g. 6.5) with NO spaces before or after. Note: checking a Null value/empty cell is not counted as a key comparion. a) The maximum number of key comparisons for a successful search is b) After inserting in the table three more keys 53, 34, and 89, the average number of key comparisons required for a successful search is c) If we use an open address hashing with linear probing to construct a hash table for the sequence of keys 37, 39, 41, 54, 92, 77, 65, 42 (in the given order) using the same hash function h(K) = K mod 12, the largest number of key comparisons in an unsuccessful search in this table is____ ; if we delete the key 54 from this hash table, then the number of key comparisons required to find 65 will be___

Answer 1

a) The maximum number of key comparisons for a successful search is 1. b) After inserting in the table three more keys 53, 34, and 89, the average number of key comparisons required for a successful search is 1.5. c) If we use an open address hashing with linear probing to construct a hash table for the sequence of keys 37, 39, 41, 54, 92, 77, 65, 42 (in the given order) using the same hash function h(K) = K mod 12 , the largest number of key comparisons in an unsuccessful search in this table is 8; if we delete the key 54 from this hash table, then the number of key comparisons required to find 65 will be 5.

Step-by-step explanation: