Solutions to the "Sample Final"
(actually the Spring 2004 Final)
CSE 373

1. C  
card(S1)=2
card(S1 U S2) = 4
2 * 4 = 8

2. E
All others are missing shortcuts for at least one chain
of length 2.

3. A
The function is both an injection (each domain element
gets a range element that is different from the others'
range elements) and a surjection (every range element
is used).  Therefore it is a bijection (i.e., invertible,
also known as a one-to-one correspondence).

4. A
Apparently newly enqueued elements are placed at the end of
the sequence.  So the e is added to the right end.

5. E
Using a circular array to implement the queue, it takes
constant time to do an ENQUEUE.  Using a linked list,
with an extra pointer keeping track of the end of the
list, it also takes constant time to do an ENQUEUE.

6. C
Each additional level of recursion causes another factor of
3 in the result.

7. D
There are 7 levels of nodes, or 2^7 - 1 nodes (127), and
the number of edges in a tree is always one less than the number of
nodes.

8. D
Postorder requires processing the left and right subtrees before
processing the root.  

9. B

10. C
A binary tree is not necessarily balanced.

11. D
FINDMIN takes O(1) time.

12. B
Horner's rule minimizes the number of multiplications.

13. 61
We generally prefer prime numbers as sizes so that
the MOD operation doesn't lead certain locations to
be hit more often than others.

14. B
We want all hash table locations to be reachable using the
hash function.

15. C
Since the tree could be a single chain without branching,
there could be as few as 6 nodes in it.

16. C
In a B-tree, every interior node other than the root must
have at least ceiling(m/2) children and at most m children.
(The root only needs at least 2, and at most m).

17. C
In a topological ordering, the first node must be a node
of in-degree zero.  In the graph, both B and D have
in-degree 0.  However, none of the available answers begin
with B.  

18. A
Mergesort uses an extra array.

19. B, C

20. D, E

21. C
There are log_b N subkeys, each requiring a pass through all
the data.  Since there are n data elements, we must multiply
those together (and multiply by a constant factor) to get
the running time.

22. C
These trees are called up-trees.

23. B
We knock down a wall provided the cells that the wall separates
are not already connected (and therefore in the same subset).

24. D
An equivalence relation must not only be reflexive and
transitive, but also symmetric.

25. C
Depth-first search of a graph is similar to a preorder traversal
of a tree, except that nodes already visited are skipped.

Part II

1. 
It is a little difficult to read the labels on the edges of
the graph in the diagram, thanks to the default settings for
Adobe Acrobat (sorry).  The values are....
A, 12
B, 7
C, 14
D, 4
E, 16
F, 6
G, 8
H, 17
I, 9
J, 13
K, 15
L, 3
M, 18
N, 5
O, 19
P, 11
Q, 10


The minimum spanning tree consists of the edges:

A, B, D, F, G, L, I, N, Q




2. initial cost matrix:  (corrected 10 Dec.)

0  1  3  :  :
1  0  7  9  2
3  7  0  :  4
:  9  :  0  6
:  2  4  6  0

Final cost matrix:

0  1  3  9  3
1  0  4  8  2
3  4  0 10  4
9  8 10  0  6
3  2  4  6  0

3.
AVL tree with the minimum number of nodes for height 3

                   o
                  / \
                 /   \
                /     \
               o       o
              / \       \
             /   \       \
            /     \       \
           o       o       o
          /
         /
        /
       o

This is not the only solution.  Exchanging left and right
subtrees at any interior node will give an equally valid
solution.