CMSC132 Fall 2005Final 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. Answer True/False questions by circling the T or F at the end of the question.e. 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.1Grader Use Only:#1 (15)#2 (7)#3 (8)#4 (13)#5 (9)#6 (16)#7 (9)#8 (7)#9 (8)#10 (8)Total (100)Honors (8)Problem 1 (15 pts) Software Engineering & Object-Oriented Designa. (1 pt) The Waterfall model is reasonable for both small and large projects. T or Fb. (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 cyclec. (1 pt) Define data abstraction. Hiding implementation details of datad. (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: traditionalbooks and books on CD. Books on CD may also contain music. The bookstore purchases booksfrom 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, andthe 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 {public String operation;public double frequency;}public class DVD {public void onOff() { // … }public void play() { // … }}public class AllOnButton extends Button {public int currentValue;}public class RemoteControl {public Button[ ] controlButtons;public DVD dvd;public AllOnButton allOnButton;public void activateButtonOn(String operation, String deviceName) { //... }}2RemoteControlcontrolButton : Button[ ]dvd : DVDallOnButton : AllOnButtonactivateButton( String, String ) : voidButtonoperation : Stringfrequency : doubleAllOnButtoncurrentValue : intDVDonOff( ) : voidplay( ) : void1 1*RemoteControlcontrolButton : Button[ ]dvd : DVDallOnButton : AllOnButtonactivateButton( String, String ) : voidButtonoperation : Stringfrequency : doubleAllOnButtoncurrentValue : intDVDonOff( ) : voidplay( ) : void1 1*Problem 2 (7 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/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 relationsProblem 3 (8 pts) Data Structures and Recursiona. (1 pt) Elements in a map have exactly 1 successor. T or Fb. (1 pt) A base case is optional for some recursive problems. T or Fc. (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 treereturn 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; }3Problem 4 (13 pts) Graph Algorithmsa. (1 pt) Every cycle is a path. T or Fb. (1 pt) Every graph has a unique minimum spanning tree. T or Fc. (1 pt) You can implement a Depth First Traversal using a Queue. T or Fd. (10 pts) Consider the following graph.i. (2 pts) List the set of nodes visited (in the order first visited) while performing a Depth First Search starting at B. 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, E,D always after C unless already visited)ii. (2 pts) List the set of nodes visited (in the order first visited) while performing a Breadth First Search starting at B. 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 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 ELowestCost 0 2 10 8 10
View Full Document
Unlocking...