CMSC132 Spring 2007 Midterm 2 Key 1 24 pts Software Development Object Oriented Design a b c d The main reason good software is difficult to produce is complexity The software life cycle is a list of operations tasks steps for developing good software The waterfall model of software development emphasizes predictability planning 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 components class Foo int X void setX i j k l g 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 Inheritance encourages code reuse Adding a new method in a subclass is an example of extension In OO design objects in a system correspond to nouns in the problem description Similarly interactions between objects correspond to verbs in the problem description 2 8 pts Trees and Heaps For a binary search tree a Inserting nodes in sorted order generates a balanced binary tree b It is more efficient to compute the minimum value in a tree using recursion c The of steps required to find a value is always O log n d A sorted list of values may be produced with an in order tree traversal T or F T or F T or F T or F For 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 F Allow F if specify there are duplicate values in heap f The most space efficient implementation is one based on arrays T or F g The same of steps is required to find the minimum or maximum value T or F h A sorted list of values may always be produced in O n log n steps T or F 1 3 8 pts Heaps a b Draw the heap if it would be stored as an array 4 6 7 11 9 12 13 20 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 5 6 2 0 7 9 1 2 1 3 1 1 6 9 1 1 7 2 0 1 2 1 3 4 10 pts Huffman a b c d e Huffman encoding compresses data by exploiting redundancy symbol frequency Consider the following Huffman tree Decode the sequence 001111001 GOAL Encode the string LOG 0111001 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 3 Remember to assign 1s and 0s to your Huffman tree any legal assignment is fine 2 C E 0 1 B 0 1 0 A 0 D 1 1 3 5 10 pts Binary Trees Recursion Given the following Java class definition for a binary search tree implement a recursive method named getLeafValues that returns a list of values of leaf nodes from largest to smallest Non recursive implementations will receive no credit You can add auxiliary helper functions Recall that the add Object o method of the List interface will append its argument to the end of the list public class BinarySearchTree E extends Comparable E class Node E data contains data for node Node left null if no left subtree Node right null if no right subtree void getLV ArrayList E myL if left null right null myL add data if right null right getLV myL if left null left getLV myL Node root if leaf append data right 1st left 2nd TREE ROOT public 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 null if n left null getLV2 n left myL 4 6 16 pts Graphs 20 8 B D 10 11 A H C 7 2 12 4 F G 9 3 E 1 Graph Traversal For each graph traversal specify the order nodes are visited Pick nodes to visit using alphabetical order when multiple choices are possible a Apply DFS Depth First Search with G as the start node G E F C H b Apply BFS Breadth First Search with F as the start node F C G E H Minimum 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 F as 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 and predecessor for each node in the graph after 3 nodes A and 2 other nodes have been added to the set of processed nodes Remember to update node costs where necessary Node Cost Pred Orde r Stop after 3 nodes processed A B C D E F 0 11 19 19 12 non e 1 A 2 F B A OR G 16 H F 3 5 All nodes processed C D E F 19 19 17 12 A 0 B 11 non e 1 A F B G 2 7 8 7 8 5 G 16 H 18 A F G 3 4 6 7 10 pts GUIs Event driven Programming and Java Support for GUIs a b c d In the software model for GUI design the model component performs the actual work An event is a condition action occurring outside the normal flow of a program In Java an inner class can access all private fields and methods of its outer class 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 here 8 14 pts Object Oriented Design Your program must track customers shopping for merchandise at a camera store Every item of merchandise has a quantity and a price Merchandise in the store s inventory include digital cameras 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 use mini DVDs for storage Customers may purchase merchandise Your program must …
View Full Document
Unlocking...