Last name: _____________________
Given name: ____________________
CSE373 Winter 2005 with notes
Miniquiz #6
Feb. 16, 2005
11 pts. total
Notes are minimal, since we went over all the questions in class
1. (2 pts.) What is the asymptotic complexity of
Heapsort? Explain.
Time complexity: N log(N).
The completeness property is what gives us the log(N) part of it, as it
guarantees the height of the tree is very nearly log(N).
2. The following array represents a heap ('x' means unused.)
(1 pt.) Is it a min-heap or a max-heap? min
(2 pts.) Show the result (in the
array)
of performing one delMin (dequeue) operation.
index
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
value
|
x
|
11
|
22
|
19
|
23
|
50
|
29
|
22
|
30
|
x
|
x
|
"30" is moved into the root (1) and percolated down.
3. In a banking database, the customer records are stored in a hash
table of size 10. The hash is computed by taking the first 2
digits of the account number mod 10. Customers are added to an
initially empty table in the following order:
23488 90378 30911 46011
52001 41777
(2 pts) Draw the table as it looks if chained hashing is used:
(2 pts.) Draw the table as it looks if open addessing (with linear
probing, the only type shown in lecture) is used:
A number of collisions result, so by the time you insert 41777, it is a couple of slots away from its home address.
4. (2 pts.) Draw the tree that results from adding these values
(in the order shown) to an initially empty binary search tree:
6 18 20
15 21 19