Name:__________________________________ 4 December 1998
CS 503 Final Examination
K. R. Kaplan
There are 7 questions on this exam; don't overlook any. All work should go on
this exam paper.
1. In the height-balanced tree shown below, lower-case letters represent
nodes, and the upper-case letters represent subtrees. The initial subtree
heights are A, C, D: h-1; B, F, G, H: h; E: h+1.
a) What is the height of the tree rooted at d?__________
b) Label each node L (for left-high), R (for right-high), or N
(neutral):
before
a: ___ e: ___
b: ___ f: ___
c: ___ g: ___
d: ___
d
/ \
b f
/ \ / \
a c e g
/ \ / \ / \ / \
A B C D E F G H
c) A deletion is made which decreases the height of B to h-1. Is any
rebalancing necessary? If so, redraw the tree in the space above.
In any event, list the new balance conditions after the deletion has
been processed.
after
a: ___ e: ___
b: ___ f: ___
c: ___ g: ___
d: ___
2. Suppose we modify the representation of a BST as indicated by the type
definitions below:
typdef struct btn {
char key; // single character key
struct btn *L,*R;
int numLST; // number of nodes in the left subtree of this node
} btNode, *bt;
btNode *initNode(char c) {
btNode *p = malloc(sizeof(btNode));
p->key = c;
p->L = p->R = null;
p->numLST = 0;
}
Complete the coding of a method find_rth which returns the rth key in the
inorder sequence of a BST implemented with the datatypes above. For example, if
r = 1, we want the smallest, if r = 2, then the second smallest, etc.
char find_rth(bt b, int r) {
/* assumes r > 0; returns the rth smallest key in the BST; returns
null if r is greater than the number of nodes in the tree */
}
Now complete the code for insertBST which inserts single-character keys into
this modified BST:
void insertBST(bt b, char c) {
if(b != null) {
}
}
3. The representation below is the adjacency list representation involving
array indices for vertices and pointers for edge records. Given that a graph
has been populated with vertices and (directed) edges, write a method to
initialize the pCount (number of incoming edges) and the sCount (number of
outgoing edges) fields for each vertex.
#define MAX = 100;
typedef struct e {
int neighbor; // vertex array index of neighbor
struct e *next; // next edge record in the adjacency list
} edge, *ep;
typedef struct {
int pCount; // number of predecessors
int sCount; // number of successors
ep head; // first edge in neighbor list
} vertex;
typedef struct {
int numVerts; // number of vertices in the graph
vertex vArray[MAX+1]; // array of vertices in 1...numVerts
} graph;
void initCounts(graph g) {
// initializes the pCount and sCount variables for each vertex
}
4. Convert the 8-element array S Y A D I L O H so that it represents a maxheap.
Do this first with the O(n#lg#n) algorithm, then with the O(n) algorithm. Show
the final arrays that represent the maxheap (as well as any intermediate work).
Consider using a height-balance BST to implement a heap. What are the insert
and remove costs for this implementation? Why might you prefer - if you do - a
binary heap implementation to using a height-balanced binary search tree to
implement a heap?
5. Trace quicksort sorting the array of characters 6 13 10 16 14 11 17 5 8 2 7
by showing the binary search tree that is "constructed". Don't quicksort lists
with three elements or less: leave them in place in the array. Show the final
array.
How many comparisons does insertion sort require to "clean-up" this array?
Suppose mergesort is modified so that it doesn't sort lists of size three or
less. The small lists are insertion-sorted. Carry out a (hybrid) mergesort - by
showing the binary tree of sublists - on the initial list above. Use the
convention that the left half of a split list is <= in size to the right half.
How many comparisons are required to do all the merging? _____________________
Can we postpone the insertion-sorting until after the mergesort is complete as
we can do in quicksort? Explain.
6. Consider the following weighted digraph; weights on edges represent task
times as in the PERT model.
6
A B
5 6
4
D 2 1 C
2
9 5 6 E
4
F
3 G
a) Compute the earliest time and latest time values for each node in
the network. Do the former by doing a BF topsort,and show the
topsort numbers and the et and lt values below.
end(verbatim)
What is the overall project completion time ? _________
List ALL critical paths from source(s) to sink (you may not need all
lines). Think carefully about this.
___________________________
___________________________
___________________________
Suppose that you wanted to decrease the overall project completion t
and that you were allowed to decrease the weight of ONE directed edg
Which edge would you choose? Explain briefly.
If you want to make the overall project completion time as small as
but it costs $D for every reduction of one unit in weight, what weig
you assign to the edge given in your previous answer so as to spend
money? ______ Why?
7. The postorder label sequence for a binomial queue (forest of
binomial trees with at most one tree of any index) is Q U I C K S O
R T I N G. (The forest is not being used as a heap: there is no heap
ordering.) Show the forest below. Why don't we need more than the
given information to determine a forest of trees?
b) Now build a binomial queue by sequentially inserting the keys H E A
P S O R T: maintain maxheap order.
c) Remove the largest key from the heap, and restore the binomial
queue.
d) What is the average cost (in merges) to insert a new key into a
binomial queue containing n keys. Why?