|
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 G
4.
E
/ \
B H
/ \ / \
A D F J
// \\ //
C G I
5.
H
/ \
E J
/ \ \
A G K
\ /
D F
6.
.....
/ \
. .
/ \ / \
00110 . 10 .
/ \ / \
010 0110 .
/ \
.
/ \
.
/ \
110100 110101
7. (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 key
8.
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 C
b.
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 G
9.
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