CSE143 Key to Sample Final, Fall 2012 handout #39 1. Preorder traversal 2, 7, 9, 0, 5, 3, 6, 1, 4, 8 Inorder traversal 9, 7, 5, 0, 3, 2, 6, 4, 1, 8 Postorder traversal 9, 5, 3, 0, 7, 4, 8, 1, 6, 2 2. +------------+ | Legolas | +------------+ / \ / \ / \ +-----------+ +---------+ | Frodo | | Sam | +-----------+ +---------+ / \ / / \ / / \ / +-------------+ +-----------+ +-----------+ | Aragorn | | Gimli | | Merry | +-------------+ +-----------+ +-----------+ \ \ \ \ \ \ +-------------+ +------------+ | Boromir | | Pippin | +-------------+ +------------+ 3. Two-Dimensional Array Contents of List Returned --------------------------------------------------------------------- [[1, 2, 3], [4, 5, 6]] [8, 17] [[3, 4], [1, 2, 3], [], [5, 6]] [4, 8, 0, 6] [[1, 2, 3], [4, 5, 6], [7, 8, 9]] [8, 17, 26] 4. One possible solution appears below. public static Map<Integer, Integer> convert(int[] list) { Map<Integer, Integer> result = new TreeMap<Integer, Integer>(); for (int i = 0; i < list.length; i++) { if (list[i] != 0) { result.put(i, list[i]); } } return result; } 5. One possible solution appears below. public String toString() { return toString(overallRoot); } private String toString(IntTreeNode root) { if (root == null) return "empty"; else if (root.left == null && root.right == null) return "" + root.data; else return "(" + root.data + ", " + toString(root.left) + ", " + toString(root.right) + ")"; } 6. One possible solution appears below. public static Map<Point, Integer> sumStrings(Map<String, Point> data) { Map<Point, Integer> result = new HashMap<Point, Integer>(); for (String s : data.keySet()) { Point p = data.get(s); if (!result.containsKey(p)) { result.put(p, s.length()); } else { result.put(p, result.get(p) + s.length()); } } return result; } 7. Two possible solutions appear below. public class TimeSpan implements Comparable<TimeSpan> { private int totalSeconds; public TimeSpan(int hours, int minutes, int seconds) { if (hours < 0 || minutes < 0 || seconds < 0) { throw new IllegalArgumentException(); } totalSeconds = seconds + 60 * (minutes + 60 * hours); } public int hours() { return totalSeconds / 3600; } public int minutes() { return totalSeconds % 3600 / 60; } public int seconds() { return totalSeconds % 60; } public int totalSeconds() { return totalSeconds; } public String toString() { return hours() + ":" + minutes() / 10 + minutes() % 10 + ":" + seconds() / 10 + seconds() % 10; } public TimeSpan add(TimeSpan other) { TimeSpan result = new TimeSpan(0, 0, 0); result.totalSeconds = totalSeconds + other.totalSeconds; return result; } public int compareTo(TimeSpan other) { return this.totalSeconds - other.totalSeconds; } } public class TimeSpan implements Comparable<TimeSpan> { private int hours, minutes, seconds; public TimeSpan(int hours, int minutes, int seconds) { if (hours < 0 || minutes < 0 || seconds < 0) { throw new IllegalArgumentException(); } int total = seconds + 60 * (minutes + 60 * hours); this.seconds = total % 60; this.minutes = total / 60 % 60; this.hours = total / 3600; } public int hours() { return hours; } public int minutes() { return minutes; } public int seconds() { return seconds; } public int totalSeconds() { return seconds + 60 * (minutes + 60 * hours); } public String toString() { return hours + ":" + minutes / 10 + minutes % 10 + ":" + seconds / 10 + seconds % 10; } public TimeSpan add(TimeSpan other) { return new TimeSpan(hours + other.hours, minutes + other.minutes, seconds + other.seconds); } public int compareTo(TimeSpan other) { if (hours != other.hours) return hours - other.hours; else if (minutes != other.minutes) return minutes - other.minutes; else return seconds - other.seconds; } } 8. One possible solution appears below. public void add(IntTree other) { overallRoot = add(overallRoot, other.overallRoot); } private IntTreeNode add(IntTreeNode root1, IntTreeNode root2) { if (root2 != null) { if (root1 == null) root1 = new IntTreeNode(0); root1.data += root2.data; root1.left = add(root1.left, root2.left); root1.right = add(root1.right, root2.right); } return root1; } 9. One possible solution appears below. public void rearrange() { if (front != null && front.next != null) { ListNode current = front.next; while (current != null && current.next != null) { ListNode temp = current.next; current.next = current.next.next; temp.next = front; front = temp; current = current.next; } } }
Stuart Reges
Last modified: Fri Dec 7 15:21:00 PST 2012