Practice Solved Questions for Midterm Exam - Object Oriented Programming II | CMSC 132, Exams of Computer Science

Download Practice Solved Questions for Midterm Exam - Object Oriented Programming II | CMSC 132 and more Exams Computer Science in PDF only on Docsity! CMSC132, Midterm #2, Practice Questions Partial Solutions Problem 1 Trees a. Binary search trees (BST) a. What is the key property of a binary search tree? Values in left subtree < value at root, values in right subtree > value at root b. On average, what is the complexity of doing an insertion in a binary search tree? O(log(n)) c. On average, what is the complexity of doing a find in a binary search tree? O(log(n)) d. What is the worst-case complexity of doing a find in a binary search tree? O(n) e. What can cause worst-case behavior in a binary search tree? Unbalanced / degenerate binary trees 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? Visiting all the nodes in a tree b. What is the difference between a depth-first and breadth-first traversal? Depth-first traversal visits entire subtree first, breadth-first traversal visits nodes in order of their distance from the root c. Pre-order, in-order, and post-order are all depth-first traversals T or F d. Pre-order traversals are faster than post-order traversals T or F e. For the following binary tree, provide an example of a i. Preorder traversal 10, 5, 2, 25, 45, 30 or 10, 45, 30, 5, 25, 2 or … ii. Postorder traversal 2, 25, 5, 30, 45, 10 or 25, 2, 5, 30, 45, 10 or … iii. Breadth-first traversal 10, 5, 45, 2, 25, 30 or 10, 45, 5, 30, 2, 25 or … 1 5 1 0 45 2 25 3 0 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. Java Language Features a. Using “==” and .equals() always return the same result T or F b. Variables of type Integer and int are both references T or F c. Autoboxing creates an Integer object from an int T or F d. Exceptions are used to capture run-time errors T or F 2 Assign node locations in array based on formula for array index g. Why are heaps used to implement priority queues? Can efficiently select items with higher priority first 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, 22, 8, 45, 25] 5 6 2 2 2 8 4 5 2 5 Problem 4 Compression & Huffman Codes j. Compression a. What are two sources of compressibility? Redundancy & human perception b. What are two types of compression? Lossy & lossless c. What is a prefix code? No prefix of a code appears as another code d. What are Huffman codes? Binary prefix code based on symbol frequencies e. How do Huffman codes achieve compression? Taking advantage of redundancy of frequently appearing symbols f. Given the following Huffman tree, decode the sequence “00110010” AASAR g. Using the same Huffman tree, encode the string “arts” as a sequence of 0’s and 1’s 010111110 h. Given the following symbol frequencies, create a Huffman tree for the symbols A = 5, B = 8, C = 4, D = 6, E = 7 6 T R S A 1 1 1 0 0 0