Grader Use Only 1 2 3 4 5 6 7 8 Total Honors CMSC132 Spring 2006 Final Exam Key 12 9 20 12 12 6 15 14 100 8 First 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 b c d This exam is closed book and closed notes If you have a question please raise your hand Total point value is 100 points 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 for the 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 1 Problem 1 12 pts Algorithm Complexity a 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 for int k 0 k 20 k f n O n ii for int i n 4 i n 2 i for int j 1 j n j j 2 f n O nlog n 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 partitioning e 2 pts Name two representations used for the implementation of a graph don t name any that use Sets Answer Adjancency Matrix and Adjacency List f 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 List 2 Problem 2 9 pts Compression and Huffman Codes a 4 pts Consider the following Huffman tree P A 0 1 M F 0 0 1 0 K 1 1 i 2 pts Decode the sequence 1001000 ii Answer FMP 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 3 3 Answer Possible Tree 1 F and B can be interchanged E B F 0 1 0 C 1 A 0 D 0 1 0 1 1 Possible Tree 2 F and B can be interchanged E F 0 1 B C 0 1 D A 0 1 0 0 1 1 4 Problem 3 20 pts Binary Trees a 6 pts Answer the following questions based on the following binary tree 2 4 5 9 6 8 Answer i Write the postorder traversal for the tree 946852 ii Write the preorder traversal for the tree 249568 iii Write the inorder traversal for the tree 942658 b 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 5 i 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 6 Problem 4 12 pts Graph Algorithms Consider 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 ACDFE b 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 Answer ACEDF 7 Consider the following graph 10 5 13 H B D 9 1 3 A 6 C E 4 8 7 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 B A D C 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 LowestCost Predecessor H 0 A 14 B 13 C 16 D 10 B H B H 8 E Problem 5 12 pts Heaps Use the following heap to answer the questions that follow 6 1 0 1 1 1 6 1 4 2 4 1 5 1 3 2 1 a 3 pts Draw the heap that would result from inserting 8 in the above heap Answer 6 8 1 1 1 0 1 6 2 4 2 1 1 5 1 4 9 1 3 b 3 pts Draw the heap that would result by deleting 6 from the original heap 1 0 1 4 1 6 1 1 2 1 1 5 1 3 2 4 c 6 pts For this problem you will implement the method …
View Full Document
Unlocking...