Name_________________
CIS 350 Exam 2
Winter '97
(3 points)
1. How does the organization of a B-tree differ from the
organization of a binary tree?
2. Write type declarations for a data structure which might be
used to implement a priority queue.
3. Compare the relative efficiencies of the Prim's algorithm
and the depth-first search algorithm as a means of finding
a spanning tree.
4. What is the principle difference between Floyd's algorithm
and Dijkstra's algorithm?
Name_________________
5. Given the following heap, cut 17 out of the heap and
readjust the heap nodes so that FindMax will a O(1)
operation.
17
/ \
10 12
/ \ / \
8 6 11 5
/ \
7 4
6. Draw the binary search tree after deleting the node
containing E.
J
/ \
E Q
/ \ / \
D G M W
/ / \
A F H
7. Which node becomes the pivot node for an AVL rotation
following the addition of F to the tree below? Why?
A
/ \
B C
/ \
D E
/
F
8. Assuming the key values T and W are inserted (in that
order) into the B-tree below, draw the new B-tree which
results.
M-Q
/ | \
E-K O V
/ | \ / \ / \
A I L N P R-S Z
Name_________________
(4 points)
9. Indicate the order in which Kruskal's algorithm would include
edges in constructing a minimum spanning tree for this graph.
1
B E ----- G
| \ 7 | |
5| \ | 4 |6
| \ | |
C ----- F ----- H
2 3
10. Construct the binary expression tree from the traversals
shown below.
Inorder: 4 + 3 + 2 * 1
Preorder: + 4 * + 3 2 1
11. 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
Name_________________
(6 points)
12. Write a function, which receives as an input argument the
root to a binary tree and returns a count of the number of
leaf nodes in the binary tree. Include any type definitions
used in your solution.