<![CDATA[
Key to CSE143 Final, Winter 2007 handout #36
1. Binary Tree Traversals, 6 points.
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. Binary Search Tree, 4 points.
+------------+
| Moon |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Mercury | | Sun |
+------------+ +------------+
/ / \
/ / \
/ / \
+------------+ +------------+ +------------+
| Jupter | | Saturn | | Venus |
+------------+ +------------+ +------------+
\
\
\
+------------+
| Mars |
+------------+
3. Binary Trees, 10 points. One possible solution appears below.
public int evenBranches() {
return evenBranches(overallRoot);
}
private int evenBranches(IntTreeNode root) {
if (root == null)
return 0;
else if (root.left == null && root.right == null)
return 0;
else if (root.data % 2 == 0)
return 1 + evenBranches(root.left) + evenBranches(root.right);
else
return evenBranches(root.left) + evenBranches(root.right);
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class MemoCalculator extends Calculator {
private Map<Integer, Integer> primeMap;
private int memoCount;
public MemoCalculator(int seed) {
super(seed);
primeMap = new HashMap<Integer, Integer>();
}
public int prime(int n) {
if (primeMap.containsKey(n)) {
memoCount++;
return primeMap.get(n);
} else {
int result = super.prime(n);
primeMap.put(n, result);
return result;
}
}
public int getMemoCount() {
return memoCount;
}
public int getComputeCount() {
return primeMap.size();
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class ClockTime implements Comparable<ClockTime> {
private int hours;
private int minutes;
private String amPm;
public ClockTime(int hours, int minutes, String amPm) {
this.hours = hours;
this.minutes = minutes;
this.amPm = amPm;
}
public int compareTo(ClockTime other) {
if (!amPm.equals(other.amPm))
return amPm.compareTo(other.amPm);
else if (hours != other.hours)
return hours % 12 - other.hours % 12;
else
return minutes - other.minutes;
}
public int getHours() {
return hours;
}
public int getMinutes() {
return minutes;
}
public String getAmPm() {
return amPm;
}
public String toString() {
String result = hours + ":";
if (minutes < 10)
result += "0" + minutes;
else
result += minutes;
result += " " + amPm;
return result;
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void limitPathSum(int max) {
overallRoot = limitPathSum(overallRoot, max, 0);
}
private IntTreeNode limitPathSum(IntTreeNode root, int max,
int current) {
if (root != null) {
current += root.data;
if (current > max)
root = null;
else {
root.left = limitPathSum(root.left, max, current);
root.right = limitPathSum(root.right, max, current);
}
}
return root;
}
7. Linked Lists. Two possible solutions appear below.
public void takeSmallerFrom(LinkedIntList other) {
if (front != null && other.front != null) {
if (front.data > other.front.data) {
ListNode temp = front;
front = other.front;
other.front = temp;
}
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current2.next != null) {
if (current1.next.data > current2.next.data) {
ListNode temp = current1.next;
current1.next = current2.next;
current2.next = temp;
temp = current1.next.next;
current1.next.next = current2.next.next;
current2.next.next = temp;
}
current1 = current1.next;
current2 = current2.next;
}
}
}
public void takeSmallerFrom(LinkedIntList other) {
if (front != null && other.front != null) {
boolean inList1 = true;
if (front.data > other.front.data) {
ListNode temp = front;
front = other.front;
other.front = temp;
inList1 = false;
}
ListNode current1 = front;
ListNode current2 = other.front;
while (current1.next != null && current2.next != null) {
if (current1.next.data > current2.next.data) {
ListNode temp = current1.next;
current1.next = current2.next;
current2.next = temp;
inList1 = !inList1;
}
current1 = current1.next;
current2 = current2.next;
}
if (!inList1) {
ListNode temp = current1.next;
current1.next = current2.next;
current2.next = temp;
}
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011