CPSC 211, Sec 201-203: Quiz 10
April 7, 2004

Name:________________________________________

  1. (2 pts) Consider a hash table where collisions are resolved with chaining. Under what conditions do the operations of insert, search and delete take constant expected time?







  2. (1 pt) Consider a hash table using chaining where M = 5, h(k) = k mod 5, and the keys 1, 5, 11, 15 are inserted, in that order, into an initially empty hash table. Draw the result.









  3. (1 pt) Consider a hash table using open addressing with linear probing where M = 5, h(k) = k mod 5, and the keys 1, 5, 11, 15 are inserted, in that order, into an initially empty hash table. Draw the result.








  4. (1 pt) What is double hashing?