<![CDATA[
CSE143 Key to Sample Final handout #32
1. Binary Tree Traversals, 6 points.
Preorder traversal 3, 7, 2, 6, 1, 9, 4, 0, 5, 8
Inorder traversal 2, 7, 1, 6, 9, 3, 4, 5, 0, 8
Postorder traversal 2, 1, 9, 6, 7, 5, 8, 0, 4, 3
2. Binary Search Tree, 4 points.
+------------+
| Dancer |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Comet | | Prancer |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Blitzen | | Cupid | | Vixen |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Rudolph |
+------------+
3. Binary Trees, 10 points. One possible solution appears below.
public void doublePositives() {
doublePositives(root);
}
private void doublePositives(TreeNode root) {
if (root != null) {
if (root.data > 0)
root.data *= 2;
doublePositives(root.left);
doublePositives(root.right);
}
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class FilteredAccount extends Account {
private int zeros;
private int transactions;
public FilteredAccount(Client c) {
super(c);
zeros = 0;
transactions = 0;
}
public boolean process(Transaction t) {
transactions++;
if (t.value() == 0) {
zeros++;
return true;
} else
return super.process(t);
}
public double percentFiltered() {
if (transactions == 0)
return 0.0;
else
return zeros * 100.0/transactions;
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class Point implements Comparable {
private double x;
private double y;
private static final Point ORIGIN = new Point();
public Point() {
this(0.0, 0.0);
}
public Point(double x, double y) {
setLocation(x, y);
}
public double getX() {
return x;
}
public double getY() {
return y;
}
public String toString() {
return "(" + x + ", " + y + ")";
}
public void setLocation(double x, double y) {
this.x = x;
this.y = y;
}
public double distanceFrom(Point other) {
double xDiff = x - other.x;
double yDiff = y - other.y;
return Math.sqrt(xDiff * xDiff + yDiff * yDiff);
}
public int compareTo(Object o) {
Point other = (Point)o;
double d = distanceFrom(ORIGIN) - other.distanceFrom(ORIGIN);
if (d < 0.0)
return -1;
else if (d == 0.0)
return 0;
else
return 1;
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void grow(int n) {
root = growHelper(n);
}
private TreeNode growHelper(int n) {
if (n < 1)
return null;
else if (n == 1)
return new TreeNode(1);
else
return new TreeNode(n, growHelper(n/2 + n % 2), growHelper(n/2));
}
7. Linked Lists, 20 points. One possible solution appears below.
public void removeRange(int low, int high) {
if (low < 0 || high < 0)
throw new IllegalArgumentException();
if (low == 0)
while (high >= 0) {
front = front.next;
high--;
}
else {
ListNode current = front;
int count = 1;
while (count < low) {
current = current.next;
count++;
}
ListNode current2 = current.next;
while (count < high) {
current2 = current2.next;
count++;
}
current.next = current2.next;
}
}
]]>