NAME:

Midterm Exam		 March 14, 2001

Computer Science 226

This test is 11 questions for a total of 99 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.   ___/15

         2.   ___/8

         3.   ___/8

         4.   ___/8

         5.   ___/8

         6.   ___/8

         7.   ___/8

         8.   ___/8

         9.   ___/8

        10.   ___/10

        11.   ___/10


     TOTAL:   ___/99












NAME:



1. (25 points) Match each of the given sorting algorithms with one or more of the given characteristics. Write as many letters as apply in the blank to the left of the name of the sorting method. 




  _______ insertion sort         A. linear extra space

  _______ selection sort         B. optimal average running time

  _______ heapsort               C. linear best-case running time

  _______ bubblesort             D. quadratic worst-case running time

  _______ mergesort              E. linear for nearly-ordered files

  _______ quicksort              F. optimal worst-case running time

  _______ shellsort              G. quadratic best-case running time



2. (7 points) What is the largest key that could be at the bottom level of a heap built from the keys 1 through 64?


















NAME:



3. (7 points) Draw the binomial queue that results when you insert the keys 
          A  F  E  D  C  B  G  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 
          A  F  E  D  C  B  G  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 
          A  F  E  D  C  B  G  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 
          A  G  F  E  D  C  B  H  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 
    1101  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 
    1101  0100  0011  0010  0001  1000  1001
in that order into an initially empty trie.

















NAME:



9. (5 points) Why not use a hash function like h2(v) = v % 97 for the second hash function in double hashing?

















10. (10 points)
a. (3 points) Circle the sequences from the following list that produce the same BST as 
          C  E  A  G  B  D  F
when inserted in the order given into an initially empty tree. 
          C  A  B  E  G  D  F
          C  A  E  G  D  B  F
          C  E  B  G  A  D  F
          C  E  G  A  F  D  B
          C  E  G  D  F  A  B
          E  A  G  B  D  F  C
b. (7 points) How many of 7! = 5040 orders in which to insert the keys produce the same tree as 
          C  E  A  G  B  D  F
when inserted into an initially empty tree?

















NAME:



11. (10 points)
Match each of given search-tree structures with the function that best describes the absolute value of the difference between the depths of two leaves in the tree. Write the letter corresponding to your answer in the blank to the left of the name. 

  ___ splay tree                  A. O(1)
  
  ___ red-black tree              B. O(log N)

  ___ BST                         C. O(N)