Ch23 - Hashing As A Dictionary Implementation Full Test Bank

Chapter 23 - Hashing as a Dictionary Implementation

True/False (15)

1. The successful addition of a new entry in a dictionary occurs after a search for a given key fails.
2. An unsuccessful addition is the result of an unsuccessful search for a given key.
3. The cost of a successful search for an entry is less than the cost of inserting that entry.
4. An unsuccessful removal of an entry has the same efficiency as an unsuccessful search.
5. Collision resolution takes less time than evaluating the hash function.
6. Collision resolution is the main contributor to the cost of hashing.
7. In separate chaining, λ has no maximum value.
8. In separate chaining, the number of entries cannot exceed the size of the hash table.
9. λ is the cost of collision resolution.
10. All open addressing schemes use more than one location in the hash table per entry.
11. If you use double hashing for collision resolution, it is recommended that the hash table be less than half full.
12. The degradation in performance as λ increases is more severe than linear probing.
13. A location in the hash table that is in the available state contains an entry in the removed state.
14. An odd integer 5 or greater is prime if it is not divisible by every odd integer up to its square root.
15. Hashing as a dictionary implementation does not support operations that involve sorted search keys.

Short Answer (7)

1. What is λ for a hash table with 500 locations and 200 entries that uses open addressing?
2. What is λ for a hash table with 200 locations and 50 entries that uses open addressing?
3. Explain why resizing a hash table that has 751 entries to double the size, or 1502, is a bad idea.
4. Given a table size of 13, the hash function h(k) = k % table size, and the entries 14, 2, 15, 26 and 29, show the hash table after the five entries are inserted into the table using open addressing with linear probing.

2 % 13 = 2
15 % 13 = 2 << collision
26 % 13 = 0
29 % 13 = 3 << collision

index 0 1 2 3 4 5 6 7 8 9 10 11 12
entry 26 14 2 15 29

1. Given the following hash table whose size is 13 and the hash function h(k) = k % table size, show the hash table after rehashing to a table size of 17, using open addressing with linear probing.
   
   index 0 1 2 3 4 5 6 7 8 9 10 11 12
   entry 12 7 14 23 37 28

7 % 17 = 7
14 % 17 = 14
23 % 17 = 6
37 % 17 = 3
28 % 17 = 11

index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
entry 37 23 7 28 12 14

1. Given a table size of 19, the hash function h(k) = k % table size, and the entries 19, 38, 20, 39 and 21, show the hash table after the five entries are inserted into the table using open addressing with linear probing.

38 % 19 = 0 << collision
20 % 19 = 1 << collision
39 % 19 = 1 << collision
21 % 19 = 2 << collision

index 0 1 2 3 4 5 6 7 8 9 10 11 12
entry 19 38 20 39 21

1. Given a table size of 19, the hash function h(k) = k % table size, and the entries 19, 38, 20, 39 and 21, show the hash table after the five entries are inserted into the table using buckets.

38 % 19 = 0 << collision
20 % 19 = 1 << collision
39 % 19 = 1 << collision
21 % 19 = 2 << collision

index 0 1 2 3 4 5 6 7 8 9 10 11 12
entry 19 20 21
38 39

Multiple Choice (22) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. Hashing is a good technique for implementing a dictionary when _____ is the primary task.
   1. searching
   2. sorting
   3. adding entries
   4. removing entries
2. Which dictionary operation searches the hash table for a given search key?
   1. getValue
   2. remove
   3. add
   4. all of the above
3. The successful addition of a new entry in a dictionary occurs
   1. after a search for a given key fails
   2. after a search for a given key succeeds
   3. after linear probing
   4. after quadratic probing
4. The cost of a successful search for an entry is _____ the cost of inserting that entry.
   1. The same as
   2. more than
   3. less than
   4. unrelated to
5. What is the ratio of the size of the dictionary to the size of the hash table called?
   1. load factor
   2. hash factor
   3. fullness quotient
   4. hash ratio
6. When a hash table is empty, λ is
   1. 0
   2. 0.1
   3. 1
   4. undefined
7. When λ = 0 the hash table
   1. is empty
   2. is full
   3. is ready to resized
   4. needs to be created
8. When a hash table is full, λ is
   1. 1
   2. 0.1
   3. 0
   4. undefined
9. λ is a measure of
   1. the cost of collision resolution
   2. hashing
   3. linear probing
   4. increasing the table size
10. What is λ in a hash table whose size is 150 that has 45 entries?
    1. 0.3
    2. 0.45
    3. 3.33
    4. 0.25
11. If you use quadratic probing for collision resolution, it is recommended that the hash table be
    1. less than half full
    2. more than half full
    3. almost empty
    4. extended to use buckets
12. In separate chaining, λ is
    1. the average number of dictionary entries per chain
    2. the maximum number of dictionary entries per chain
    3. the number of indexes without a chain
    4. the number of indexes with a chain
13. If you can find a perfect hash function for you particular set of keys, the ADT dictionary will provide operations with efficiency of
    1. O(1)
    2. O(log n)
    3. O(n)
    4. O(n2)
14. To maintain reasonable efficiency in hashing with separate chaining, you should keep
    1. λ < 1
    2. λ = 1
    3. λ > 1
    4. λ < 100
15. The average number of comparisons for an unsuccessful search when hashing with separate chaining is
    1. λ
    2. 1 + λ / 2
    3. n / λ
    4. n
16. The average number of comparisons for a successful search when hashing with separate chaining is
    1. 1 + λ / 2
    2. λ
    3. n / λ
    4. n
17. Enlarging a hash table and computing new hash indices for its contents is called
    1. rehashing
    2. resizing
    3. linear expansion
    4. quadratic expansion
18. In hashing with open addressing, an empty location is represented by
    1. null
    2. 0
    3. an empty flag
    4. none of the above
19. In the class HashDictionary, the method remove returns _____ if the key is not found.
    1. null
    2. -1
    3. 0
    4. throws a KeyNotHashedException
20. In the class HashDictionary, the method getValue returns _____ if the key is not found.
    1. null
    2. -1
    3. 0
    4. throws a KeyNotHashedException
21. Given a table size of 19 the hash function h(k) = k % table size, what index does the entry 24 map to?
    1. 5
    2. 4
    3. 19
    4. 24
22. Given a table size of 13 the hash function h(k) = k % table size, what index does the entry 26 map to?
    1. 0
    2. 13
    3. 26
    4. 12