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

```