CSCI 3300
Fall 2009
Exercises for Quiz 10

1. An efficient algorithm that implements a priority queue uses how much time per insert or remove operation, in the worst case?

   1. O(1)
   2. O(log₂(n))
   3. O(n)
   4. O(n log₂(n))
   5. O(n²)

   Answer

2. To within a constant factor, how long does Heapsort take to sort an array of n numbers, in the worst case?

   Answer

3. Is it possible to create an implementation of binary search trees that is nondestructive (so that it builds new trees rather than modifying existing trees) or must every implementation of binary search trees work by making modifications to existing data structures?

   Answer

4. If an algorithm sorts a list of n values by using comparisons, then, to within a constant factor, in the worst case, that algorithm must use at least

   1. log₂(n) comparisons.
   2. n/log₂(n) comparisons.
   3. n comparisons.
   4. n log₂(n) comparisons.
   5. n² comparisons.

   Answer

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

6. 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;
      }
    };