Chapter 18 Questions
Multiple Choice
1. The ADT dictionary is appropriate for problems that must manage data by
a. value
b. order
c. priority
d. importance
2. What does the ADT dictionary use to identify its entries?
a. it’s position in the list
b. a search key
c. its priority
d. what group it belongs to
3. Which of the following is not an ADT dictionary operation?
a. add a new entry
b. retrieve an entry
c. sort the entries
d. traverse the entries in sorted search-key order
4. Which of the following is the better choice when attempting to add a new entry to a dictionary
where the search key already exists?
a. replace the existing entry with a new entry
b. crash the program
c. throw an exception
d. deny the attempt
5. In the header file for the class ArrayDictionary, the text declares which of the following
methods as private?
a. destroyDictionary()
b. isEmpty()
c. getNumberOfEntries()
d. clear()
6. In the class ArrayDictionary declared by the text, which of the following methods bears the
responsibility for keeping the array items sorted?
a. remove
b. add
c. getValue
d. traverse
7. According to the text, for the ADT dictionary, in which of the following situations would a sorted
array-based implementation be appropriate for frequent retrievals?
a. when the maximum size is unknown
b. when the maximum size is known
Chapter 18 Questions
c. when you have duplicate search keys
d. when search keys are all similar.
8. According to the text, for the ADT dictionary, what implementation should be used when you do
not know the maximum size of the dictionary?
a. link-based
b. array-based
c. max-heap
d. binary search tree
9. According to the text, for the ADT dictionary, a sorted array-based implementation will shift data
during what two operations?
a. additions and removals
b. additions and traversals
c. removals and traversals
d. searches and gets
10. Which of the following dictionary operations has efficiency O(n) no matter what
implementation if the ADT dictionary is chosen?
a. retrieval
b. traversal
c. removal
d. addition
11. What is the implementation of the ADT dictionary which has efficiency O(log n) for addition?
a. unsorted link-based
b. sorted array-based
c. binary search tree
d. sorted link-based
12. What is the implementation of the ADT dictionary which has efficiency O(1) for addition?
a. sorted link-based
b. sorted array-based
c. binary search tree
d. unsorted link-based
13. What kind of function tells you where a dictionary entry is currently or will be placed if it is new?
a. hash function
b. logarithmic function
c. interrogatory function
d. big O function
14. What is it called when a hash function maps two or more search keys into the same integer
a. an accident
Chapter 18 Questions
b. a collision
c. a perfect hash function
d. an exception
15. When you begin at the hash location and search the dictionary sequentially, this is called what?
a. closed addressing
b. Horner’s rule
c. linear probing
d. inverse probing
16. The process of enlarging a hash table and computing new hash indices for its contents is called
a. re-probing
b. de-hashing
c. inverse hashing
d. re-hashing
17. You define a hash table so that each location table[i] is itself an array. This array is referred
to as a(n)
a. bucket
b. bracket
c. closet
d. shelf
Chapter 18 Questions
True or False
1. To make an intelligent choice among various possible dictionary implementations, you must
analyze the efficiency with wich each supports the dictionary operations
2. The getValue(searchKey) method for an ADT dictionary retrieves the specified search key
for a given value.
3. The client code should not be able to modify an entry’s search key once that entry is in the
dictionary.
4. An ADT dictionary should never allow duplicate search keys
5. The traverse method visits all dictionary entries.
6. A dictionary must store and form an association between search key and data value only for a
sorted version of the dictionary, not for unsorted.
7. A linear link-based implementation of the ADT dictionary does not need to shift data for an add
or a remove operation.
8. A linear link-based implementation of the ADT dictionary supports addition and removel
operations more efficiently than an array-based implementation.
9. A binary search tree implementation of the ADT dictionary is nonlinear.
10. In the ArrayDictionary class, we must sort the items each time traverse is called.
11. The binary search tree implementation of the ADT dictionary has a binary search tree as a data
member.
12. The add method for the template for TreeDictionary presented in the text does not allow
for duplicate entries.
13. It is important to know both what operations are needed for a given application of an ADT
dictionary and how often each operation is required.
Chapter 18 Questions
14. A sorted array-based implementation of the ADT dictionary cannot use a binary search.
15. A binary search is impractical with a link-based implementation of the ADT dictionary.
16. An implementation of the ADT dictionary using a binary search tree is a poor choice for retrieval
dominate applications.
17. Because linear implementations are easy to understand conceptually they are appropriate for
dictionaries that will only contain a small number of entries.
18. According to the text, if the size of a problem is small, the difference in efficiency among
possible solutions is likely insignificant.
19. If the size of a dictionary is small, a linear implementation is inadequate and difficult to
understand.
20. A perfect hash function maps each search key into a unique location of the hash table.
21. It is insufficient for hash functions to operate only on integers.
22. Digit selection does not distribute entries in the hash table.
23. Quadratic probing causes no clustering at all.
24. Double hashing drastically reduces clustering.
25. With separate chaining, the size of the dictionary is dynamic and can exceed the size of the hash
table.
26. On average, quadratic probing and double hashing require more comparisons than linear probing.
27. Dictionary traversal is inefficient when using hashing.
Chapter 18 Questions
Short Answer
1. Consider sorting a group of people based on their zip code. This criteria is known as a(n)
________________.
2. What are two other names for the ADT dictionary?
3. An entry in an ADT dictionary is sometimes known as a(n) _________________ pair.
4. What are two possible things that could be done if a new entry’s search key already exists in the
dictionary?
5. What happens when the search key of an existing entry in the dictionary is changed?
6. Name three categories of linear implementations of a dictionary.
7. What must a sorted linear array-based implementation of the ADT dictionary do during an
addition and when removing an entry?
8. The header file for a class of dictionary entries, called Entry, overloaded what two operators?
9. When does use of the binary search tree implementation of the ADT dictionary become less
efficient?
10. Name two reasons for studying the linear implementations of an ADT dictionary?
11. A hash function maps an integer into a(n) _______________________.
12. When is a perfect hash function possible?
13. What are two requirements for a hash function?
14. Use modulo arithmetic to determine the index for a key 1234 for a table of 101 entries.
Chapter 18 Questions
15. When using linear probing, what must be done when removing a dictionary item so that later
hashing and linear probing still work correctly?
16. What does primary clustering cause?
17. You have 650 table entries in a hash table with size of 1500. What is the load factor?
18. Name three major concerns which constitute a good hash function.