Last name: _____________________
Given name: ____________________
CSE373 Winter 2005
Miniquiz #5
Feb. 9, 2005
1 pt. per part unless noted
(16 pts. total)
1. (4 pt.) Draw (as a tree) the heap that results
from inserting the following elements, in the order shown, into an
initially empty (min) heap.
30 50 2 7
19 1
The final heap, as an array, would be
(x) 1 7 2 50
19 30
Scoring: -1 for each incorrect entry, up to -4
2. (2 pts.) Does the array represent a (min) heap? If "no",
explain exactly why not. If "yes", then show the result (in the
array)
of performing one delMin (dequeue) operation. ('x' means unused.)
index
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
value
|
x
|
11
|
22
|
19
|
23
|
50
|
21
|
18
|
30
|
x
|
x
|
Not a heap. The node at position 3 (value
19) has a child at position 7 with a smaller value (18). This is
the only place where the heap property fails.
3. Suppose in a data base for a small college, each student has a
unique ID which is random integer less than 1,000,000. Suppose
there are never more than 500 students. A hashing scheme is to be
used for the student records. Call the table (array) size k.
a. (2 pts.) If you had to pick k from these choices: 999,
1000, 1001, 1002; which would you pick and why?
Other factors being equal, picking a prime number
is a better choice. 1001 is not actually a prime, it turns
out! (I thought it was when I wrote the question). If you
choose 1001 because it looked prime, or even mentioned "prime", you get
the points. Otherwise, we would have to read your answer to see
if there is any good argument in it.
b. (2 pts.) what would be a simple but plausible mapping from a student
record
to a table position?
ID % k
ID is a good starting point since it is unique
per student. Since the IDs are already randomly distributed over
a large range, there is no need for a further
randomization. % k is always the last step in a
mapping, and in this case it is sufficient.
4. Identify each of the following methods as to whether it is required
in
the Model, View, or Control of Homework 3:
a. start(int, int) Model
b. getDiskList(int) Model
c. startUp( ) Control
5. Yes/No
a. You are supposed to implement your own version of TowerStarter No
b. You can define as many non-public methods as you like in TowerView Yes
c. You can modify and turn in ITowerController No