<![CDATA[
CSE143 Key to Sample Final, Fall 2009 handout #15
1. Binary Tree Traversals, 6 points.
Preorder traversal 0, 3, 7, 4, 6, 2, 9, 1, 5, 8
Inorder traversal 4, 7, 6, 3, 0, 1, 9, 2, 8, 5
Postorder traversal 4, 6, 7, 3, 1, 9, 8, 5, 2, 0
2. Binary Search Tree, 4 points.
+------------+
| Kenny |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Cartman | | Stan |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Kyle | | Tweek |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Timmy | | Wendy |
+------------+ +------------+
3. Binary Trees, 10 points. One possible solution appears below.
public int countMultiples(int value) {
if (value == 0)
throw new IllegalArgumentException();
return countMultiples(overallRoot, value);
}
private int countMultiples(IntTreeNode root, int value) {
if (root == null)
return 0;
else {
int sum = countMultiples(root.left, value) +
countMultiples(root.right, value);
if (root.data % value == 0)
return 1 + sum;
else
return sum;
}
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class HistoryList extends ArrayIntList {
private List<String> history;
public HistoryList() {
this(DEFAULT_CAPACITY);
}
public HistoryList(int capacity) {
super(capacity);
history = new ArrayList<String>();
history.add("initial list = []");
}
public void add(int value) {
super.add(value);
history.add("add(" + value + "), list = " + this);
}
public void add(int index, int value) {
super.add(index, value);
history.add("add(" + index + ", " + value + "), list = "
+ this);
}
public void remove(int index) {
super.remove(index);
history.add("remove(" + index + "), list = " + this);
}
public int historySize() {
return history.size();
}
public String history(int index) {
return history.get(index);
}
}
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 int matches(IntTree other) {
return matches(overallRoot, other.overallRoot);
}
private int matches(IntTreeNode root1, IntTreeNode root2) {
if (root1 == null || root2 == null)
return 0;
else {
int sum = matches(root1.left, root2.left) +
matches(root1.right, root2.right);
if (root1.data == root2.data)
return 1 + sum;
else
return sum;
}
}
7. Linked Lists. Two possible solutions appear below. The second is shorter
because it uses recursion.
public void removeFrom(LinkedIntList other) {
if (front != null && other.front != null) {
ListNode current2 = other.front;
while (current2 != null && front != null &&
current2.data <= front.data) {
if (current2.data < front.data)
current2 = current2.next;
else // current2.data == front.data
front = front.next;
}
if (front != null) {
ListNode current1 = front;
while (current1.next != null && current2 != null)
if (current1.next.data < current2.data)
current1 = current1.next;
else if (current1.next.data == current2.data)
current1.next = current1.next.next;
else // current1.next.data > current2.data
current2 = current2.next;
}
}
}
public void removeFrom(LinkedIntList other) {
front = removeHelper(front, other.front);
}
private ListNode removeHelper(ListNode front1, ListNode front2) {
if (front1 == null || front2 == null)
return front1;
else if (front1.data < front2.data)
front1.next = removeHelper(front1.next, front2);
else if (front1.data == front2.data)
front1 = removeHelper(front1.next, front2);
else // front1.data > front2.data
front1 = removeHelper(front1, front2.next);
return front1;
}
]]>