| 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
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 H
in 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 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
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.
Draw the binary trie corresponding to the keys below
110100 010 00110 110101 10 0110
Circle 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 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 _______________________
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.
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