CMSC132 Midterm 2 Practice Questions Problem 1 Trees a Binary search trees BST a What is the key property of a binary search tree b On average what is the complexity of doing an insertion in a binary search tree c On average what is the complexity of doing a find in a binary search tree d What is the worst case complexity of doing a find in a binary search tree e What can cause worst case behavior in a binary search tree b Binary search trees examples a Draw the binary search tree created when the following values are inserted in order 6 5 2 8 10 3 b Given the previous BST draw the tree created when the node 5 is removed c Traversals a What is a tree traversal b What is the difference between a depth first and breadth first traversal c Pre order in order and post order are all depth first traversals d Pre order traversals are faster than post order traversals e For the following binary tree provide an example of a i Preorder traversal ii Postorder traversal iii Breadth first traversal 10 5 2 45 25 30 1 T or F T or F d Given the following Java class definition for a binary tree Class Node int myValue Node left Node right Class Tree Node root root node in tree Node find int k int treeHeight void preorder Write the following code a find k Use a recursive algorithm to find a node with myValue k in tree b treeHeight Use a recursive algorithm to find the height of a tree c preorderPrint Use a recursive algorithm to print myValue for each node using a preorder traversal of the tree starting from the root Problem 2 Java Programming e True or False a Using and equals always return the same result b Variables of type Integer and int are both references c Autoboxing creates an Integer object from an int d Exceptions are used to capture run time errors f Write Java code for a Card class a Use an enumerated type for the suits in a card deck Spades Hearts Diamonds Clubs b Implement the comparable interface for Card objects so that the suits are ranked in the order listed Spades Hearts Diamonds Clubs g Write Java code for a Deck class a Uses an ArrayList to store multiple Card objects b Use an anonymous inner class to generate an Iterator over Card objects in the Deck 2 Problem 3 Heaps h Properties characteristics a What are two key properties of a heap b What operation s supported by binary search trees are not supported by heaps c On average what is the complexity of doing an insertion in a heap d On average what is the complexity of doing a find in a heap e What is the worst case complexity of doing a find in a heap f How can heaps be stored in a compact array representation g Why are heaps used to implement priority queues i Examples a Draw the heap created when the following values are inserted in order 6 5 2 8 10 3 b Given the previous heap draw the heap produced when the smallest value is removed c Show the tree representation of the following heap in array representation A B C D E F d Show the array representation of the following heap in tree representation 2 6 8 22 45 Problem 4 Compression Huffman Codes 3 25 j Compression a What are two sources of compressibility b What are two types of compression c What is a prefix code d What are Huffman codes e How do Huffman codes achieve compression f Given the following Huffman tree decode the sequence 00110010 T S 1 0 1 R 0 1 A 0 g Using the same Huffman tree encode the string arts as a sequence of 0 s and 1 s h Given the following symbol frequencies create a Huffman tree for the symbols A 5 B 8 C 4 D 6 E 7 4
View Full Document
Unlocking...