CMSC132 Spring 2006Final Exam KeyFirst Name: _______________________Last Name: _______________________Student ID: _______________________Section time ___________ TA: _____________________I pledge on my honor that I have not given or received any unauthorized assistance on this examination.Your signature: _____________________________________________________________General Rules (Read):a. This exam is closed book and closed notes.b. If you have a question, please raise your hand.c. Total point value is 100 points. d. The short answer questions are not essay questions. Strive to answer them in 1 or 2 sentences. Longer answers are not necessary and are discouraged.e. WRITE NEATLY. If we cannot understand your answer, we will not grade it (i.e., 0 credit).f. PUNT RULE:. For any question, you may write PUNT, and you will get ¼ of the points forthe question (rounded down). If you feel totally lost on a question, you are encouraged to punt rather than waste time writing down a bunch of vaguely related verbiage in hopes of getting some partial credit.g. Honors section questions only count for credit for students in the honors section.1Grader Use Only:#1 (12)#2 (9)#3 (20)#4 (12)#5 (12)#6 (6)#7 (15)#8 (14)Total (100)Honors (8)Problem 1 (12 pts) Algorithm Complexitya. (3 pts) Calculate the asymptotic complexity of the code snippets below (using big-O notation) with respect to the problem size n.i. for (int i=0; i<n/4; i++) { f(n) = O( n ) for (int k=0; k<20; k++) { // … }}ii. for (int i=n/4; i<=n/2; i++) { f(n) = O( nlog(n) ) for (int j=1; j<=n; j=j*2) { // ... }}iii. for (int i=1; i<=100; i++) { f(n) = O( 1 ) // ...}b. (2 pts) List the following big-O expressions in order of asymptotic complexity (with the lowest complexity first)O(nlog(n)) O(1) O(log(n)) O(2n) O(n2)Answer: O(1), O(log(n)), O(nlog(n)), O(n2), O(2n)c. (1 pt) What is the worst case complexity of sorting using quicksort?Answer: O(n2)d. (2 pts) What can cause worst case behavior for quicksort?Answer: A bad partitioninge. (2 pts) Name two representations used for the implementation of a graph (don’t name any that use Sets).Answer: Adjancency Matrix and Adjacency Listf. (2 pts) For the two graph representations named above, which would be more efficient for performing a depth first search of the graph?Answer: Adjancency List2Problem 2 (9 pts) Compression and Huffman Codesa. (4 pts) Consider the following Huffman tree.i. (2 pts) Decode the sequence “1001000”Answer: FMPii. (2 pts) Encode the string “FAM”Answer: 1000101 b. (5 pts) Create a Huffman tree for the symbols A, B, C, D, E, and F which have the following frequencies:A : 7 B : 3 C : 4 D : 8 E : 2 F : 3MKF11101000AP3Answer:Possible Tree 1 (F and B can be interchanged)Possible Tree 2 (F and B can be interchanged)DA11101000FEB C10AD11101000FEB C014Problem 3 (20 pts) Binary Treesa.(6 pts) Answer the following questions based on the following binary tree:Answer: i. Write the postorder traversal for the tree9 4 6 8 5 2ii. Write the preorder traversal for the tree.2 4 9 5 6 8iii. Write the inorder traversal for the tree.9 4 2 6 5 8b. (14 pts) The following Java class definition for a binary tree will be use to answer the questions that follow. public class BinaryTree <E> {static class Node<T> {T data;Node <T> left, right;public Node(T data) {this.data = data;left = null;right = null;}}Node <E> root;public int interiorNodesCnt() {// Method you need to implement}public List<E> leafNodeValues() {// Method you need to implement}}4 59 8625i. Implement the method interiorNodesCnt that determines the number of interior nodes in the tree. An interior node is a node that is not a leaf node. A tree with only one node has no interior nodes. You may add auxiliary/helper methods.Answer: public int interiorNodesCnt() {return interiorNodesCnt(root);}private int interiorNodesCnt(Node<E> currRoot) {if (currRoot == null)return 0;else {int count = 0;if (currRoot.left != null || currRoot.right != null)count++;return count + interiorNodesCnt(currRoot.left) + interiorNodesCnt(currRoot.right); }}ii. Implement the method leafNodeValues that returns a list (ArrayList) of the data values present in the leaf nodes. You may add auxiliary/helper methods.Answer: public List<E> leafNodeValues() {ArrayList<E> list = new ArrayList<E>();leafNodeValues(root, list);return list;}public void leafNodeValues(Node<E> currRoot, List<E> list) {if (currRoot == null)return;else {if (currRoot.left == null && currRoot.right == null)list.add(currRoot.data);else {leafNodeValues(currRoot.left, list);leafNodeValues(currRoot.right, list);}}}6Problem 4 (12 pts) Graph AlgorithmsConsider the following graph.a. (2 pts) List the set of nodes visited (in the order first visited) while performing a Depth First Search starting at A. Use alphabetical order to choose the next node to process, when several successors are available.Answer:A C D F Eb. (2 pts) List the set of nodes visited (in the order first visited) while performing a Breadth First Search starting at A. Use alphabetical order to choose the next node to process, when several successors are available.AnswerA C E D F7Consider the following graph:c. (2 pts) Assume the above graph is an undirected graph. Run Kruskal’s minimum spanning tree algorithm in the above graph, and draw the tree we will have after four edges have been considered. Answer:d. (6 pts) Run Dijkstra’s shortest path algorithm on the previous graph using H as the start vertex. Show the entries in the following table after adding the first 3 nodes (H & 2 other nodes) to the set S of processed nodes (as defined by Djikstra’s algorithm). Keep in mind that after adding a node to the set S you must adjust the cost/predecessor of the appropriate successors nodes. In the table below, leaving a LowestCost entry blank represents an infinite cost, and leaving a Predecessor entry blank represents no predecessor. Answer:H A B C D ELowestCost 0 14 13 16 10Predecessor B H B H13B5B DA C8HA C ED698431107Problem 5 (12 pts) HeapsUse the following heap to answer the questions that follow.a. (3 pts) Draw the heap that would result from inserting 8 in the above heap.Answer: 61016242114111513 6816242110111513149b. (3 pts) Draw the heap that would result by deleting 6 from the original heap.c. (6 pts) For this problem you will implement the method isMinHeap that has the following prototype:public static boolean
View Full Document
Unlocking...