<![CDATA[
CSE143 Key to Sample Final, Fall 2008 handout #38
1. Binary Tree Traversals, 6 points.
Preorder traversal 4, 5, 2, 9, 3, 7, 6, 0, 1, 8
Inorder traversal 2, 9, 5, 3, 7, 4, 0, 6, 8, 1
Postorder traversal 9, 2, 7, 3, 5, 0, 8, 1, 6, 4
2. Binary Search Tree, 4 points.
+------------+
| Karl |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Chris | | Simon |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Anton | | John | | Zoe |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Zach |
+------------+
3. Binary Trees, 10 points. One possible solution appears below.
public int oddDepthSum() {
return sum(overallRoot, 1);
}
private int sum(IntTreeNode root, int depth) {
if (root == null)
return 0;
else if (depth % 2 == 0)
return sum(root.left, depth + 1) + sum(root.right, depth + 1);
else
return root.data + sum(root.left, depth + 1) +
sum(root.right, depth + 1);
}
4. Comparable class, 20 points. One possible solution appears below.
class TeamData implements Comparable<TeamData> {
private String name;
private int solved;
private int totalTime;
private int problems;
public TeamData(String name, int problems) {
this.name = name;
this.problems = problems;
this.totalTime = 0;
this.solved = 0;
}
public void success(int problem, int time) {
solved++;
totalTime += time;
}
public String toString() {
return name + " solved " + solved + " of " + problems + " in "
+ totalTime + " minutes";
}
public int solved() {
return solved;
}
public int time() {
return totalTime;
}
public double percentCorrect() {
return 100.0 * solved / problems;
}
public int compareTo(TeamData other) {
if (solved != other.solved)
return other.solved - solved;
else
return totalTime - other.totalTime;
}
}
5. Programming with inheritance, 20 points. One possible solution appears
below.
class ExtendedTeamData extends TeamData {
private int[] times;
private int[] failed;
public ExtendedTeamData(String name, int problems) {
super(name, problems);
times = new int[problems];
failed = new int[problems];
}
public void success(int problem, int time) {
times[problem] = time;
super.success(problem, time + failed[problem] * 20);
}
public void fail(int problem) {
failed[problem]++;
}
public String detailString() {
String result = "solved:";
for (int i = 0; i < times.length; i++)
if (times[i] > 0) {
result += " " + i + " (" + times[i];
if (failed[i] > 0)
result += "+" + failed[i] * 20;
result += ")";
}
return result;
}
}
6. Binary Trees, 20 points. 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;
}
7. Linked Lists, 20 points. One possible solution appears below.
public void markMultiples(int n) {
if (n <= 0)
throw new IllegalArgumentException();
if (front != null) {
ListNode current = front;
if (front.data % n == 0)
front = new ListNode(0, front);
while (current.next != null) {
if (current.next.data % n == 0) {
current.next = new ListNode(0, current.next);
current = current.next.next;
} else
current = current.next;
}
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011