<![CDATA[
CSE143 Key to Final, Fall 2010 handout #37
1. Preorder traversal 3, 5, 9, 6, 0, 2, 7, 8, 4, 1
Inorder traversal 3, 0, 6, 2, 9, 5, 4, 8, 7, 1
Postorder traversal 0, 2, 6, 9, 4, 8, 1, 7, 5, 3
2. +------------+
| Ginger |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Gilligan | | Professor |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Lovey | | Skipper |
+------------+ +------------+
\ \
\ \
\ \
+------------+ +------------+
| Maryann | | Thurston |
+------------+ +------------+
3. Two-Dimensional Array Contents of List Returned
------------------------------------------------------------------
[[0, 1], [2, 3]] [1]
[[0, 1, 2], [3, 4, 5], [6, 7, 8]] [2, 3, 5, 6]
[[3, 4], [1, 2, 3], [], [5, 6]] [0, 1, 4]
4. One possible solution appears below.
public boolean equals(Set<Integer> s1, Set<Integer> s2) {
for (int n : s1) {
if (!s2.contains(n))
return false;
}
return s1.size() == s2.size();
}
5. One possible solution appears below.
public int countMultiples(int value) {
if (value == 0)
throw new IllegalArgumentException();
return countMultiples(overallRoot, value);
}
private int countMultiples(IntTreeNode root, int value) {
if (root == null)
return 0;
else {
int sum = countMultiples(root.left, value) +
countMultiples(root.right, value);
if (root.data % value == 0)
return 1 + sum;
else
return sum;
}
}
6. One possible solution appears below.
public Map<Point, Integer> pointCount(List<Point> list) {
Map<Point, Integer> result = new HashMap<Point, Integer>();
for (Point p : list) {
if (!result.containsKey(p))
result.put(p, 1);
else
result.put(p, result.get(p) + 1);
}
return result;
}
7. One possible solution appears below.
public class FoodData implements Comparable<FoodData> {
private String name;
private double fat;
private double carbs;
private double protein;
public FoodData(String name, double fat, double carbs,
double protein) {
if (fat < 0 || carbs < 0 || protein < 0)
throw new IllegalArgumentException();
this.name = name;
this.fat = fat;
this.carbs = carbs;
this.protein = protein;
}
public String getName() {
return name;
}
public double getCalories() {
return 9 * fat + 4 * (carbs + protein);
}
public double percentFat() {
return 100.0 * (9 * fat / getCalories());
}
public String toString() {
return name + ": " + fat + "g fat, " + carbs +
"g carbohydrates, " + protein + "g protein";
}
public int compareTo(FoodData other) {
double difference = percentFat() - other.percentFat();
if (difference < 0)
return -1;
else if (difference > 0)
return 1;
else
return name.compareTo(other.name);
}
}
8. One possible solution appears below.
public void makeFull() {
overallRoot = makeFull(overallRoot);
}
private IntTreeNode makeFull(IntTreeNode root) {
if (root != null) {
root.left = makeFull(root.left);
root.right = makeFull(root.right);
if (root.left == null && root.right != null)
root = root.right;
else if (root.left != null && root.right == null)
root = root.left;
}
return root;
}
9. One possible solution appears below.
public void reorder3() {
if (front != null && front.next != null) {
ListNode temp = front;
front = temp.next;
temp.next = front.next;
front.next = temp;
ListNode current = temp.next;
while (current != null && current.next != null &&
current.next.next != null) {
temp = current.next;
current.next = temp.next;
temp.next = current.next.next;
current.next.next = temp;
current = temp.next;
}
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011