CSC 372
Sample Test 2
1. Insert the following elements (beginning with 50) into
a binary search tree. Show each insertion after balancing
the tree using the AVL algorithm:
50 80 55 70 90 75
2.1 Make the following array into a max heap using the usual
operation to produce a heap:
|
50
|
10
|
40
|
90
|
60
|
30
|
20
|
80
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
2.2 Consider the following min heap. Show the array as a
min heap after the 10 is deleted.
|
10
|
60
|
80
|
90
|
70
|
140
|
150
|
100
|
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
Answer:
3. Consider the following numbers (from LEFT to RIGHT: beginning
at 21):
21 95 53 22 85 82 31 34
A. Considering the hash function:
Hash( number ) = number % 17
i. Using a linear probe of 3 to resolve collisions,
fill in the following hash table:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
ii. Using quadratic probing to resolve collisions, fill in
the following hash table:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
B. Considering the hash function:
Hash( number ) = (sum of the digits of the number) % 17
i. Using a linear probe of 3 to resolve collisions,
fill in the following hash table:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
ii. Using quadratic probing to resolve collisions, fill in
the following hash table:
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
4. Suppose we wanted to store 50 different three-digit numbers
in a hash table of size 100. Which would be the best hash
function to use, and WHY?
A) H(number) = (sum of digits of the number) % 100
B) H(number) = (product of the digits of the number)
% 100
C) H(number) = number % 100
5. Consider the weighted, undirected graph:
20
10 5
40
80 70
A. If we use Dijkstra’s algorithm for calculating
the shortest paths from vertex 0 to all other vertices,
what are the values in the predecessor array at the end
of the algorithm that will help calculate the actual best
paths?
B. If beginning at 1 we were to traverse the graph printing
the vertex number out each time the traversal visits the
vertex, what would be printed if we use a
i. Depth-first search
ii. Breadth-first search
|