CSE143 Sample Final, Fall 2012 handout #32 1. Binary Tree Traversals, 6 points. Consider the following tree. +---+ | 2 | +---+ / \ / \ +---+ +---+ | 7 | | 6 | +---+ +---+ / \ \ / \ \ +---+ +---+ +---+ | 9 | | 0 | | 1 | +---+ +---+ +---+ / \ / \ / \ / \ +---+ +---+ +---+ +---+ | 5 | | 3 | | 4 | | 8 | +---+ +---+ +---+ +---+ Fill in each of the traversals below: Preorder traversal __________________________________________________ Inorder traversal __________________________________________________ Postorder traversal __________________________________________________ 2. Binary Search Tree, 4 points. Draw a picture below of the binary search tree that would result from inserting the following words into an empty binary search tree in the following order: Legolas, Frodo, Sam, Merry, Pippin, Aragorn, Gimli, Boromir. 3. Collections Mystery, 5 points. Consider the following method: public List<Integer> mystery(int[][] data) { List<Integer> result = new LinkedList<Integer>(); for (int i = 0; i < data.length; i++) { int sum = 0; for (int j = 0; j < data[i].length; j++) { sum = sum + j * data[i][j]; } result.add(sum); } return result; } In the left-hand column below are specific two-dimensional arrays. Indicate in the right-hand column what values would be stored in the list returned by method mystery if the array in the left-hand column is passed as a parameter to mystery. Two-Dimensional Array Contents of List Returned --------------------------------------------------------------------- [[1, 2, 3], [4, 5, 6]] ______________________________ [[3, 4], [1, 2, 3], [], [5, 6]] ______________________________ [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ______________________________ 4. Collections Programming, 5 points. Write a method called convert that takes an array of integers as a parameter and that returns a map that contains the nonzero elements of the array (mapping an integer index to an integer value). For example, if an array called list stores these values: [0, 19, 4, 0, 0, 0, 12, 0, 0, 0, 9, 18] then the call convert(list) should return the following map: {1=19, 2=4, 6=12, 10=9, 11=18} Your map should store the keys in increasing numerical order. The array passed as a parameter should be not be changed. 5. Binary Trees, 10 points. Write a toString method for a binary tree of integers. The method should return "empty" for an empty tree. For a leaf node, it should return the data in the node as a String. For a branch node, it should return a parenthesized String that has three elements separated by commas: the data at the root followed by a String representation of the left subtree followed by a String representation of the right subtree. For example, if a variable t stores a reference to the following tree: +---+ | 2 | +---+ / \ +---+ +---+ | 8 | | 1 | +---+ +---+ / / \ +---+ +---+ +---+ | 0 | | 7 | | 6 | +---+ +---+ +---+ / \ +---+ +---+ | 4 | | 9 | +---+ +---+ then the call t.toString() should return the following String: "(2, (8, 0, empty), (1, (7, 4, empty), (6, empty, 9)))" The quotes above are used to indicate that this is a String but should not be included in the String that you return. You are writing a public method for a binary tree class defined as follows: public class IntTreeNode { public int data; // data stored in this node public IntTreeNode left; // reference to left subtree public IntTreeNode right; // reference to right subtree <constructors> } public class IntTree { private IntTreeNode overallRoot; <methods> } You may define private helper methods to solve this problem, but otherwise you may not call any other methods of the class. You may not define any auxiliary data structures to solve this problem. 6. Collections Programming, 10 points. Write a method called sumStrings takes a map whose keys are strings and whose values are points and that returns a map that associates each point with the sum of the lengths of the strings it is associated with in the first map. For example, suppose that a map called data has the following associations: {a=[x=1,y=3], apple=[x=7,y=7], be=[x=4,y=7], bear=[x=7,y=4], carpet=[x=2,y=19], cat=[x=1,y=3], dog=[x=2,y=18], specialty=[x=7,y=4], student=[x=1,y=3], umbrella=[x=42,y=8]} Then the call sumStrings(data) should return the following map: {[x=7,y=7]=5, [x=42,y=8]=8, [x=2,y=18]=3, [x=1,y=3]=11, [x=2,y=19]=6, [x=7,y=4]=13, [x=4,y=7]=2} Notice that the point [x=7,y=7] maps to 5 in the result because it was associated with a string of length 5 in the original ("apple"). Notice that [x=1,y=3] maps to 11 because it was associated with three strings ("a", "cat", "student") whose lengths add up to 11 (1, 3, 7). Your method should construct the new map and can construct iterators but should otherwise not construct any new data structures. It should also not modify the map passed as a parameter and it should be reasonably efficient. 7. Comparable class, 20 points. Define a class called TimeSpan that keeps track of an amount of time. A time span can be thought of in two ways. You can think of it as being a certain number of hours, minutes, and seconds where each hour is composed of 60 minutes and each minute is composed of 60 seconds. Or you can think of it as the total number of seconds. The class has the following public methods: TimeSpan(hrs, min, sec) constructs a TimeSpan object with the given hours, minutes, and seconds hours() returns the number of hours minutes() returns the number of minutes (0 to 59) seconds() returns the number of seconds (0 to 59) totalSeconds() returns the total number of seconds including the minutes and hours components add(other) returns a new TimeSpan object formed by adding this TimeSpan to the other TimeSpan toString() returns a string in the form "hhh:mm:ss" For example, the following code constructs three TimeSpan objects: TimeSpan t1 = new TimeSpan(18, 3, 54); TimeSpan t2 = new TimeSpan(95, 58, 7); TimeSpan t3 = t1.add(t2); The first TimeSpan object is expressed as 18 hours, 3 minutes, and 54 seconds. The totalSeconds method would report this as 65034 seconds. The call t1.toString() should produce "18:03:54". Notice that the minutes are reported as two digits even when it is a single digit. The same should be true of the seconds, so t2.toString() should produce the string "95:58:07". Your class should make sure that minutes and seconds are always reported as being between 0 and 59. When t1 and t2 are added together to produce t3, the resulting time should be reported as 114 hours, 2 minutes, and 1 second, with t3.toString() returning "114:02:01". Your constructor should throw an IllegalArgumentException if any value passed to it is negative. It should fix values of minutes and seconds that are higher than 59, adjusting hours and minutes appropriately. For example, given the following call: TimeSpan t4 = new TimeSpan(4, 65, 100); the resulting TimeSpan object should be reported as 5 hours, 6 minutes, and 40 seconds with t4.toString() returning "5:06:40". The TimeSpan class should implement the Comparable<E> interface, where a shorter amount of time is considered less than a longer amount of time. 8. Binary Trees, 20 points. Write a method called add that takes as a parameter a reference to a second binary tree and that adds the values in the second tree to this tree. If the method is called as follows: tree1.add(tree2); it should add all values in tree2 to the corresponding nodes in tree1. In other words, the value stored at the root of tree2 should be added to the value stored at the root of tree1 and the values in tree2's left and right subtrees should be added to the corresponding positions in tree1's left and right subtrees. The values in tree2 should not be changed by your method. initial tree1 initial tree2 final tree1 +---+ +---+ +---+ | 1 | | 2 | | 3 | +---+ +---+ +---+ / \ / \ / \ +---+ +---+ +---+ +---+ +---+ +---+ | 4 | | 7 | | 3 | | 1 | | 7 | | 8 | +---+ +---+ +---+ +---+ +---+ +---+ If tree1 has a node that has no corresponding node in tree2, then that node is unchanged. For example, if tree2 is empty, tree1 is not changed at all. It is also possible that tree2 will have one or more nodes that have no corresponding node in tree1. For each such node, create a new node in tree1 in the corresponding position with the value stored in tree2's node. For example: initial tree1 initial tree2 final tree1 +---+ +---+ +---+ | 6 | | 1 | | 7 | +---+ +---+ +---+ / / \ / \ +---+ +---+ +---+ +---+ +---+ | 2 | | 4 | | 5 | | 6 | | 5 | +---+ +---+ +---+ +---+ +---+ / \ / \ +---+ +---+ +---+ +---+ | 8 | | 2 | | 8 | | 2 | +---+ +---+ +---+ +---+ You are writing a public method for a binary tree class defined as follows: public class IntTreeNode { public int data; // data stored in this node public IntTreeNode left; // reference to left subtree public IntTreeNode right; // reference to right subtree // post: constructs an IntTreeNode with the given data and links public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) { this.data = data; this.left = left; this.right = right; } } public class IntTree { private IntTreeNode overallRoot; <methods> } You are writing a method that will become part of the IntTree class. You may define private helper methods to solve this problem, but otherwise you may not assume that any particular methods are available. You are NOT to replace any of the existing nodes in the tree. You will, however, construct new nodes to be inserted into the tree as described above. 9. Linked Lists, 20 points. Write a method called rearrange that rearranges the order of a list of integers so that all of the values in even-numbered positions appear in reverse order followed by all of the values in odd-numbered positions in forward order. We are using zero-based indexing, as with Java arrays and lists, where the first element is considered to be at position 0. For example, if a variable called list stores these values: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] and you make the following call: list.rearrange(); the list should store the following values after the call: [8, 6, 4, 2, 0, 1, 3, 5, 7, 9] In this example the values in the original list were equal to their positions and there were an even number of elements, but that won't necessarily be the case. For example, if the list had instead stored: [3, 8, 15, 9, 4, 42, 5] then after a call on rearrange it would store: [5, 4, 15, 3, 8, 9, 42] If the list has fewer than two elements, it should be unchanged by a call on rearrange. You are writing a public method for a linked list class defined as follows: public class ListNode { public int data; // data stored in this node public ListNode next; // link to next node in the list <constructors> } public class LinkedIntList { private ListNode front; <methods> } You are writing a method that will become part of the LinkedIntList class. You may define private helper methods to solve this problem, but otherwise you may not assume that any particular methods are available. You are allowed to define your own variables of type ListNode, but you may not construct any new nodes, and you may not use any auxiliary data structure to solve this problem (no array, ArrayList, stack, queue, String, etc). You also may not change any data fields of the nodes. You MUST solve this problem by rearranging the links of the list. Your solution must run in O(n) time where n is the length of the list.
Stuart Reges
Last modified: Fri Nov 30 17:46:52 PST 2012