CSE143X Key to Final, Fall 2024 handout #26 1. Preorder traversal 3, 5, 9, 6, 0, 2, 7, 8, 4, 1 Inorder traversal 3, 0, 6, 2, 9, 5, 4, 8, 7, 1 Postorder traversal 0, 2, 6, 9, 4, 8, 1, 7, 5, 3 2. +------------+ | Luke | +------------+ / \ / \ +------------+ +------------+ | Kylo | | Poe | +------------+ +------------+ / / \ / / \ +------------+ +------------+ +------------+ | BB8 | | Maz | | Rey | +------------+ +------------+ +------------+ \ \ +------------+ | Finn | +------------+ 3. Two-Dimensional Array Contents of Set Returned ------------------------------------------------------------------ [[1, 2], [3, 4]] [1, 2, 13, 14] [[7], [], [8, 8, 9, 10]] [7, 28, 29, 30] [[3, 14], [5, 13, 4], [4, 3, 1]] [3, 14, 15, 21, 23, 24] 4. One possible solution appears below. public void recordTrip(Map<String, Set<String>> trips, String person, String place) { if (!trips.containsKey(person)) { trips.put(person, new TreeSet<>()); } trips.get(person).add(place); } 5. Binary Trees, 10 points. One possible solution appears below. public void printLeaves() { if (overallRoot == null) { System.out.println("no leaves"); } else { System.out.print("leaves:"); printLeaves(overallRoot); System.out.println(); } } private void printLeaves(IntTreeNode root) { if (root != null) { if (root.left == null && root.right == null) System.out.print(" " + root.data); } else { printLeaves(root.right); printLeaves(root.left); } } } 6. One possible solution appears below. public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) { Set<Point> removed = new HashSet<>(); if (points.containsKey(n)) { Iterator<Point> itr = points.get(n).iterator(); while (itr.hasNext()) { Point p = itr.next(); if (p.getX() < p.getY()) { itr.remove(); removed.add(p); } } } return removed; } 7. One possible solution appears below. public class ItemOrder implements Comparable<ItemOrder> { private String item; private int quantity; private int pricePer; private String note; public ItemOrder(String item, int quantity, int pricePer) { this(item, null, quantity, pricePer); } public ItemOrder(String item, String note, int quantity, int pricePer) { this.item = item; this.note = note; this.quantity = quantity; this.pricePer = pricePer; } public String getItem() { return item; } public int getPrice() { return quantity * pricePer; } public String toString() { String text = "item #" + item; if (note != null) { text += " (" + note + ")"; } text = text + ": " + quantity + "@" + moneyString(pricePer) + " = " + moneyString(getPrice()); return text; } private String moneyString(int cents) { return "$" + cents / 100 + "." + cents % 100 / 10 + cents % 10; } public int compareTo(ItemOrder other) { if (!item.equals(other.item)) { return item.compareTo(other.item); } else { return other.getPrice() - getPrice(); } } } 8. One possible solution appears below. public void makeFull() { overallRoot = makeFull(overallRoot, 1); } private IntTreeNode makeFull(IntTreeNode root, int level) { if (root != null) { if (root.left == null && root.right != null) { root = new IntTreeNode(-level, root, root.right); root.left.right = null; } else if (root.left != null && root.right == null) { root = new IntTreeNode(-level, root.left, root); root.right.left = null; } root.left = makeFull(root.left, level + 1); root.right = makeFull(root.right, level + 1); } return root; } 9. Two possible solutions appear below. public void switchEvens(LinkedIntList other) { if (front != null && other.front != null) { ListNode temp = other.front; other.front = front; front = temp; temp = front.next; front.next = other.front.next; other.front.next = temp; ListNode curr1 = front.next; ListNode curr2 = other.front.next; while (curr1 != null && curr2 != null && curr1.next != null && curr2.next != null) { temp = curr2.next; curr2.next = curr1.next; curr1.next = temp; temp = curr2.next.next; curr2.next.next = curr1.next.next; curr1.next.next = temp; curr1 = curr1.next.next; curr2 = curr2.next.next; } } } public void switchEvens(LinkedIntList other) { if (front != null && other.front != null) { ListNode temp = other.front; other.front = front; front = temp; ListNode curr1 = front; ListNode curr2 = other.front; int count = 0; while (curr1.next != null && curr2.next != null) { count++; temp = curr2.next; curr2.next = curr1.next; curr1.next = temp; curr1 = curr1.next; curr2 = curr2.next; } if (count % 2 == 0) { temp = curr2.next; curr2.next = curr1.next; curr1.next = temp; } } }
Stuart Reges
Last modified: Thu Dec 19 14:22:56 PST 2024