These are typical exam questions from Chapter 12 of the textbook. These exact questions might not be on your exam, but if you research and find the right answers to these questions, that should be good preparation for a real exam. (It's also possible that some of this material was not covered in your class.) At the moment there are 10 short answer questions and 10 multiple choice questions in this file.
| Short Answers Section 12.1 Serial Search and Binary Search |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Suppose that we are doing a serial search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Suppose that we are doing a binary search for an element. Circle any elements that will be found by examining two or fewer numbers from the array.
bool has_42(const int data[ ], size_t n) // Precondition: The elements data[0]. data[n-1] are sorted from smallest // to largest. The value of n might be zero (indicating an empty // array). // Postcondition: A true return value indicates that the number 42 appears in // data[0]. data[n-1]. A false return value indicates that 42 doesn�t appear.
| Short Answers Section 12.2 Open-Address Hashing |
| Short Answers Section 12.3 Chained Hashing |
struct record_type < int key; . other stuff may also appear here . >;
The hash table uses open addressing with linear probing. The table size is a global constant called CAPACITY. Locations of the table that have NEVER been used will contain the key -1. Locations of the table that were once used but are now vacant will contain the key -2. All valid keys will be non-negative, and the hash function is:
size_t hash(int key)Complete the implementation of the following function. There is no need to check the precondition, but your code must be as efficient as possible.
bool key_occurs(const record_type data[ ], int search_key) // Precondition: data[0]. data[CAPACITY-1] is an open address hash table // as described above. // Postcondition: If search_key occurs as a key of a record in the table, then // the function returns true; otherwise the function returns false.
| Short Answers Section 12.4 Time Analysis of Hashing |
A. About how big should the array be if I use open addressing with linear probing? NOTE: For a load factor of A , the average number of accesses is generally ½(1+1/(1- A )).
B. About how big should the array be if I use chained hashing? NOTE: For a load factor of A , the average number of accesses is generally (1+ A /2).
| Multiple Choice Section 12.1 Serial Search and Binary Search |
| Multiple Choice Section 12.2 Open-Address Hashing |
| Multiple Choice Section 12.3 Chained Hashing |
| Multiple Choice Section 12.4 Time Analysis of Hashing |