March 13, 2002|
Computer Science 226
This test is 10 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
1. ___/13 2. ___/6 3. ___/9 4. ___/8 5. ___/8 6. ___/8 7. ___/16 8. ___/10 9. ___/11 10. ___/10 TOTAL: ___/99
Match up each sorting algorithm below with the term on the right that
best describes the average number of key comparisons it
uses to sort a randomly ordered file of 1 million distinct elements.
_______ insertion sort A. N lg N _______ selection sort B. 2N ln N _______ heapsort C. 2N lg N _______ mergesort D. N^(3/2) _______ quicksort E. N^2 / 4 _______ shellsort (with Knuth sequence) F. N^2 / 2
Suppose that there are N distinct elements in a binary heap (with the maximum at the root). Which positions could possibly be occupied by the fourth largest element? Circle all that apply.
A. 1 B. 2 or 3 C. 4, 5, 6, or 7 D. 8 through 15 E. 16 and higher
Draw the binomial queue that results when you insert the keys
I G E A D C B F Hin that order into an initially empty queue. Use left-heap-ordered power-of-2 trees. Circle your final answer.
Draw the red-black tree that results when you perform top-down insertion of the keys
J H F B E D A C G Iin that order into an initially empty tree. Denote red links by extra-thick lines. Circle your final answer. Hint: the tree after the first 6 insertions is:
H // \ E J / \ B F \\ D
Draw the tree that results when you first insert the keys
J E F A D K Gin that order into an initially empty binary search tree using the standard algorithm, then insert H using splay insertion.
Draw the binary trie corresponding to the keys below
110100 010 00110 110101 10 0110Circle your final answer.
Match each of the given search data structures 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.
_______ binary trie A. tree/trie shape not dependent on the order in which keys are inserted _______ digital search tree B. exactly two links per key _______ Patricia trie C. key values in nodes not dependent on the order in which keys are inserted _______ binary search tree D. inorder traversal gives sorted order _______ red-black tree E. worst-case search time = O(log N) where N is the number of keys F. worst-case search time = O(L) where L is the number of digits in search key
Suppose that the following keys, with the given hash values, are inserted into an initially empty table of size 7 using linear-probing hashing.
key: A B C D E F G hash: 3 5 3 4 5 6 3a. (3 points) Circle the lines on the list below that could not possibly result from inserting these keys, no matter in which order they are inserted.
0 1 2 3 4 5 6 --------------------- E F G A C B D C E B G F D A B D F A C E G C G B A D E F F G B D A C E G E C A D B Fb. (7 points) Give the minimum and the maximum number of probes that could be required build a table of size 7 with these keys, and an insertion order that justifies your answer.
minimum _____ order _______________________ maximum _____ order _______________________
a. (1 points) Give the fraction of permutations of the keys A through G that will, when inserted into an initially empty tree, produce the same BST as does
A B C D E F GHint: 7! = 5040.
b. (3 points) Circle the sequences from the following list that produce the same BST as
A E F G B D Cwhen inserted in the order given into an initially empty tree.
A C B E G D F A F E G D B C A E B G C D F A E G C F D B A E G D C B F E A G B D F Cc. (7 points) Give the fraction of permutations of the keys A through G that will, when inserted into an initially empty tree, produce the same BST as does
A E F G B D CCircle your final answer.
Suppose that you do a search in a red-black tree that terminates unsuccessfully after following 20 links from the root. Fill in the blanks below with the best (integer) bounds that you can infer from this fact about any unsuccessful search
must follow at least ______ links from the root need follow at most _______ links from the root