NAME: Midterm Exam October 21, 2004 Computer Science 226

This test is 9 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.''

```
0 _____/ 5

1 _____/12

2 _____/ 8

3 _____/10

4 _____/10

5 _____/10

6 _____/10

7 _____/13

8 _____/12

9 _____/10

TOTAL _____/100

```

0. (5 points) Write your name on each page of this exam.

#### NAME:

1. (12 points) Match up each sorting algorithm below with a number on the right that is closest to the average number of times the standard implementation in the book stores an item when sorting a randomly ordered file of 1 million distinct items. (Count exchanges as 2.)

```  _______ insertion sort                          A.  2 million

_______ selection sort                          B.  10 million

_______ bubble sort                             C.  40 million

_______ mergesort                               D.  80 million

_______ quicksort                               E.  250 billion

_______ heapsort                                F.  1 trillion
```

2. (8 points) Show that heapsort is not stable.

#### NAME:

3. (10 points) Draw the top-down 2-3-4 tree that results when the keys
```          R  E  D  S  O  X
```
are inserted in that order into an initially empty tree, using the standard top-down algorithm. Then draw all red-black trees that correspond to that 2-3-4 tree, and circle the one that is constructed by the standard top-down algorithm.

4. (10 points) Draw the sequence of binary search trees that result when the keys
```          R  E  D  S  O  X
```
are inserted in that order into an initially empty tree, using the root insertion method.

#### NAME:

5. (10 points) Draw the TST that results when the keys
```  peter piper picked a peck of pickled peppers
```
are inserted in that order into an initially empty TST.

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

#### NAME:

7. (13 points) Match each of the given search data structures with one or more of the given characteristics, where N is the number of keys and L is the maximum number of digits in a key. Write as many letters (in alphabetical order) as apply in the blank to the left of the name of the data structure.

```
_______ M-ary trie             A. tree/trie shape not dependent on the order
in which keys are inserted

_______ TST                    B. about 2N links

_______ Separate chaining      C. key values in nodes not dependent on the
order in which keys are inserted

_______ BST                    D. inorder traversal gives sorted order

_______ red-black tree         E. worst-case search time = O(log N)

F. worst-case search time = O(L)

```

8. (12 points) Match each of the given sorting algorithms with one or more of the given characteristics. Write as many letters (in alphabetical order) as apply in the blank to the left of the name of the data structure.

```
_______ mergesort              A. slowed down in cache memory systems
because of excessive non-local references

_______ heapsort               B. uses extra space proportional to file size

_______ LSD radix sort         C. should handle small files differently

_______ MSD radix sort         D. must handle small files differently

_______ quicksort              E. much faster if file is in order

_______ selection sort         F. requires randomization to avoid quadratic
running time
```

#### NAME:

9. (10 points) The column on the left is the original input of strings to be sorted. The columns to the right are the contents at some intermediate step during a sorting algorithm. Match up each algorithm by writing its letter under the corresponding column. One letter should appear twice in your answer; the others should appear exactly once.
```bold | coma acme ache abet coma slab abet bold abet abet
cash | gala akin acne acid gala lady acid cash ache ache
coma | idea abet ajar acme idea fame acme acre acid acid
band | club acid band akin club knee acne band acme acme
club | slab ajar bold band slab fall ajar ache acne acne
acme | bold acne acme bold acid dawn akin acme acre acre
akin | band also akin cash bald fake band akin ajar ajar
abet | acid ache abet club bold idea bold abet akin akin
knee | bald acre bank coma band half cart bank also also
slab | acme bold bald fall acme club cash bald bald bald
fall | knee band acre knee ache debt cell chef band band
acid | fame bald acid slab acne city club acid bank bank
fame | acne bank also fame acre bold coma also fame fame
ajar | ache cash cell ajar else else fall ajar bold bold
cart | else coma chef cart fake coma fame cart cart cart
cell | fake club city cell fame cell gala cell cell cell
acne | acre cart chug acne knee dark knee acne club chef
gala | half cell cash gala chef gala slab chug gala chug
half | chef chef coma half half chug ache half half dark
also | chug city club also chug also acre fame knee fame
chef | cash chug cart chef cash chef also fall chef fall
debt | bank debt debt debt bank cash bald debt debt debt
bald | dark dawn slab bald dark bald bank slab slab coma
bank | fall dark knee bank cell bank chef knee coma fake
city | cell else idea city fall acid chug city city city
ache | akin fall lady ache akin ache city club cash club
dawn | dawn fame dawn dawn dawn acme dark dawn dawn dawn
else | also fake else else also akin dawn else else else
slaw | ajar gala slaw slaw ajar ajar debt slaw slaw gala
fake | abet half fake fake abet cart else fake fake knee
acre | cart idea fall acre cart acre fake coma fall slab
idea | debt knee fame idea debt abet half idea idea idea
lady | slaw lady half lady slaw band idea lady lady lady
dark | city slab gala dark city acne lady dark dark half
chug | lady slaw dark chug lady slaw slaw gala chug slaw
----   ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
A

A. Original input
B. 3-way radix quicksort
C. Heap sort
D. Insertion sort
E. LSD radix sort
F. Mergesort
G. MSD radix sort
H. Quicksort
I. Selection sort
J. none of the above
```