Computer Science 230 Homework 5

Assignment:
1a. Use a hash table of size thirteen. First initialize the table.
We want to be able to delete from the table easily.
The hash
function is f(k) = k%13.
Use a linear probing to deal with collisions. On the left, show the table after
the following keys have been inserted in this order:

1b. Given the current state of the scatter table in
Question 1a, briefly explain how you would search for the numbers 4, 38, and 32.

 
1c. Show the table of Question 1a after deleting the
numbers 31 and 43. DO NOT ERASE THE FIRST TABLE. Write your answer in the right-hand
table.

1d. Given the current state of the scatter table in
Question 1c, briefly explain how you would search for the numbers 4, 38, and 32.

 

 
2a. Given a hash table of size seven with the hash function f(key)
= key%7,  show
the hash table after the following keys have been inserted in this order. Use a
linked hashed structure (p. 292) to
deal with collisions.

16,
29, 23, 20, 17, 31, 2, 15, 36, 30, 13

b. Given the current state of the hash table in
Question 3, briefly explain how you would search for the numbers 23, 4, and 22.

 Submission:

Alternative ways
to submit:

1. Print this document and write your answers on it.
Give it to me by the date and time above. Be sure to put your name on it.

2. Edit this document so that it contains your
answers. Be sure to put your name in it. Name it <yourName.doc, where <yourName is your last name. Submit it on WebCT by the date and time above.

3. Print this document and write your answers on it.
Be sure to put your name in it. Scan it and submit it as a pdf file. Name it <yourName.pdf, where <yourName is your last name. Submit on WebCT by the date and time above.
Powered by