CSE143 Key to Sample Final (Part 1) handout #33 1. Binary Tree Traversals, 6 points. Preorder traversal 2, 6, 0, 1, 3, 5, 7, 9, 8, 4 Inorder traversal 0, 6, 3, 1, 5, 2, 7, 8, 9, 4 Postorder traversal 0, 3, 5, 1, 6, 8, 4, 9, 7, 2 2. Binary Search Tree, 4 points. +------------+ | Kirk | +------------+ / \ / \ / \ +------------+ +------------+ | Chekov | | Spock | +------------+ +------------+ / \ / \ / \ +------------+ +------------+ | Scotty | | Uhura | +------------+ +------------+ / / / / / / +------------+ +------------+ | McCoy | | Sulu | +------------+ +------------+ 3. Programming with inheritance, 20 points. One possible solution appears below. public class AnalyzingDocumentList extends DocumentList { private Map<Integer, Integer> counts; private int stateCount; public AnalyzingDocumentList(int capacity) { super(capacity); counts = new HashMap<Integer, Integer>(); counts.put(0, 1); stateCount = 1; } public void add(Document d) { super.add(d); stateUpdate(); } public void add(int index, Document d) { super.add(index, d); stateUpdate(); } public void remove(int index) { super.remove(index); stateUpdate(); } private void stateUpdate() { stateCount++; int size = size(); if (!counts.containsKey(size)) counts.put(size, 1); else counts.put(size, counts.get(size) + 1); } public int totalStates() { return stateCount; } public int sizeCount(int size) { if (counts.containsKey(size)) return counts.get(size); else return 0; } } 4. Linked Lists, 20 points. Two possible solutions appear below. The second is much shorter because it uses recursion. public void reverse3() { if (front != null && front.next != null && front.next.next != null) { ListNode temp = front; front = front.next.next; ListNode temp2 = front.next; front.next = temp.next; temp.next.next = temp; temp.next = temp2; while (temp.next != null && temp.next.next != null && temp.next.next.next != null) { temp2 = temp.next; temp.next = temp.next.next.next; temp = temp2; temp2 = temp.next.next.next; temp.next.next.next = temp.next; temp.next.next = temp; temp.next = temp2; } } } public void reverse3() { front = reverse3(front); } private ListNode reverse3(ListNode lst) { if (lst != null && lst.next != null && lst.next.next != null) { ListNode temp = lst; lst = lst.next.next; ListNode temp2 = lst.next; lst.next = temp.next; temp.next.next = temp; temp.next = temp2; temp.next = reverse3(temp.next); } return lst; }