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
0 _____/ 5 1 _____/12 2 _____/ 8 3 _____/10 4 _____/10 5 _____/10 6 _____/10 7 _____/13 8 _____/12 9 _____/10 TOTAL _____/100
_______ 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
R E D S O Xare 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.
R E D S O Xare inserted in that order into an initially empty tree, using the root insertion method.
peter piper picked a peck of pickled peppersare inserted in that order into an initially empty TST.
_______ 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)
_______ 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
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