Name_________________
CIS 350 Final Exam
Winter '97
(2 points)
1. Use order arithmetic to evaluate:
O(3n * [(n - 1) + (n * log n) + n!])
(3 points)
2. In the context of object oriented programming describe the
role of a "method"?
3. Describe a programming situation in which a digraph would
be preferred to a binary search tree as a data structure.
4. What are the economic benefits of using object-oriented
programming methodologies?
5. Why would it ever be necessary to remove recursion from an
algorithm once it has compiled and executed correctly?
Name_________________
6. How are parallel algorithms different from distributed
algorithms?
7. What is the principle of divide and conquer as applied to
parallel algorithm design?
8. With no prior knowledge of order, and for a large number of
array elements (n > 300), order these sorting algorithms from
greatest (1) to least (4) efficiency:
bubble ________ heap ________
shell ________ selection ________
9. Describe the critical portion of the quicksort algorithm
which determines whether or not quicksort exhibits its
worst case behavior.
10. Explain why Kruskal's algorithm is an example of a greedy
algorithm?
Name_________________
11. Perform the AVL rotation required to rebalance this tree.
A
/ \
B C
/ \
D E
/
F
12. Given the following heap, move the root node to its final
resting place and readjust the heap according to the text
rules for the heap sort.
17
/ \
10 12
/ \ / \
8 6 11 5
/ \
7 4
(4 points)
13. Using h(x) = x % 5 and chaining to resolve collisions, draw a
diagram which shows the results of hashing the numbers:
13 4 14 15 8 5 6 16 9
14. Use Dijkstra's algorithm to find the shortest path from
vertex 2 to each other vertex in the digraph shown below.
tail
| 1 2 3 4
--------------
h 1 | 0 5 2
e 2 | 2 0 3 1
a 3 | 2 0
d 4 | 0
Name_________________
15. Consider a doubly linked list stored in the array structure
below (I is the subscript value). Show the contents of the
structure after deleting the node pointed to by P.
I INFO LEFT RIGHT
1 12 0 3
2 1 4 5 P = 2
3 -6 1 4
4 10 3 2
5 17 2 0
16. Create a Huffman code for the characters: b, l, u, e with the
corresponding the relative frequencies: .2, .4, .25, .15
17. Use the digraph adjacency matrix below and topologically sort
vertices 1 to 5.
| 1 2 3 4 5
-----------------
1 | 0 0 1 0 0
2 | 0 0 1 1 0
3 | 0 0 0 0 1
4 | 0 0 0 0 1
5 | 0 0 0 0 0
18. Solve the recurrence relation shown below.
T(n) = 1 for n = 1
= 2 * T(n - 1) for n > 1
Name_________________
(5 points)
19. Redraw this order 3 B-tree after deleting E and L in that
order.
M-Q
/ | \
E-K O W
/ | \ / \ / \
A-B I-J L N P T-U Z
20. Determine the worst case running time for the algorithm
below. Express your answer in big-Oh notation and explain how
it was determined (this means show me all your work).
cin >> N;
for (I = 0 ; I <= N; I++)
for (J = 0; J <= N; J++)
cin >> A[I,J] >> B[I,J];
for (I = 0; I <= N; I++)
for (J = 0; J <= N; J++)
{
C[I,J] = 0;
for (K = 1; K <= N; K++)
if (I > J)
C[I,J] 0 = C[I,J] + A[I,K] * B[K,J];
}
(6 points)
21. Write a recursive procedure (or function) which has as
input parameters a pointer to a binary tree and a numeric key
sought for and returns a "pointer" to the node containing the
key if found or NULL otherwise.
Name_________________
(8 points)
22. Write a procedure, which receives graph and a vertex as input
parameters. Your procedure should delete the vertex from the
graph, along with all edges incident on the vertex. Include
all declarations needed to implement the graph type in your
solution.