- Dictionary Implementations Chapter 21 Exam Prep

Chapter 21 - Dictionary Implementations

True/False (11)

1. In a dictionary implementation, you cannot encapsulate both the search and the value in a single object.
2. In the unsorted array-based dictionary class ArrayDictionary, the inner class Entry has no need to set or change the search key.
3. In the unsorted array-based dictionary class ArrayDictionary, adding an entry requires a binary search.
4. In the unsorted array-based dictionary class ArrayDictionary, removing an entry requires a sequential search.
5. In the unsorted array-based dictionary class ArrayDictionary, retrieving an entry does not require a search.
6. To remove an entry from an unsorted array-based dictionary, locate the entry and replace it with the first entry in the dictionary.
7. In Java, copying array entries that are references to objects is fast.
8. In a sorted array-based dictionary, the search key must belong to a class that implements the interface Comparable.
9. A linked chain can provide as much storage as necessary for dictionary entries.
10. In a sorted linked dictionary, changing the search key will not affect the order of the dictionary.
11. In a sorted linked dictionary, you know a search key does not exist in the chain as soon as you pass the node that should have contained it.

Short Answer (5)

1. Explain why adding an element to an unsorted array-based dictionary has an efficiency of O(n) when additions occur after the last entry without shifting any data.
2. Explain how you add a new entry to a sorted array-based dictionary.
3. Explain how you remove an entry from a sorted array-based dictionary.
4. Why is it a good practice to include comments in a class’s implementation that tells the client what the efficiency of a method is?
5. Explain why adding an element to an unsorted linked dictionary has an efficiency of O(n) when additions occur after the last node.

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

1. In an array-based implementation of a dictionary, using one array to store the search keys and a separate array to store the corresponding values is called
   1. parallel arrays
   2. concurrent arrays
   3. corresponding arrays
   4. duplicate arrays
2. In an array-based implementation of a dictionary, you can store key-value pairs
   1. in parallel arrays
   2. encapsulated in an object
   3. both a & b
   4. none of the above
3. In the unsorted array-based dictionary class ArrayDictionary, the class Entry is
   1. private and internal
   2. protected
   3. public
   4. part of the package
4. In the unsorted array-based dictionary class ArrayDictionary, which method requires a sequential search?
   1. add
   2. remove
   3. retrieve
   4. all of the above
5. In the unsorted array-based dictionary class ArrayDictionary, which method requires a binary search?
   1. add
   2. remove
   3. retrieve
   4. none of the above
6. In the unsorted array-based dictionary class ArrayDictionary, the method ensureCapacity
   1. checks to see if the array is full
   2. doubles the size of the array if it is full
   3. avoids a full dictionary
   4. all of the above
7. In the unsorted array-based dictionary class ArrayDictionary, what does the locateIndex method return if the search key is not found?
   1. the numberOfEntries
   2. null
   3. 0
   4. it throws an exception
8. In the unsorted array-based dictionary class ArrayDictionary, a new key-value entry is added
   1. after the last entry in the array
   2. before the first entry in the array
   3. in sorted order in the array
   4. none of the above
9. In the unsorted array-based dictionary class ArrayDictionary, what does the add method return if the search key is not found?
   1. null
   2. the numberOfEntries
   3. 0
   4. true
10. In the unsorted array-based dictionary class ArrayDictionary, what does the add method return if the search key is found?
    1. the corresponding value it found
    2. the numberOfEntries
    3. null
    4. it throws an exception
11. To remove an entry from an unsorted array-based dictionary, locate the entry and
    1. replace it with the last entry in the dictionary
    2. replace it with the first entry in the dictionary
    3. replace it with the entry just after the location where it was found
    4. replace it with the entry just prior to the location where it was found
12. In the unsorted array-based dictionary class ArrayDictionary, what does the remove method return if the search key is found in the dictionary?
    1. the corresponding value
    2. the search key
    3. true
    4. null
13. In the unsorted array-based dictionary class ArrayDictionary, what does the remove method return if the search key is not found in the dictionary?
    1. null
    2. the search key
    3. false
    4. it throws an exception
14. In a sorted array-based dictionary, the search key must belong to a class that implements the interface
    1. Comparable
    2. Sortable
    3. Dictionary
    4. Equals
15. In the unsorted array-based dictionary, the worst-case time efficiency of adding a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
16. In the unsorted array-based dictionary, the worst-case time efficiency of removing a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
17. In the unsorted array-based dictionary, the worst-case time efficiency of retrieving a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
18. In the unsorted array-based dictionary, the worst-case time efficiency of traversing the dictionary is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
19. In a sorted array-based dictionary, you add an entry by
    1. shifting subsequent array entries up by one position
    2. shifting subsequent array entries down by one position
    3. adding it to the end of the array
    4. adding it to the beginning of the array
20. In the sorted array-based dictionary, the worst-case time efficiency of adding a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
21. In the sorted array-based dictionary, the worst-case time efficiency of removing a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
22. In the sorted array-based dictionary, the worst-case time efficiency of retrieving a key-value pair is
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n2)
23. In the sorted array-based dictionary, the worst-case time efficiency of traversing the dictionary is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
24. In the unsorted linked dictionary, the worst-case time efficiency of adding a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
25. In the unsorted linked dictionary, the worst-case time efficiency of removing a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
26. In the unsorted linked dictionary, the worst-case time efficiency of retrieving a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
27. In the unsorted linked dictionary, the worst-case time efficiency of traversing the dictionary is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
28. In the sorted linked dictionary, the worst-case time efficiency of adding a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
29. In the sorted linked dictionary, the worst-case time efficiency of removing a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
30. In the sorted linked dictionary, the worst-case time efficiency of retrieving a key-value pair is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n2)
31. In the sorted linked dictionary, the worst-case time efficiency of traversing the dictionary is
    1. O(n)
    2. O(log n)
    3. O(1)
    4. O(n²)