Sample | Sample Final Exam | COMP2521 |
Consider a scenario where we have
Based on the above answer the following questions:
In the ideal case (no collisions), what is the complexity of searching for a key in a hash table with N slots?
Consider the scenario where the above hash table uses chaining for collision resolution, and has the following distribution of chain lengths: 2 slots are empty, 2 slots have a chain of length 1, 1 slot has a chain of length 2, 1 slot has a chain of length 3, and 1 slot has a chain of length 4.
Now consider the scenario where the hash table uses linear probing for collision resolution. If we start from an initially empty hash table and insert the following keys (in the order supplied) into the table:
11 21 31 32 12 22 24
show the state of the hash table after the insertion of each key. (The q5.txt file contains a template for how to show the table, and even shows the state of the table after the insertion of the first key).
Now consider the scenario where the hash table uses double hashing for collision resolution, with h2 as the secondary hash function. If we start from an initially empty hash table and insert the following keys (in the order supplied) into the table:
11 21 31 32 12 22 24
show the state of the hash table after the insertion of each key. (The q5.txt file contains a template for how to show the table, and even shows the state of the table after the insertion of the first key).
Type the answer to this question into the file called q5.txt and submit it using the command:
$ submit q5
The above command will make a copy of q5.txt as your answer for this question.