<![CDATA[
CSE143 Key to Final, Autumn 2017 handout #26
1. Preorder traversal 7, 2, 3, 8, 4, 1, 9, 6, 0, 5
Inorder traversal 3, 8, 2, 4, 1, 7, 6, 9, 5, 0
Postorder traversal 8, 3, 1, 4, 2, 6, 5, 0, 9, 7
3. Method Call Contents of Set Returned
-----------------------------------------------
mystery(grid, 0) [2, 4]
mystery(grid, 1) [4, 5, 6, 9]
mystery(grid, 3) [4, 5, 6]
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. Binary Trees, 10 points. One possible solution appears below.
public String toString() {
return toString(overallRoot);
}
private String toString(IntTreeNode root) {
if (root == null) {
return "empty";
} else if (root.left == null && root.right == null) {
return "" + root.data;
} else {
return "(" + root.data + ", " + toString(root.left)
+ ", " + toString(root.right) + ")";
}
}
6. One possible solution appears below.
public Map<Point, Set<Integer>> pointMap(List<Point> data) {
Map<Point, Set<Integer>> map = new HashMap<Point, Set<Integer>>();
for (int i = 0; i < data.size(); i++) {
Point p = data.get(i);
if (!map.containsKey(p)) {
map.put(p, new TreeSet<Integer>());
}
map.get(p).add(i);
}
return map;
}
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 add(IntTree other) {
overallRoot = add(overallRoot, other.overallRoot);
}
private IntTreeNode add(IntTreeNode root1, IntTreeNode root2) {
if (root2 != null) {
if (root1 == null) {
root1 = new IntTreeNode(root2.data, null, null);
} else {
root1 = new IntTreeNode(root1.data + root2.data,
root1.left, root1.right);
}
root1.left = add(root1.left, root2.left);
root1.right = add(root1.right, root2.right);
}
return root1;
}
9. One possible solution appears below.
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode current = front.next.next;
front.next.next = current.next.next;
current.next.next = front;
front = current;
current = current.next.next.next;
while (current.next != null && current.next.next != null &&
current.next.next.next != null &&
current.next.next.next.next != null) {
ListNode temp = current.next.next.next;
current.next.next.next = temp.next.next;
temp.next.next = current.next;
current.next = temp;
current = temp.next.next.next;
}
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011