Grader Use Only 1 2 3 4 5 6 7 8 9 10 Total Honors CMSC132 Fall 2005 Final Exam Key First Name 15 7 8 13 9 16 9 7 8 8 100 8 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 e This exam is closed book and closed notes If you have a question please raise your hand Total point value is 100 points Answer True False questions by circling the T or F at the end of the question Answer multiple choice questions by circling the letter e g a b at the front of each choice f Answer essay questions concisely using 1 or 2 sentences Longer answers are not necessary and are discouraged g WRITE NEATLY If we cannot understand your answer we will not grade it i e 0 credit h Honors section questions only count for credit for students in the honors section 1 Problem 1 15 pts Software Engineering Object Oriented Design a 1 pt The Waterfall model is reasonable for both small and large projects T or F b 1 pt The Waterfall model Unified model and Rapid Prototyping are intended to be models of what Hint Provide a 3 word answer You get 0 points for providing definitions of each model Software life cycle c 1 pt Define data abstraction Hiding implementation details of data d 8 pts Given the following problem description produce an object oriented solution and answer the questions below Design a software system for a bookstore that keeps an inventory of two types of books traditional books and books on CD Books on CD may also contain music The bookstore purchases books from publishers and sets a price for each book Customers can purchase books from the bookstore using either cash or a credit card The bookstore keeps track of which books it has its inventory and the books purchased by each customer i What are the objects in your object oriented solution Store Book NormalBook CDBook Customer NormalBook is optional ii What are the interactions between objects in your object oriented solution BookstorePurchaseBook FromPublisher SetPrice CustomerPurchaseBook FromBookstore iii Which objects have other objects Also list target object Store has Book Store has Customer Customer has Book is optional iv Which objects use other objects Also list target object Customer uses Book is optional if Customer has book v Which objects are other objects Also list target object NormalBook is Book CDBook is Book NormalBook is optional e 4 pts Given the following Java code draw its UML class diagram public class Button RemoteControl public String operation controlButton Button public double frequency dvd DVD public class DVD allOnButton AllOnButton public void onOff activateButton String String void public void play public class AllOnButton extends Button 1 1 public int currentValue DVD public class RemoteControl public Button controlButtons onOff void public DVD dvd play void public AllOnButton allOnButton public void activateButtonOn String operation String deviceName 2 Button operation String frequency double AllOnButton currentValue int Problem 2 7 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 2 i f n O n for int k 0 k 20 k for int j 0 j 30 j ii for int i n 2 i n i f n O n log n log n for int j 1 j n j j 2 for int k 1 k n k k 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 2 n O n O 1 O log n O n O nlog n O 2 n c 2 pts How can asymptotic complexity be analyzed for recursive algorithms Using recurrence relations Problem 3 8 pts Data Structures and Recursion a 1 pt Elements in a map have exactly 1 successor T or F b 1 pt A base case is optional for some recursive problems T or F c 6 pts Given the following Java class definition for a binary tree write a recursive method named numLeafNodes that determines the number of leaf nodes in the binary tree Remember that leaf nodes are nodes with no children Assume left and right have the value null if no subtree is present You may use helper functions Class Node Object myValue Node left Node right Class Tree Node root root node in tree int numLeafNodes return number of leaf nodes in tree return countLeaf root int countLeaf Node n if n null return 0 int L countLeaf n left int R countLeaf n right if n left null n right null return 1 return L R 3 Problem 4 13 pts Graph Algorithms a b c d 1 pt Every cycle is a path 1 pt Every graph has a unique minimum spanning tree 1 pt You can implement a Depth First Traversal using a Queue 10 pts Consider the following graph i T or F T or F T or F 10 2 pts List the set of nodes visited in the order first visited while performing a Depth First Search starting at B 10 4 S B D B A C E D or B C E D A or B D A C E or B D C E A or BCEAD C E D always immediately after A unless already visited 2 2 E D always after C unless already visited 1 3 6 ii 2 pts List the set of nodes visited in the order first visited while performing a Breadth First Search starting at A B C E 6 8 B A C D E or B A D C E or B C A D E or B C D A E E is always 7 last iii 2 pts List the first edge rejected by Kruskal s minimal spanning tree algorithm you can treat all edges as undirected edges for this problem A C or D E iv 4 pts Show the entries in the following table after adding the first 3 nodes S 2 other nodes when applying Djikstra s single source shortest path algorithm starting at S S A B C D E LowestCost 0 2 10 8 10 16 Predecessor none S S A S C 4 Problem 5 9 pts Compression and Huffman Codes a 1 pt The compression factor associated with the Huffman encoding is affected by how 0 s and 1 s are assigned to a Huffman tree b 4 pts Consider the following Huffman tree H T 0 1 M K 0 Z 0 1 0 1 1 i 2 pts Decode the sequence 1001000 ii 2 pts Encode the string MTZ KMH 0100111 c 4 pts Create a Huffman tree for the following nodes A B B C D C A …
View Full Document
Unlocking...