CSCI 3300
Fall 2009
Exercises for Quiz 11

1. How much time does Quicksort take to sort an array of n integers in the average case?

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

   Answer

2. How much time does Quicksort take to sort an array of n integers in the worst case?

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

   Answer

3. Types Cell and Node are shown at the bottom of the page, where Cell is the cell type for a linked list of integers and Node is the node type for a binary search tree. Write a function that takes a binary search tree T and returns a linked list of all of the numbers in T, in ascending order.

   Do this by writing a helper function treeToListHelp(T, L) that returns all numbers in tree T, in ascending order, followed by list L. For example, if L = [18, 19, 20] and T holds numbers 4, 8 and 14 (in some structure), then treeToListHelp(T, L) returns list [4, 8, 14, 18, 19, 20]. Then write function treeToList in terms of treeToListHelp.

     Cell* treeToListHelp(Node* T, Cell* L)
     {
     }
   
     Cell* treeToList(Node* T)
     {
     }
   

   Answer

    struct Cell
    {
      Cell* next;
      int item;

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

    struct Node
    {
      int item;
      Node* left;
      Node* right;
      Node(int i, Node* L, Node* R)
      {
        item = i;
        left = L;
        right = R;
      }
    };