NAME:

Midterm Exam		 March 11, 1998

Computer Science 226

This test is 11 questions, weighted as indicated. Do all of your work on these pages (use the back for scratch space), giving the answer in the space provided. Put your name on every page (now), and write out and sign the Honor Code pledge before turning in the test.

``I pledge my honor that I have not violated the Honor Code during this examination.''





1. (50 points) Fill in the following table. Express running times as a function of the number of items, N, to within a constant factor for large N. Assume that the items to be sorted are 64-bit integers, stored in an array. 
                                running time                        
                         worst      best      average     stable?    inplace?


  insertion


  selection


  bubble


  shellsort
   1, 4, 13, ...

  heapsort


  mergesort


  Batcher's sort


  quicksort


  LSD radix sort


  MSD radix sort

NAME:



2. (5 points) Show the heap that results when the bottom-up construction method is used to build a heap from the keys 
          B E A T U N L V


















3. (5 points) Show the result of inserting the keys 
          B E A T U N L V
into an initially empty binomial queue.

















NAME:



4. (5 points) Draw the 2-3-4 tree that results when the keys 
          B E A T U N L V
are inserted in that order into an initially empty tree.

















5. (5 points) Draw the red-black tree that results when the keys 
          B E A T U N L V
are inserted in that order into an initially empty tree.

















NAME:



6. (5 points) Draw the binary search tree that results when the keys 
          B E A T U N L V
are inserted in that order into an initially empty tree, using the top-down insertion method.


















7. (5 points) Draw the splay tree that results when the keys 
          B E A T U N L V
are inserted in that order into an initially empty tree.

















NAME:



8. (5 points) Draw the binary trie that results when the keys 
  00010 00101 00001 10100 10101 01110 01100 10110
are inserted in that order into an initially empty trie.


















9. (5 points) Draw the Patricia trie that results when the keys 
  00010 00101 00001 10100 10101 01110 01100 10110
are inserted in that order into an initially empty trie.

















NAME:



10. (5 points) Double hashing requires that the increment and the table size be relatively prime. Describe two different ways to accomplish this.

















11. (5 points) Draw all the binary search trees that could be built from three randomly ordered items with the keys A B C, and give the probability of occurrence of each tree.