NAME:

Midterm Exam		 March 10, 1999

Computer Science 226

This test is 10 questions for a total of 96 points, 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.   ___/20

         2.   ___/7

         3.   ___/7

         4.   ___/7

         5.   ___/7

         6.   ___/7

         7.   ___/7

         8.   ___/7

         9.   ___/7

        10.   ___/20

     TOTAL:   ___/96












NAME:



1. (25 points) Match each of the given sorting algorithms with one of its most important features. Write the letter corresponding to your answer in the blank to the left of the name of the sorting method. In some cases, more than one answer might be argued, but you must put only one letter per algorithm. If you pick the best matches, you will use all the letters. 

  ___ insertion sort              A. best for linked lists

  ___ selection sort              B. fastest when keys and records are small

  ___ heapsort                    C. best for string keys

  ___ mergesort                   D. fastest all-purpose sort

  ___ Batcher's sort              E. best for nearly-ordered files

  ___ quicksort                   F. fastest on a multiprocessor

  ___ LSD radix sort              G. asymptotically optimal (time and space)

  ___ MSD radix sort              H. best for small number of huge records
2. (7 points) Which of the following does not represent a heap-ordered complete binary tree? Circle your answer. 
               1  2  3  4  5  6  7
              ---------------------
          A.   G  F  E  D  C  B  A
          B.   G  F  E  A  B  C  D
          C.   G  D  F  A  C  B  E
          D.   G  F  D  A  C  E  B
          E.   G  E  F  A  C  B  D
          F.   G  C  F  A  B  D  C













NAME:



3. (7 points) Draw the binomial queue that results when you insert the keys 
          G  F  E  D  C  B  A  H  I
in that order into an initially empty queue. Use left-heap-ordered power-of-2 trees.


















4. (7 points) Draw the red-black tree that results when you perform top-down insertion of the keys 
          G  F  E  D  C  B  A  H  I
in that order into an initially empty tree.

















NAME:



5. (7 points) Draw the binary search tree that results when you insert the keys 
          G  F  E  D  C  B  A  H  I
in that order into an initially empty tree, using the root insertion method.


















6. (7 points) Draw the splay tree that results when you insert the keys 
          H  G  F  E  D  C  B  A  I  J
in that order into an initially empty tree.

















NAME:



7. (7 points) Draw the binary trie that results when you insert the keys 
    0101  0100  0011  0010  0001  1000  1001
in that order into an initially empty trie.


















8. (7 points) Draw the Patricia trie that results when you insert the keys 
    0101  0100  0011  0010  0001  1000  1001
in that order into an initially empty trie.

















NAME:



9. (7 points) Draw the linear-probing hash table that results when you insert the keys 
  19  6  16  8  5  13  1
in that order into an initially empty table. Use a table of size 11 and the hash function
h(x) = 3x + 4 (mod 11).

















10. (25 points) Match each of the given symbol-table implementations with one of its most important features. Write the letter corresponding to your answer in the blank to the left of the name of the method. In some cases, more than one answer might be argued, but you must put only one letter per algorithm. If you pick the best matches, you will use all the letters. 

  ___ splay trees                 A. best use of space

  ___ separate-chaining hashing   B. best for long string keys

  ___ skip lists                  C. quadratic worst case construction cost

  ___ red-black trees             D. optimal search (bits examined)

  ___ double hashing              E. amortized performance guarantee

  ___ Patricia tries              F. constant-time insert

  ___ binary search trees         G. optimal search (comparisons)

  ___ 3-way radix search tries    H. randomized performance guarantee