<![CDATA[
CSE143 Key to Final, Fall 2012 handout #40
1. Preorder traversal 2, 0, 5, 1, 7, 6, 3, 4, 9, 8
Inorder traversal 1, 5, 0, 7, 6, 2, 3, 9, 4, 8
Postorder traversal 1, 5, 6, 7, 0, 9, 8, 4, 3, 2
2. +------------+
| Pride |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Envy | | Sloth |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Anger | | Greed |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Gluttony | | Lust |
+------------+ +------------+
3. list1: [b, l, u, e]
list2: [s, p, o, t]
map returned: {b=s, e=t, l=p, o=u, p=l, s=b, t=e, u=o}
list1: [k, e, e, p]
list2: [s, a, f, e]
map returned: {a=e, e=p, f=e, k=s, p=e, s=k}
list1: [s, o, b, e, r]
list2: [b, o, o, k, s]
map returned: {b=o, e=k, k=e, o=b, r=s, s=r}
4. One possible solution appears below.
public void retainAll(Set<Integer> s1, Set<Integer> s2) {
Iterator<Integer> i = s1.iterator();
while (i.hasNext()) {
if (!s2.contains(i.next())) {
i.remove();
}
}
}
5. One possible solution appears below.
public int evenBranches() {
return evenBranches(overallRoot);
}
private int evenBranches(IntTreeNode root) {
if (root == null)
return 0;
else if (root.left == null && root.right == null)
return 0;
else if (root.data % 2 == 0)
return 1 + evenBranches(root.left) + evenBranches(root.right);
else
return evenBranches(root.left) + evenBranches(root.right);
}
6. One possible solution appears below.
public static Map<Point, String> recordMoves(List<Move> moves,
List<String> graveyard) {
Map<Point, String> result = new HashMap<Point, String>();
for (Move m : moves) {
Point p = new Point(m.getX(), m.getY());
if (result.containsKey(p)) {
graveyard.add(result.get(p));
}
result.put(p, m.getName());
}
return result;
}
7. Two possible solutions appear below.
public class USCurrency implements Comparable<USCurrency> {
private int totalCents;
public USCurrency(int dollars, int cents) {
totalCents = dollars * 100 + cents;
}
public int dollars() {
return totalCents / 100;
}
public int cents() {
return totalCents % 100;
}
public String toString() {
int cents = Math.abs(totalCents);
String s = cents / 100 + "." + cents % 100 / 10 + cents % 10;
if (totalCents < 0)
return "-$" + s;
else
return "$" + s;
}
public USCurrency add(USCurrency other) {
return new USCurrency(dollars() + other.dollars(),
cents() + other.cents());
}
public USCurrency subtract(USCurrency other) {
return new USCurrency(dollars() - other.dollars(),
cents() - other.cents());
}
public int compareTo(USCurrency other) {
return totalCents - other.totalCents;
}
}
public class USCurrency implements Comparable<USCurrency> {
private int dollars;
private int cents;
public USCurrency(int dollars, int cents) {
int totalCents = 100 * dollars + cents;
this.dollars = totalCents / 100;
this.cents = totalCents % 100;
}
public int dollars() {
return dollars;
}
public int cents() {
return cents;
}
public String toString() {
String s = Math.abs(dollars) + ".";
if (Math.abs(cents) < 10)
s += "0" + Math.abs(cents);
else
s += Math.abs(cents);
if (dollars < 0 || cents < 0)
return "-$" + s;
else
return "$" + s;
}
public USCurrency add(USCurrency other) {
return new USCurrency(dollars + other.dollars,
cents + other.cents);
}
public USCurrency subtract(USCurrency other) {
return new USCurrency(dollars - other.dollars,
cents - other.cents);
}
public int compareTo(USCurrency other) {
return dollars * 100 + cents - other.dollars * 100 - other.cents;
}
}
8. One possible solution appears below.
public void stretch() {
overallRoot = stretch(overallRoot);
}
private IntTreeNode stretch(IntTreeNode root) {
if (root != null) {
root.left = stretch(root.left);
root.right = stretch(root.right);
if (root.left != null && root.right == null)
root = new IntTreeNode(1, root, null);
else if (root.left == null && root.right != null)
root = new IntTreeNode(1, null, root);
}
return root;
}
9. One possible solution appears below.
public void weave(LinkedIntList other) {
if (front == null) {
front = other.front;
other.front = null;
} else if (other.front != null) {
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current2.next != null) {
ListNode temp = current1.next;
current1.next = current2;
current2 = current2.next;
current1.next.next = temp;
current1 = temp;
}
if (current1.next == null)
current1.next = current2;
else {
current2.next = current1.next;
current1.next = current2;
}
other.front = null;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011