Sample Data Structures Questions
Chapter 11
Searching

Data Structures and Other Objects Using Java (Third Edition)
by Michael Main
ISBN 0-321-37525-4

The Purpose of These Questions

These are typical exam questions from Chapter 11 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 11.1
    Serial Search and
    Binary Search

  1. 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.

  2. 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.

  3. Implement the body of the following function using a binary search of the array. You do not need to check the precondition. 
        public static boolean has42(int[ ] data, int start, int end)
    // Precondition: The elements data[start]...data[end] are sorted from smallest
    // to largest. This array segment might be empty (indicated by end being less
    // than start).
    // Postcondition: A true return value indicates that the number 42 appears in
    // data[start]...data[end]. A false return value indicates that 42 doesn’t 
    // appear.

    Short Answers
    Section 11.2
    Open-Address
    Hashing

  4. 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).

  5. 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:

    Short Answers
    Section 11.3
    Chained
    Hashing

  6. You are writing code for the remove method 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 Java code: 
        public void Table remove(Object key)
    {
       ChainedHashNode cursor;
       int i;

       1. i = key.hashCode( );

       2. Make cursor refer 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. _____________________________________________________________
          }

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

  8. Suppose that I have the following private instance variables for an open-address hash table: 
        public class Table
    {
       private int manyItems;
       private Object[ ] keys;
       private Object[ ] data;
       private boolean[ ] hasBeenUsed;
       ...
    The hash table uses open addressing with linear probing. A location [i] of the table that has NEVER been used will have hasBeenUsed[i] set to false. Other locations have hasBeenUsed[i] set to true. Complete the implementation of the following method of the Table class. There is no need to check the precondition, but your code must be as efficient as possible. 
    public boolean containsKey(Object key)
// Postcondition: If key occurs as a key of a record in the table, then
// the method returns true; otherwise the method returns false.

    Short Answers
    Section 11.4
    Time Analysis
    of Hashing

  9. 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.)

  10. 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 11.1
    Serial Search and
    Binary Search

  1. What is the worst-case time for serial search finding a single item in an array?

  2. What is the worst-case time for binary search finding a single item in an array?

  3. What additional requirement is placed on an array, so that binary search may be used to locate an entry?

    Multiple Choice
    Section 11.2
    Open-Address
    Hashing

  4. What is the best definition of a collision in a hash table?

  5. Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:

  6. 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 method has a better implementation because of this difference?

  7. What kind of initialization needs to be done for an open-address hash table?

    Multiple Choice
    Section 11.3
    Chained
    Hashing

  8. What kind of initialization needs to be done for an chained hash table?

  9. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?

    Multiple Choice
    Section 11.4
    Time Analysis
    of Hashing

  10. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?


Michael Main (main@colorado.edu)