Grader Use Only 1 2 3 4 5 6 7 Total Honors CMSC132 Fall 2006 Midterm 2 22 14 10 10 11 21 12 100 15 First 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 1 2 1 22 pts Trees Search Trees Heaps a b c d e f g h i j k Trees are hierarchical data structures A tree node can have multiple children A tree node can have multiple parents A leaf node can have up to 2 children A binary tree node can have up to 2 children A binary tree is balanced if most interior nodes have 2 children A binary tree is degenerate if more than 100 nodes have only 1 child A binary tree is perfect if no node has only 1 child A tree traversal visits every node in the tree Preorder traversals are faster than postorder traversals Breadth first traversals are slower than depth first traverals T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F For a binary search tree l The value of a node is always greater than the values of its children m The left child s value is always smaller than the value of the right child n The of steps required to find a value is proportional to the tree s height o The of steps required to delete a value is always O log n p 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 T or F For 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 r The left child s value is always smaller than the value of the right child s The of steps required to find a value is proportional to the tree s height t The of steps required to delete a value is always O log n T or F T or F T or F T or F u A priority queue allows higher priority elements to be dequeued first v A priority queue of size n allows elements to be inserted in O 1 time T or F T or F 3 2 14 pts Trees Heaps Use the following binary tree heap to answer the questions that follow 6 8 1 3 9 1 1 1 4 a List the order nodes are traversed in an in order traversal of the tree b List the order nodes are traversed in a breadth first traversal of the tree c Draw the heap as it would be stored in an array d 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 4 a Create a Huffman tree for the symbols A B C and D which have the following frequencies A 3 B 6 C 8 D 7 Assign 1s and 0s to your Huffman tree b 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 Trees The following Java class definition for a binary tree will be used to answer the question that follow 5 public 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 class during the implementation of this method Non recursive solutions will receive no credit YOU CAN IMPLEMENT THE METHOD IN THE NEXT PAGE 6 SPACE FOR YOUR interiorNodesCnt IMPLEMENTATION 7 5 11 pts Software Development and Testing a b c d e f g h i j k 6 Software is difficult because managers are cheap Software is difficult because programmers are stupid Software life cycle refers to how long software is used Coding is the largest component of software development Problem specification is more important than program testing The waterfall model is a software development methodology The waterfall model performs steps in order Iterative development builds many software prototypes Iterative development produces working code faster than waterfall model Unit tests should be applied before integration tests Black box tests may be performed by users T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F T or F 21 pts Object Oriented Design Inheritance a Inheritance describes a relationship between related classes b Inheritance encourages code reuse c Many forms of inheritance exist in Java d Java supports combined multiple inheritance T or F T or F T or F T or F Given the following problem description produce an object oriented solution Include as many details as possible Draw a UML class diagram you may write code for Java classes ONLY 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 originally aired Theater movies include the box office earnings Operations associated with the server system are buy a movie buy a song and search for media based on media properties e g title box office earnings etc You can write your design on the next page 8 Space for your Object Oriented UML design 9 7 12 pts UML a Provides a software blueprint for object oriented software systems b Can describe both static dynamic behavior of a software system c Name two types of …
View Full Document
Unlocking...