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 songs;
private Map mp3s;
public CachedSongList(UserData data) {
super(data);
songs = new LinkedList();
mp3s = new HashMap();
}
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 {
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;
}
}
}