March 13, 2002 Computer Science 226 |
2. B, C, DE insertion sort A. N lg N F selection sort B. 2N ln N C heapsort C. 2N lg N A mergesort D. N^(3/2) B quicksort E. N^2 / 4 D shellsort (with Knuth sequence) F. N^2 / 2
3.
I H / F / \ D E / \ / \ C B A G4.
E / \ B H / \ / \ A D F J // \\ // C G I5.
H / \ E J / \ \ A G K \ / D F6.
..... / \ . . / \ / \ 00110 . 10 . / \ / \ 010 0110 . / \ . / \ . / \ 110100 1101017. (16 points)
ACDF binary trie A. tree/trie shape not dependent on the order in which keys are inserted BF digital search tree B. exactly two links per key ABDF Patricia trie C. key values in nodes not dependent on the order in which keys are inserted BD binary search tree D. inorder traversal gives sorted order BDE 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 key8.
a.
0 1 2 3 4 5 6 --------------------- E F G A C B D Yes. A C B D E F G C E B G F D A No. F before A B D F A C E G Yes. A C E G B D F C G B A D E F Yes. A D E F C G B F G B D A C E No. D before A G E C A D B F Yes. A D B F G E Cb.
minimum 20 order A B C D E F G 1 + 1 + 2 + 3 + 3 + 3 + 7 maximum 20 order A B C D E F G9.
a. 1 / 7! = 1/ 5040
b. None
c. 10
The BST is given below. The first two keys must be A followed by E. For the remaining keys, F must precede G and B must precede D which must precede C. There are 5! / (2! * 3!) = 10 ways to do this.
A \ E / \ B F \ \ D G / C
10.
In a red-black tree, every path from the root to a leaf has the same number of black links since these correspond to links in the underlying 2-3-4 tree. There cannot be two consecutive red links. Thus, the shortest possible path consists of only black links; the longest possible path consists of an alternating sequence of red and black links, starting and ending with red.
must follow at least 10 links from the root need follow at most 41 links from the root