CMSC132 Fall 2006Midterm #2First 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):- 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 essay questions concisely using 1 or 2 sentences. Longer answers are not necessary and are discouraged.- WRITE NEATLY. If we cannot understand your answer, we will not grade it (i.e., 0 credit).- Honors section questions only count for credit for students in the honors section.1Grader Use Only:#1 (22)#2 (14)#3 (10)#4 (10)#5 (11)#6 (21)#7 (12)Total (100)Honors (15)21. (22 pts) Trees, Search Trees, Heapsa. Trees are hierarchical data structures T or Fb. A tree node can have multiple children T or Fc. A tree node can have multiple parents T or Fd. A leaf node can have up to 2 children T or Fe. A binary tree node can have up to 2 children T or Ff. A binary tree is balanced if most interior nodes have 2 children T or Fg. A binary tree is degenerate if more than 100 nodes have only 1 child T or Fh. A binary tree is perfect if no node has only 1 child T or Fi. A tree traversal visits every node in the tree T or Fj. Preorder traversals are faster than postorder traversals T or Fk. Breadth-first traversals are slower than depth-first traverals T or FFor a binary search tree:l. The value of a node is always greater than the values of its children T or Fm. The left child’s value is always smaller than the value of the right child T or Fn. The # of steps required to find a value is proportional to the tree’s height T or Fo. The # of steps required to delete a value is always O(log(n)) T or Fp. A sorted list of values may be produced with an in-order tree traversal T or FFor a heap (designed to find the minimum value of a collection):q. The value of a node is always smaller than the values of its children T or Fr. The left child’s value is always smaller than the value of the right child T or Fs. The # of steps required to find a value is proportional to the tree’s height T or Ft. The # of steps required to delete a value is always O(log(n)) T or Fu. A priority queue allows higher priority elements to be dequeued first T or Fv. A priority queue of size n allows elements to be inserted in O(1) time T or F32. (14 pts) Trees & HeapsUse the following binary tree/heap to answer the questions that follow.a. List the order nodes are traversed in an in-order traversal of the treeb. List the order nodes are traversed in a breadth-first traversal of the treec. Draw the heap as it would be stored in an arrayd. Draw the heap that would result from inserting 4 in the above heap.e. Draw the heap that would result by deleting 6 from the original heap.3. (10 pts) Huffman 6813119144a. Create a Huffman tree for the symbols A, B, C, and D which have the following frequencies:A : 3 B : 6 C : 8 D : 7Assign 1s and 0s to your Huffman treeb. Use your Huffman tree to encode the string “CCCC”. Show the resulting code.c. Use your Huffman tree to decode the code “0000000000”. Show the resulting string. You can ignore the remaining code (at the end) if it is incomplete.4. (10 pts) Binary TreesThe following Java class definition for a binary tree will be used to answer the question that follow. 5public class BinaryTree <E> {class Node<T> {public T data;public Node <T> left, right;public Node(T data) {this.data = data;left = null;right = null;}}Node <E> root;}Implement a recursive method named interiorNodesCnt method that has the following signature:public int interiorNodesCnt()The method returns the number of interior nodes present in the tree. An interior node is one that has at least one child. You can add an auxiliary method if you need to. You may not use any Java API classduring the implementation of this method. Non-recursive solutions will receive no credit.YOU CAN IMPLEMENT THE METHOD IN THE NEXT PAGE6SPACE FOR YOUR interiorNodesCnt IMPLEMENTATION75. (11 pts) Software Development and Testinga. Software is difficult because managers are cheap T or Fb. Software is difficult because programmers are stupid T or Fc. Software life cycle refers to how long software is used T or Fd. Coding is the largest component of software development T or Fe. Problem specification is more important than program testing T or Ff. The waterfall model is a software development methodology T or Fg. The waterfall model performs steps in order T or Fh. Iterative development builds many software prototypes T or Fi. Iterative development produces working code faster than waterfall model T or Fj. Unit tests should be applied before integration tests T or Fk. Black box tests may be performed by users T or F6. (21 pts) Object-Oriented DesignInheritancea. Inheritance describes a relationship between related classes T or Fb. Inheritance encourages code reuse T or Fc. Many forms of inheritance exist in Java T or Fd. Java supports combined (multiple) inheritance T or FGiven the following problem description, produce an object-oriented solution. Include asmany details as possible. Draw a UML class diagram (you may write code for Java classesONLY if you don't know UML, but will lose points if you do so). You will implement a media server system that allow users to buy two types of media:songs and movies. Movies can be classified as made-for-TV movies or theater movies.All media types has a title, cost, and duration (in minutes). Made-for-TV movies have,in addition, the network that produced the movie, and the date the movie was originallyaired. Theater movies include the box office earnings. Operations associated with theserver system are: buy a movie, buy a song, and search for media based on mediaproperties (e.g., title, box office earnings, etc.).You can write your design on the next page.8Space for your Object-Oriented UML design97. (12 pts) UML a. Provides a software blueprint for object-oriented software systems T or Fb. Can describe both static & dynamic behavior of a software system T or Fc. Name two types of UML diagrams (excluding class diagrams)Given the following Java code, draw its UML class diagram.
View Full Document
Unlocking...