CMSC132 Spring 2007 Midterm #2 - Key1. (24 pts) Software Development & Object Oriented Designa. The main reason good software is difficult to produce is complexityb. The software life cycle is a list of operations / tasks / steps for developing good software. c. The waterfall model of software development emphasizes predictability / planning.d. The iterative model of software development emphasizes adaptability / feedback / prototypes / flexibility.e. Problem specifications may be ambiguous due to imprecision of natural language / English.f. One approach to program design is to divide the problem as a collection of functions / objects/ subproblems / componentsg. In the code at left, X is an example of an object’s state. h. In the code at left, setX( ) is an example of an object’s behavior.i. Inheritance encourages code reuse.j. Adding a new method in a subclass is an example of extensionk. In OO design, objects in a system correspond to nouns in the problem description.l. Similarly, interactions between objects correspond to verbs in the problem description.2. (8 pts) Trees and HeapsFor a binary search tree:a. Inserting nodes in sorted order generates a balanced binary tree. T or Fb. It is more efficient to compute the minimum value in a tree using recursion. T or Fc. The # of steps required to find a value is always O(log(n)). T or Fd. A sorted list of values may be produced with an in-order tree traversal. T or FFor a heap designed to find the maximum value of a collection:e. The value of a node is always larger than (or equal to) the values of its children. T or FAllow F if specify there are duplicate values in heapf. The most space efficient implementation is one based on arrays. T or Fg. The same # of steps is required to find the minimum or maximum value. T or Fh. A sorted list of values may always be produced in O(n log(n)) steps. T or F1class Foo { int X; void setX( ) { … }}3. (8 pts) Heapsa. Draw the heap if it would be stored as an array: 4, 6, 7, 11, 9, 12,13, 20b. Draw the heap that would result from inserting 5 in the above heap.c. Draw the heap that would result by deleting 4 from the original heap. SHAPE \* MERGEFORMAT 4. (10 pts) Huffmana. Huffman encoding compresses data by exploiting redundancy / symbol frequency b. Consider the following Huffman tree.c. Decode the sequence “001111001” GOALd. Encode the string “LOG” 0111001e. Create a Huffman tree for the symbols A, B, C, D and E with the following frequencies:A : 5 B : 7 C : 3 D : 4 E : 3Remember to assign 1s and 0s to your Huffman tree (any legal assignment is fine) 4569712132011 691120712132BDA11101000EC35. (10 pts) Binary Trees & RecursionGiven the following Java class definition for a binary search tree, implement a recursivemethod named getLeafValues that returns a list of values of leaf nodes, from largest tosmallest. Non-recursive implementations will receive no credit. You can add auxiliary helperfunctions. Recall that the add(Object o) method of the List interface will append its argumentto the end of the list. public class BinarySearchTree<E extends Comparable<E>> { class Node {E data; // contains data for nodeNode left; // null if no left subtreeNode right; // null if no right subtreevoid getLV(ArrayList<E> myL) {if ((left == null) & (right == null)) // if leafmyL.add(data); // append dataif (right != null) right.getLV(myL); // right 1stif (left != null) left.getLV(myL); // left 2nd}}Node root; // TREE ROOTpublic ArrayList<E> getLeafValues() { ArrayList<E> myL = new ArrayList<E>( );if (root != null) root.getLV(myL);return myL;}public ArrayList<E> getLeafValues2() { // Alternative solution ArrayList<E> myL = new ArrayList<E>( );getLV2(root, myL);return myL;}void getLV2(Node n, ArrayList<E> myL) {// if (n == null) return; *can avoid null check later*if ((n.left == null) && (n.right == null))myL.add(n.data);if (n.right != null) getLV2(n.right, myL); // check for nullif (n.left != null) getLV2(n.left, myL); } }46. (16 pts) GraphsGraph Traversal - For each graph traversal, specify the order nodes are visited. Pick nodes to visitusing alphabetical order (when multiple choices are possible).a. Apply DFS (Depth First Search) with G as the start node. G, E, F, C, Hb. Apply BFS (Breadth First Search) with F as the start node. F, C, G, E, HMinimum Spanning Tree (MST) - Consider the above graph as an undirected graph. c. List (in the order added to the MST) the first 5 edges selected by Prim’s MST algorithm using Fas the starting node. (F,G), (G,E), (G,H), (F,C), (C,B)d. List (in the order added to the MST) the first 5 edges selected by Kruskal’s MST algorithm.(G,E),(G,H),(F,G),(F,C),(B,D)Single Source Shortest Path - Consider the above graph as an undirected graph. e. Apply Dijkstra’s algorithm using A as the starting (source) node. Indicate the cost andpredecessor for each node in the graph after 3 nodes (A and 2 other nodes) have been added tothe set of processed nodes. Remember to update node costs where necessary. Stop after 3 nodes processed OR All nodes processedNode A B C D E F G H A B C D E F G HCost 0 11 19 19 ∞ 12 16 ∞ 0 11 19 19 17 12 16 18Pred noneA F B A F noneA F B G A F GOrder 1 2 3 1 2 7/8 7/8 5 3 4 6BA CFDGHE2081110749122 3157. (10 pts) GUIs, Event-driven Programming, and Java Support for GUIsa. In the software model for GUI design, the model component performs the actual workb. An event is a condition / action occurring outside the normal flow of a program. c. In Java, an inner class can access all private fields and methods of its outer class. d. In Java, the ActionListener interface requires the method void actionPerformed(ActionEvent e) be implemented. Create an anonymous inner class implementing the ActionListener interface for the following Java component:GUIcomponent.addActionListener( new ActionListener( ) { public void actionPerformed (ActionEvent e) { … } // method}) ; // right parentheses here8. (14 pts) Object-Oriented DesignYour program must track customers shopping for merchandise at a camera store. Every item ofmerchandise has a quantity and a price. Merchandise in the store’s inventory include digitalcameras and storage media. Some digital cameras support recording HD (High-Definition)video. Digital cameras use flash memory for storage. HD-video digital cameras can also usemini-DVDs for storage. Customers may purchase merchandise. Your program
View Full Document
Unlocking...