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.