|
March 14, 2001 Computer Science 226 |
CDE insertion sort A. linear extra space
DG selection sort B. optimal average running time
BF heapsort C. linear best-case running time
D bubblesort D. quadratic worst-case running time
ABF mergesort E. linear for nearly-ordered files
BD quicksort F. optimal worst-case running time
shellsort G. quadratic best-case running time
58. Heap has depth 7. All nodes on path from bottom node to root must be greater than bottom node, but path could be 64-63-62-61-60-59-58.
3. (7 points) Draw the binomial queue that results when you insert the keys
A F E D C B G H I
in that order into an initially empty queue. Use left-heap-ordered
power-of-2 trees.
H I
/
F
/ \
E C
/ \ / \
D A B G
4. (7 points) Draw the red-black tree that results when you perform top-down insertion of the keys
A F E D C B G H I
in that order into an initially empty tree.
E
// \\
C G
/ \ / \
A D F H
\\ \\
B I
5. (7 points)
Draw the binary search tree that results when you insert the keys
A F E D C B G H I
in that order into an initially empty tree,
using the root insertion method.
I
/
H
/
G
/
B
/ \
A C
\
D
\
E
\
F
6. (7 points)
Draw the splay tree that results when you insert the keys
A G F E D C B H I J
in that order into an initially empty tree.
J
/
I
/
H
/
C
/ \
B E
/ / \
A D G
/
F
7. (7 points)
Draw the binary trie that results when you insert the keys
1101 0100 0011 0010 0001 1000 1001
in that order into an initially empty trie.
...........
/ \
. .
/ \ / \
. 0100 . 1101
/ \ / \
0001 . .
/ \ / \
0010 0011 1000 1001
8. (7 points)
Draw the Patricia trie that results when you insert the keys
1101 0100 0011 0010 0001 1000 1001
in that order into an initially empty trie.
_______
1101(0) \
/ \ \
/ \ \
0100(1) -> 1000(1) |
/ / \ / / \__/
/ \_/ / /
0011(2)_ _ _ / 1001(3)
/ \ \ | / / \
/ \ | |__/ \_/
0001(3) 0010(3) |
/ / \ / \ \ |
/ \_/ \ / \_|
.
9. (5 points)
Why not use a hash function like If the first hash function hashes to a filled slot and h2(v) = 0, then you get stuck in an infinite loop.
10. (10 points)
a. (3 points)
Circle the sequences from the following list that produce the same
BST as
C E A G B D F
C
/ \
A E
\ / \
B D G
/
F
when inserted in the order given into an initially empty tree.
C A B E G D F
C A E G D B F
C E B G A D F No. B comes before A.
C E G A F D B
C E G D F A B
E A G B D F C No. E comes before C.
b. (7 points)
How many of 7! = 5040 orders in which to insert the keys produce the
same tree as
C E A G B D F
when inserted into an initially empty tree?
The first node is C. We first consider the number of ways to
build the two subtrees EDGF and AB independently.
There are 3 ways to construct the subtree EDGF and 1 way to construct
the subtree AB.
Instead, let's consider what happens if we fix the ordering
of the two subtrees, e.g, AB and EGDF. Then, we can build the whole
BST by interleaving these two orderings in any way, e.g.,
ABEGDF, AEGDFB, EABGDF, etc. If you've taken a probability course,
you might remember that the formula for the number of
ways is 6! / (2! * 4!) = 15. (Alternatively, you could enumerate
them all.)
Since there is only 1 legal ordering of the subtree AB and 3 legal
orderings of the subtree EDGF, the total number is 15 * 3 * 1 = 45.
11. (10 points)
Match each of given search-tree structures with the function
that best describes the absolute value of the difference between
the depths of two leaves in the tree.
Write the letter corresponding to your answer
in the blank to the left of the name.
C splay tree A. O(1) B red-black tree B. O(log N) C BST C. O(N)