Grader Use Only 1 2 3 4 5 6 Total CMSC132 Summer 2007 Midterm 2 KEY 20 10 12 12 10 36 100 First Name Last Name Student ID Section time TA General Rules Read 1 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 True or False 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 20 pts Heaps Trees Use the following binary tree heap to answer the questions that follow 1 8 9 1 0 1 1 a 1 3 1 2 1 4 What is the big O notation for heapsort Answer O nlog n b Heaps are balanced trees True False Answer True c A heap is a binary search tree True False Answer False d List the order nodes are traversed in an depth search traversal of the tree Answer 8 9 11 13 10 12 14 One possible traversal e List the order nodes are traversed in a breadth first traversal of the tree Answer 8 9 10 11 13 12 14 One possible traversal f 4 pts Draw the heap that would result from inserting 5 in the above heap 5 8 9 1 0 1 3 1 2 1 4 1 1 g 4 pts Draw the heap that would result by deleting 8 from the original heap 2 9 1 1 1 0 1 4 2 1 3 1 2 10 pts Huffman A B 0 1 C D 0 0 1 0 a E 1 1 2 pts Use the above Huffman tree to encode the string BD Show the resulting code Answer 00110 b 2 pts Use the above Huffman tree to decode the code 0111 Show the resulting string Answer CE c 6 pts Create a Huffman tree for the symbols M P R and T which have the following frequencies M 4 P 5 R 8 T 7 You don t need to assign 0 s and 1 s Answer M P 0 1 0 3 R 0 T 1 1 12 pts Hashing a 2 pts Using hashing we can achieve a complexity of O 1 during the retrieval of an element 3 True False Answer True b 2 pts What is the load factor i ii iii iv Number of entries in the hash table divided by table size Maximum number of entries that can be placed in the table The load generated by the multiplicative congruency method None of the above Answer i c 2 pts The hashCode method for a class always returns the number 14 Is this a valid hashCode method for the class True False Answer True d 2 pts Hashing is efficient for a load factor that is less than i ii iii iv 99 90 80 None of the above Answer ii e 4 pts Mentioned two properties of a good hash function Notice we are not asking about the properties of the Java hashCode method Answer Any two valid ones Possible ones 1 Cheap to compute 2 Good distribution of values 4 16 pts Dijkstras Algorithm 1 D 2 4 B 2 A E 2 7 F 5 C 4 Run Dijkstra s shortest path algorithm on the previous graph using B as the start vertex Show the entries in the following table after adding the first 3 nodes B 2 other nodes to the set S of processed nodes as defined by Djikstra s algorithm Keep in mind that after adding a node to the set S you must adjust the cost predecessor of the appropriate successor nodes Answer A B C 4 D E F 5 LowestCost 3 0 2 5 5 Predecessor D none none B A B 10 pts GUIs Consider the following Java Swing code that uses a JSlider object A JSlider object let s the user graphically select a value by sliding a knob The following is a snapshot of a slider The stateChanged method is called when we move the knob public class JSliderPanel extends JPanel private JSlider jSlider public JSliderPanel add jSlider new JSlider JSlider HORIZONTAL jSlider addChangeListener new Handler class Handler implements ChangeListener public void stateChanged ChangeEvent e System out println Slider action a 2 pts In the above code which class represents the view Answer JSliderPanel b 2 pts In the above code which class represents the controller Answer Handler c 6 pts Write a new JSliderPanel constructor that uses an anonymous inner class to implement the same ChangeListener for the JSlider Answer Code that should appear in YOUR CODE HERE jSlider addChangeListener new ChangeListener public void stateChanged ChangeEvent e System out println Slider action public class JSliderPanel extends JPanel private JSlider jSlider public JSliderPanel add jSlider new JSlider JSlider HORIZONTAL YOUR CODE HERE 6 36 pts Binary Trees a 2 pts We generate a balanced binary search tree when elements are inserted in sorted order True False 5 Answer False b The following Java class definition for a binary search tree will be used to answer the questions below Feel free to add an auxiliary method during the implementation of any method Nonrecursive solutions will receive no credit public class BinarySearchTree E class Node T T data Node T left right public Node T data this data data left right null Node E root Tree Root YOU MUST IMPLEMENT A DEFAULT CONSTRUCTOR public int numberOfLeaves YOU MUST IMPLEMENT THIS METHOD public ArrayList E decreasingOrder YOU MUST IMPLEMENT THIS METHOD i 2 pts Constructor Define a default constructor that creates an empty binary search tree Answer public BinarySearchTree root null ii 4 pts isEmpty Returns true if the tree is empty and false otherwise Answer public boolean isEmpty if root null return true return false iii 14 pts numberOfLeaves Implement a method named numberOfLeaves The method returns the number of leave nodes present in the tree Answer public int numberOfLeaves return numberOfLeavesAux root private int numberOfLeavesAux Node E currRoot 6 if currRoot null if currRoot left null currRoot right null return 1 else if currRoot left null return numberOfLeavesAux currRoot right else if currRoot right null return numberOfLeavesAux currRoot left else return numberOfLeavesAux currRoot left numberOfLeavesAux currRoot right return 0 iv 14 pts decreasingOrder Implement a method named decreasingOrder It returns an array with the data elements of the tree in decreasing order public ArrayList E decreasingOrder ArrayList E result new ArrayList E decreasingOrderAux root result return result private void decreasingOrderAux Node E currRoot ArrayList E result if currRoot null if currRoot right null decreasingOrderAux currRoot right result result add currRoot data if currRoot left null decreasingOrderAux currRoot left result YOU CAN IMPLEMENT THE METHODS ON THE NEXT PAGE 7
View Full Document
Unlocking...