Closed book. 8-1/2 X 11" crib sheet is allowed.
1.
Consider this skip list. What is the resulting skip list after insert(32),
with
the random number generator providing: 1, 1, 0 for the tower building
(1 means
continue to build tower, 0 means stop building tower).
2. a. Given this splay tree, what is resulting splay tree after insert(32)?
splay tree 1
2. b. Given this splay tree, what is resulting splay tree after find(25)?
splay tree 2
| key | hash |
|---|---|
| 5 | 5 |
| 10 | 5 |
| 15 | 3 |
| 20 | 2 |
| 25 | 2 |
| 30 | 6 |
| 35 | 6 |
| 40 | 9 |
| 45 | 9 |
| 50 | 6 |
The starting table is:
| index | data |
|---|---|
| 0 | |
| 1 | |
| 2 | 20 |
| 3 | 25 |
| 4 | |
| 5 | 5 |
| 6 | 10 |
| 7 | # |
| 8 | # |
| 9 | 40 |
insert(35)
delete(10)
insert(50)
insert(45)
delete(40)
| index | data |
|---|---|
| 0 | |
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 |
4. Consider this 2, 3, 4 tree. What is the tree after insert(25)?
Hint: There will an overflow at the leaf <21,22, 29>
13
/ \
/ \
/ \
5 10 20 30 40
/ | \ / | | \
/ | \ / / | \
1, 2 6, 9 11, 12 14, 15, 18 21, 22, 29 35, 36 50, 60
5. Fill in the trace for executing (an internal) merge sort on the following
data:
2, 15, 8, 7, 1, 6, 13, 3
2, 15, 8, 7, 1, 6, 13, 3
___________________________
/ \
________ ________
/ \ / \
____ ____ ____ ____
/ \ / \ / \ / \
__ __ __ __ __ __ __ __
\ / \ / \ / \ /
____ ____ ____ ____
\ / \ /
________ ________
\ /
1, 2, 3, 6, 7, 8, 13, 15
__________________________
6. Repeat #5 for quick sort. The pivot selected is always the initial element
of the sequence.
7. You are given sequences of length 2 of decimal 10 integers. Show the phases
of radix sort from
initial unsorted sequence to final sorted sequence.
Unsorted sequence: 2, 15, 78, 7, 1, 6, 12, 5, 8
101. Is this a valid skip list?
-∞ ------------------------------------------------------ +∞ -∞ -----------14-------------------------36-------------- +∞ -∞ ---------------------25---------------36-------------- +∞ -∞ -----------14--------25----26---30----36-------------- +∞
102. A proposed hash function of a String is the Unicode value of the most common
character in the String.
If two or more characters have the same number of appearances, then the first
character in the String is used.
This is a bad hash function, leading to multiple collisions.
Why is this a bad hash function?
103. Which expression finds the correct index into the hash table size 64:
a. hash(key) % 10
b. hash(key) % 2
c. hash(key) % 64
d. hash(key) % key
104. Suppose you have a horrible hash function h(key) = 2, so all data values
hash to the same location. You are hashing using chaining for collision
resolution. The chain is an unsorted linked list. What is the Big Oh for
find one element in this situation?
a. O(1)
b. O(log n)
c. O(n)
d. O(n log n)
e. O(n2)
105. Suppose you are doing quick sort on this sequence:
2, 15, 8, 7, 1, 6, 13, 3
The pivot selection is median of the first 3 elements.
What is the first pivot chosen?
a. 2
b. 15
c. 8
d. (floor) ((2 + 15 + 8) / 3.0) = 8.0
e. 6.5