Midterm Exam Solutions
 March 13, 2002 Computer Science 226

1.
```E   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

```
2. B, C, D

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
```