<![CDATA[
Key to CSE143 Final, Autumn 2006 handout #38
1. Binary Tree Traversals, 6 points.
Preorder traversal 8, 7, 2, 4, 9, 5, 1, 3, 6, 0
Inorder traversal 4, 2, 9, 7, 8, 3, 1, 6, 5, 0
Postorder traversal 4, 9, 2, 7, 3, 6, 1, 0, 5, 8
2. Binary Search Tree, 4 points.
+------------+
| Monday |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Friday | | Tuesday |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Thursday | | Wednesday |
+------------+ +------------+
/
/
/
+------------+
| Saturday |
+------------+
\
\
\
+------------+
| Sunday |
+------------+
3. 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);
}
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class TestableRouter extends Router {
private boolean inExperiment;
private boolean haveResult;
private int success;
private int failure;
private String address;
public TestableRouter(NetworkData d) {
super(d);
}
public void test(String address) {
this.address = address;
inExperiment = true;
success = 0;
failure = 0;
}
public boolean route(Packet p) {
boolean result = super.route(p);
if (inExperiment && p.getSource().equals(address)) {
if (result)
success++;
else
failure++;
if (success + failure == 1000) {
inExperiment = false;
haveResult = true;
}
}
return result;
}
public boolean rateAvailable() {
return haveResult && !inExperiment;
}
public double getRate() {
if (!rateAvailable())
throw new IllegalStateException();
return success / 10.0;
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class Location implements Comparable<Location> {
private String name;
private double longitude;
private double latitude;
public Location(String name, double longitude, double latitude) {
this.name = name;
this.longitude = longitude;
this.latitude = latitude;
}
public int compareTo(Location other) {
double difference = Math.abs(longitude)
- Math.abs(other.longitude);
if (difference == 0)
difference = Math.abs(latitude) - Math.abs(other.latitude);
if (difference < 0)
return -1;
else if (difference == 0)
return 0;
else // difference > 0
return 1;
}
public String getName() {
return name;
}
public double getLongitude() {
return longitude;
}
public double getLatitude() {
return latitude;
}
public String toString() {
String result = name + " " + Math.abs(longitude);
if (longitude < 0)
result += "S";
else
result += "N";
result += " " + Math.abs(latitude);
if (latitude < 0)
result += "E";
else
result += "W";
return result;
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public int countNodes(int left, int right) {
if (left < 0 || right < 0)
throw new IllegalArgumentException();
return countNodes(overallRoot, left, right);
}
private int countNodes(IntTreeNode root, int left, int right) {
if (root == null || left < 0 || right < 0)
return 0;
else if (left == 0 && right == 0)
return 1;
else
return countNodes(root.left, left - 1, right)
+ countNodes(root.right, left, right - 1);
}
7. Linked Lists. One possible solution appears below.
public void interleave(LinkedIntList other) {
if (front == null) {
front = other.front;
other.front = null;
} else if (other.front != null) {
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current2.next != null) {
ListNode temp = current1.next;
current1.next = current2;
current2 = current2.next;
current1.next.next = temp;
current1 = temp;
}
if (current1.next == null)
current1.next = current2;
else {
current2.next = current1.next;
current1.next = current2;
}
other.front = null;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011