**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)