<![CDATA[
CSE143 Key to Final, Spring 2007 handout #39
1. Binary Tree Traversals, 6 points.
Preorder traversal 0, 3, 1, 2, 5, 8, 9, 4, 7, 6
Inorder traversal 1, 3, 5, 2, 8, 0, 9, 7, 4, 6
Postorder traversal 1, 5, 8, 2, 3, 7, 6, 4, 9, 0
2. Binary Search Tree, 4 points.
+------------+
| Ephraim |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Ben | | Frank |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Adam | | Dan | | Gideon |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Caleb |
+------------+
3. 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) + ")";
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class DiscountBill extends GroceryBill {
private boolean discount;
private int count;
private double total;
public DiscountBill(ClerkInfo info, boolean discount) {
super(info);
this.discount = discount;
}
public void add(Item i) {
super.add(i);
if (discount) {
double amount = i.discount();
if (amount > 0.0) {
count++;
total += amount;
}
}
}
public int getDiscountCount() {
return count;
}
public double getDiscountAmount() {
return total;
}
public double getDiscountPercent() {
return total / super.getTotal() * 100;
}
public double getTotal() {
return super.getTotal() - total;
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class Rectangle implements Comparable<Rectangle> {
private int x, y;
private int width, height;
public Rectangle(int x, int y, int width, int height) {
if (width < 0 || height < 0)
throw new IllegalArgumentException();
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
public int getArea() {
return width * height;
}
private double distance() {
return Math.sqrt(x * x + y * y);
}
public int compareTo(Rectangle other) {
int diff1 = getArea() - other.getArea();
if (diff1 != 0)
return diff1;
else {
double diff2 = distance() - other.distance();
if (diff2 < 0)
return -1;
else if (diff2 == 0)
return 0;
else // diff2 > 0
return 1;
}
}
public String toString() {
return "rectangle at (" + x + ", " + y + ") of size (" + width
+ ", " + height + ")";
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void construct(int n) {
if (n < 0)
throw new IllegalArgumentException();
overallRoot = construct(0, n - 1);
}
private IntTreeNode construct(int low, int high) {
if (low > high)
return null;
else {
int mid = (low + high) / 2;
return new IntTreeNode(mid, construct(low, mid - 1),
construct(mid + 1, high));
}
}
7. Linked Lists. One possible solution appears below.
public void shift() {
if (front != null && front.next != null) {
ListNode otherFront = front.next;
front.next = front.next.next;
ListNode current1 = front;
ListNode current2 = otherFront;
while (current1.next != null) {
current1 = current1.next;
if (current1.next != null) {
current2.next = current1.next;
current1.next = current1.next.next;
current2 = current2.next;
}
}
current2.next = null;
current1.next = otherFront;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011