CSE143 Key to Final, Spring 2008 handout #38 1. Binary Tree Traversals, 6 points. Preorder traversal 0, 4, 7, 9, 2, 6, 1, 8, 5, 3 Inorder traversal 4, 0, 2, 9, 7, 8, 1, 6, 5, 3 Postorder traversal 4, 2, 9, 8, 1, 3, 5, 6, 7, 0 2. Binary Search Tree, 4 points. +------------+ | Lisa | +------------+ / \ / \ / \ +------------+ +------------+ | Bart | | Marge | +------------+ +------------+ \ / \ \ / \ \ / \ +------------+ +------------+ +------------+ | Homer | | Maggie | | Smithers | +------------+ +------------+ +------------+ / / / +------------+ | Flanders | +------------+ 3. Binary Trees, 10 points. One possible solution appears below. public boolean equals(IntTree other) { return equals(overallRoot, other.overallRoot); } private boolean equals(IntTreeNode root1, IntTreeNode root2) { if (root1 == null || root2 == null) return root1 == null && root2 == null; else return root1.data == root2.data && equals(root1.left, root2.left) && equals(root1.right, root2.right); } 4. Programming with inheritance, 20 points. One possible solution appears below. public class CachedSongList extends SongList { private List<String> songs; private Map<String, MP3> mp3s; public CachedSongList(UserData data) { super(data); songs = new LinkedList<String>(); mp3s = new HashMap<String, MP3>(); } public MP3 get(String name) { if (mp3s.containsKey(name)) { songs.remove(name); songs.add(0, name); return mp3s.get(name); } else { MP3 response = super.get(name); songs.add(0, name); if (songs.size() == 11) { mp3s.remove(songs.get(10)); songs.remove(10); } mp3s.put(name, response); return response; } } public String getRecent(int index) { return songs.get(index); } public int recentSize() { if (songs.size() != mp3s.size()) throw new IllegalStateException(); return songs.size(); } } 5. Comparable class, 20 points. 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(); } } 6. Binary Trees, 20 points. One possible solution appears below. public IntTree combineWith(IntTree other) { IntTree result = new IntTree(); result.overallRoot = combine(overallRoot, other.overallRoot); return result; } private IntTreeNode combine(IntTreeNode root1, IntTreeNode root2) { if (root1 == null) if (root2 == null) return null; else // root2 != null return new IntTreeNode(2, combine(null, root2.left), combine(null, root2.right)); else // root1 != null if (root2 == null) return new IntTreeNode(1, combine(root1.left, null), combine(root1.right, null)); else return new IntTreeNode(3, combine(root1.left, root2.left), combine(root1.right, root2.right)); } 7. Linked Lists, 20 points. One possible solution appears below. public void reorder() { if (front != null) { ListNode current = front; while (current.next != null) { if (current.next.data < 0) { ListNode temp = current.next; current.next = current.next.next; temp.next = front; front = temp; } else current = current.next; } } }
Stuart Reges
Last modified: Wed Jun 11 17:42:28 PDT 2008