<![CDATA[
CSE143 Key to Final, Winter 2014 handout #37
1. Preorder traversal 4, 2, 7, 9, 3, 6, 1, 8, 5, 0
Inorder traversal 7, 9, 2, 3, 6, 4, 8, 1, 0, 5
Postorder traversal 9, 7, 6, 3, 2, 8, 0, 5, 1, 4
2. +------------+
| Moon |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Mercury | | Sun |
+------------+ +------------+
/ / \
/ / \
/ / \
+------------+ +------------+ +------------+
| Jupter | | Saturn | | Venus |
+------------+ +------------+ +------------+
\
\
\
+------------+
| Mars |
+------------+
3. Collections Mystery, 10 points.
Two-Dimensional Array Contents of Set Returned
------------------------------------------------------------------
[[1, 2], [3, 4]] [1, 2, 13, 14]
[[7], [], [8, 8, 9, 10]] [7, 28, 29, 30]
[[3, 14], [5, 13, 4], [4, 3, 1]] [3, 14, 15, 21, 23, 24]
4. One possible solution appears below.
public void retainEqual(Set<Point> data) {
Iterator<Point> itr = data.iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (p.getX() != p.getY()) {
itr.remove();
}
}
}
5. Binary Trees, 10 points. One possible solution appears below.
public void printLeaves() {
if (overallRoot == null)
System.out.println("no leaves");
else {
System.out.print("leaves:");
printLeaves(overallRoot);
System.out.println();
}
}
private void printLeaves(IntTreeNode root) {
if (root != null)
if (root.left == null && root.right == null)
System.out.print(" " + root.data);
else {
printLeaves(root.right);
printLeaves(root.left);
}
}
6. One possible solution appears below.
public Map<String, Set<String>> convert(Set<String> numbers) {
Map<String, Set<String>> result = new TreeMap<String, Set<String>>();
for (String s : numbers) {
String exchange = s.substring(0, 3);
String digits = s.substring(4);
if (!result.containsKey(exchange)) {
result.put(exchange, new TreeSet<String>());
}
result.get(exchange).add(digits);
}
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 limitPathSum(int max) {
overallRoot = limitPathSum(overallRoot, max);
}
private IntTreeNode limitPathSum(IntTreeNode root, int max) {
if (root != null) {
if (root.data > max) {
root = null;
} else {
root.left = limitPathSum(root.left, max - root.data);
root.right = limitPathSum(root.right, max - root.data);
}
}
return root;
}
9. One possible solution appears below.
public void mergeFrom(LinkedIntList other) {
if (other.front != null) {
if (front == null)
front = other.front;
else {
ListNode current1 = front;
ListNode current2 = other.front;
if (front.data <= other.front.data) {
current1 = current1.next;
} else {
front = other.front;
current2 = current2.next;
}
ListNode current3 = front;
while (current1 != null && current2 != null) {
if (current1.data <= current2.data) {
current3.next = current1;
current1 = current1.next;
} else {
current3.next = current2;
current2 = current2.next;
}
current3 = current3.next;
}
if (current1 != null) {
current3.next = current1;
} else {
current3.next = current2;
}
}
other.front = null;
}
}
10. One possible solution appears below.
public IntTree(int n) {
if (n < 0) {
throw new IllegalArgumentException();
}
overallRoot = makeTree(1, n);
}
private IntTreeNode makeTree(int low, int high) {
if (low > high) {
return null;
} else {
int mid = (low + high - 1) / 2;
return new IntTreeNode(high, makeTree(low, mid),
makeTree(mid + 1, high - 1));
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011