CSE143 Key to Sample Final, Spring 2021 handout #24 1. Preorder traversal 7, 6, 3, 8, 5, 0, 2, 1, 9, 4 Inorder traversal 3, 8, 6, 7, 2, 0, 1, 5, 9, 4 Postorder traversal 8, 3, 6, 2, 1, 0, 4, 9, 5, 7 2. +------------+ | Java | +------------+ / \ / \ +------------+ +------------+ | C | | Rust | +------------+ +------------+ \ / \ \ / \ +------------+ +------------+ +------------+ | Go | | Kotlin | | Swift | +------------+ +------------+ +------------+ \ \ +------------+ | Python | +------------+ 3. Method Call Contents of Set Returned ----------------------------------------------- mystery(grid, 3, 1) [6] mystery(grid, 1, 2) [3, 5, 6] mystery(grid, 3, 3) [1, 3, 4, 5, 6, 9] 4. One possible solution appears below. public static Set<Point> switchXY(Set<Point> points) { Set<Point> result = new HashSet<Point>(); Iterator<Point> itr = points.iterator(); while (itr.hasNext()) { Point p = itr.next(); if (p.getX() == p.getY()) { itr.remove(); } else { result.add(new Point(p.getY(), p.getX())); } } return result; } 5. Binary Trees, 10 points. One possible solution appears below. public List<Integer> inorderList() { List<Integer> result = new ArrayList<Integer>(); inorderList(result, overallRoot); return result; } private void inorderList(List<Integer> result, IntTreeNode root) { if (root != null) { inorderList(result, root.left); result.add(root.data); inorderList(result, root.right); } } 6. One possible solution appears below. public static int recordDate(Map<String, List<String>> dates, String name1, String name2) { if (!dates.containsKey(name1)) { dates.put(name1, new LinkedList<String>()); } if (!dates.containsKey(name2)) { dates.put(name2, new LinkedList<String>()); } dates.get(name1).add(0, name2); dates.get(name2).add(0, name1); int n = 0; for (String s : dates.get(name1)) { if (s.equals(name2)) { n++; } } return n; } 7. One possible solution appears below. public class FoodData implements Comparable<FoodData> { private String name; private double fat; private double carbs; private double protein; public FoodData(String name, double fat, double carbs, double protein) { if (fat < 0 || carbs < 0 || protein < 0) { throw new IllegalArgumentException(); } this.name = name; this.fat = fat; this.carbs = carbs; this.protein = protein; } public String getName() { return name; } public double getCalories() { return 9 * fat + 4 * (carbs + protein); } public double percentFat() { return 100.0 * (9 * fat / getCalories()); } public String toString() { return name + ": " + fat + "g fat, " + carbs + "g carbohydrates, " + protein + "g protein"; } public int compareTo(FoodData other) { double difference = percentFat() - other.percentFat(); if (difference < 0) { return -1; } else if (difference > 0) { return 1; } else { return name.compareTo(other.name); } } } 8. One possible solution appears below. public void tighten() { overallRoot = tighten(overallRoot); } private IntTreeNode tighten(IntTreeNode root) { if (root != null) { root.left = tighten(root.left); root.right = tighten(root.right); if (root.left == null && root.right != null) { root = root.right; } else if (root.left != null && root.right == null) { root = root.left; } } return root; } 9. One possible solution appears below. public int shiftLastOf3() { int count = 0; if (front != null && front.next != null && front.next.next != null) { ListNode curr1 = front; ListNode oldFront = curr1; front = front.next.next; ListNode curr2 = front; curr1.next.next = curr2.next; curr1 = curr1.next.next; count++; while (curr1 != null && curr1.next != null && curr1.next.next != null) { curr2.next = curr1.next.next; curr2 = curr2.next; curr1.next.next = curr2.next; curr1 = curr1.next.next; count++; } curr2.next = oldFront; } return count; }
Stuart Reges