Short Answers Section 12.1 Serial Search and Binary Search |
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).
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
void Table
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
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