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