Sample Data Structures Questions

Sample Data Structures Questions
Chapter 12
Searching

Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch
Second Edition ISBN 0-201-70297-5, Softcover, 816 pages, 2000

The Purpose of These Questions

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

Short Answers
Section 12.1
Serial Search and
Binary Search

Here is an array with exactly 15 elements:
```
 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.
Here is an array with exactly 15 elements:
```
 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.

Implement the body of the following function using a binary search of the array. You do not need to check the precondition. All your local variables must be size_t variables.

    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

Draw a hash table with open addressing and a size of 9. Use the hash function "k%9". Insert the keys: 5, 29, 20, 0, 27 and 18 into your table (in that order).
Suppose you are building an open address hash table with double hashing. The hash table capacity is n, so that the valid hash table indexes range from 0 to n. Fill in the blanks:
- In order to ensure that every array position is examined, the value returned by the second hash function must be ________________________ with respect to n.
- One way to ensure this good behavior is to make n be _______________, and have the return value of the second hash function range from _________ to _________ (including the end points).
Short Answers
Section 12.3
Chained
Hashing

You are writing code for the remove member function of a chained hash table. Fill in the blanks in this pseudocode with the two missing statements. You may use pseudocode yourself, or write actual C++ code:

    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. _____________________________________________________________
           }

Draw a hash table with chaining and a size of 9. Use the hash function "k%9" to insert the keys 5, 29, 20, 0, and 18 into your table.
Suppose that I have the following record_type definition for a record in a hash 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
Suppose that an open-address hash table has a capacity of 811 and it contains 81 elements. What is the table's load factor? (An appoximation is fine.)
I plan to put 1000 items in a hash table, and I want the average number of accesses in a successful search to be about 2.0.
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

Multiple Choice
Section 12.1
Serial Search and
Binary Search

What is the worst-case time for serial search finding a single item in an array?
- A. Constant time
- B. Logarithmic time
- C. Linear time
- D. Quadratic time
What is the worst-case time for binary search finding a single item in an array?
- A. Constant time
- B. Logarithmic time
- C. Linear time
- D. Quadratic time
What additional requirement is placed on an array, so that binary search may be used to locate an entry?
- A. The array elements must form a heap.
- B. The array must have at least 2 entries.
- C. The array must be sorted.
- D. The array's size must be a power of two.
Multiple Choice
Section 12.2
Open-Address
Hashing
What is the best definition of a collision in a hash table?
- A. Two entries are identical except for their keys.
- B. Two entries with different data have the exact same key.
- C. Two entries with different keys have the same exact hash value.
- D. Two entries with the exact same key have different hash values.
Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:
- A. Hash table size should be the product of two primes.
- B. Hash table size should be the upper of a pair of twin primes.
- C. Hash table size should have the form 4K+3 for some K.
- D. Hash table size should not be too near a power of two.
In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which function has a better implementation because of this difference?
- A. insert
- B. is_present
- C. remove
- D. size
- E. Two or more of the above functions
What kind of initialization needs to be done for an open-address hash table?
- A. None.
- B. The key at each array location must be initialized.
- C. The head pointer of each chain must be set to NULL.
- D. Both B and C must be carried out.
Multiple Choice
Section 12.3
Chained
Hashing
What kind of initialization needs to be done for an chained hash table?
- A. None.
- B. The key at each array location must be initialized.
- C. The head pointer of each chain must be set to NULL.
- D. Both B and C must be carried out.
A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?
- A. 256
- B. 511
- C. 512
- D. 1024
- E. There is no maximum.
Multiple Choice
Section 12.4
Time Analysis
of Hashing
Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?
- A. s + m
- B. s - m
- C. m - s
- D. m * s
- E. m / s

Data Structures and Other Objects Using C++

Michael Main (main@colorado.edu)
and
Walter Savitch (wsavitch@ucsd.edu)