CSCI 3300
Spring 2009
Exercises for Quiz 12

Work the exercises for quiz 11 again. Similar questions will be on quiz 12 too. Here are some additional questions.

1. Which of the following is true about log₂(1500)?

   1. 6 < log₂(1500) < 7
   2. 8 < log₂(1500) < 9
   3. 10 < log₂(1500) < 11
   4. 250 < log₂(1500) < 251
   5. 499 < log₂(1500) < 501

   Answer

2. To within a constant factor, how much time does it take, on average, to look up a value into a hash table that has n values in it?

   Answer

3. To within a constant factor, how much time does it take, on average, to insert a value into a hash table that has n values in it?

   Answer

4. Would a hash table be a useful tool for sorting an array? Why or why not?

   Answer

5. Suppose that a linked list is used to store a set of numbers. If there are n numbers in the list, how long, to within a constant factor, does it take to check whether a given number is in the list, in the worst case?

   Answer

6. Write a C++ definition of function insert(x, L) that inserts x into linked list L, modifying list L. It does not matter where in the list x ends up. It can be at the beginning or at the end or anywhere in between. The heading should be

     void insert(int x, Cell*& L)
   

   Type Cell is shown at the bottom of the page.

   Answer

7. Write a C++ definition of function remove(x, L) that removes the first occurrence of x from linked list L, modifying list L. If x does not occur in L, then remove(x, L) should not make any changes. There should be no memory leak. The heading should be

     void remove(int x, Cell*& L)
   

   Answer

    struct Cell
    {
      Cell* next;
      int item;

      Cell(int i, Cell* n)
      {
        item = i;
        next = n;
      }
    };