1. Assume n items ((key, value) pairs) are inserted into a Dictionary implemented with a Linked List (e.g., a log file) where the key can have N possible values. The average time is _______ for an put(k,v), _______ for a find(k), and _______ for an erase(k). The data structures space usage is ________.

2. Consider a Hash Table H of size N = 11 and the hash function h(k) = k mod N and double hash function d(k) = 1 + (k mod (N-1)).

(a) The key 19 has a hash value of ______ and a double hash value of _______.

(b) The key 10 has a hash value of ______ and a double hash value of _______.

3. Consider the insertion into a hash table of (left to right) 5, 2, 11, 6, 22, 1, 27. Assume a Hash Table of size N=11 with the hash/double hash functions specified in #2.

(a) Draw the resulting Hash Table using chaining to resolve collisions.

(b) Draw the resulting Hash Table using linear probing to resolve collisions.

(c) Draw the resulting Hash Table using double hashing to resolve collisions.