Short Answers Section 12.1 Serial Search and Binary Search |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Suppose 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 15Suppose 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
void Table::remove(int key) { Node cursor; size_t i; 1. i = hash(key); 2. Make cursor point to the node that contains an item with the given key (or set it to NULL if there is no such node). 3. if (cursor != NULL) { 3a. _____________________________________________________________ 3b. _____________________________________________________________ }
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) { return (key % CAPACITY); }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
Data Structures and Other Objects Using C++
Thank you for visiting
http://www.cs.colorado.edu/~main/questions/chap12q.html
Copyright © 2000
Addison-Wesley Computer and Engineering Publishing Group