NAME:                                                 PRECEPT #: Midterm Exam 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 this examination.''

```         1.   ___/13

2.   ___/6

3.   ___/9

4.   ___/8

5.   ___/8

6.   ___/8

7.   ___/16

8.   ___/10

9.   ___/11

10.   ___/10

TOTAL:   ___/99
```

#### NAME:

1. (13 points)

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

```

2. (6 points)

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

#### NAME:

3. (9 points)

Draw the binomial queue that results when you insert the keys

```          I  G  E  A  D  C  B  F  H
```
in that order into an initially empty queue. Use left-heap-ordered power-of-2 trees. Circle your final answer.

4. (8 points)

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

#### NAME:

5. (8 points)

Draw the tree that results when you first insert the keys

```          J  E  F  A  D  K  G
```
in that order into an initially empty binary search tree using the standard algorithm, then insert H using splay insertion.

#### NAME:

6. (8 points)

Draw the binary trie corresponding to the keys below

```    110100  010  00110  110101  10  0110
```
Circle your final answer.

7. (16 points)

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

```

#### NAME:

8. (10 points)

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  3
```
a. (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  F
```
b. (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 _______________________
```

#### NAME:

9. (11 points)

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  G
```
Hint: 7! = 5040.

b. (3 points) Circle the sequences from the following list that produce the same BST as

```          A  E  F  G  B  D  C
```
when 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  C
```
c. (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  C
```
Circle your final answer.

10. (10 points)

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

```