<![CDATA[
CSE143 Key to Sample Final handout #36
1. Binary Tree Traversals, 6 points.
Preorder traversal 3, 5, 9, 6, 0, 2, 7, 8, 4, 1
Inorder traversal 3, 0, 6, 2, 9, 5, 4, 8, 7, 1
Postorder traversal 0, 2, 6, 9, 4, 8, 1, 7, 5, 3
2. Binary Search Tree, 4 points.
+------------+
| Johanna |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Danny | | Nehemiah |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Lacy | | Rachel |
+------------+ +------------+
\ \
\ \
\ \
+------------+ +------------+
| Melinda | | Wes |
+------------+ +------------+
3. Binary Trees, 10 points. One possible solution appears below.
public int numEmpty() {
return numEmpty(root);
}
private int numEmpty(TreeNode root) {
if (root == null)
return 1;
else
return numEmpty(root.left) + numEmpty(root.right);
}
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class UndoStack extends Stack {
private Stack myUndoStack;
public UndoStack() {
myUndoStack = new Stack();
}
public void push(Object value) {
super.push(value);
myUndoStack.push("push");
}
public Object pop() {
Object value = super.pop();
myUndoStack.push(value);
myUndoStack.push("pop");
return value;
}
public boolean canUndo() {
return !myUndoStack.isEmpty();
}
public void undo() {
if (!canUndo())
throw new IllegalStateException();
String action = (String)myUndoStack.pop();
if (action.equals("push"))
super.pop();
else
super.push(myUndoStack.pop());
}
}
5. Comparable class, 20 points. Two possible solutions appear below.
public class USCurrency implements Comparable<USCurrency> {
private int totalCents;
public USCurrency(int dollars, int cents) {
totalCents = dollars * 100 + cents;
}
public int dollars() {
return totalCents / 100;
}
public int cents() {
return totalCents % 100;
}
public String toString() {
int cents = Math.abs(totalCents);
String s = cents / 100 + "." + cents % 100 / 10 + cents % 10;
if (totalCents < 0)
return "-$" + s;
else
return "$" + s;
}
public USCurrency add(USCurrency other) {
return new USCurrency(dollars() + other.dollars(),
cents() + other.cents());
}
public USCurrency subtract(USCurrency other) {
return new USCurrency(dollars() - other.dollars(),
cents() - other.cents());
}
public int compareTo(USCurrency other) {
return totalCents - other.totalCents;
}
}
public class USCurrency implements Comparable<USCurrency> {
private int dollars;
private int cents;
public USCurrency(int dollars, int cents) {
int totalCents = 100 * dollars + cents;
this.dollars = totalCents / 100;
this.cents = totalCents % 100;
}
public int dollars() {
return dollars;
}
public int cents() {
return cents;
}
public String toString() {
String s = Math.abs(dollars) + ".";
if (Math.abs(cents) < 10)
s += "0" + Math.abs(cents);
else
s += Math.abs(cents);
if (dollars < 0 || cents < 0)
return "-$" + s;
else
return "$" + s;
}
public USCurrency add(USCurrency other) {
return new USCurrency(dollars + other.dollars,
cents + other.cents);
}
public USCurrency subtract(USCurrency other) {
return new USCurrency(dollars - other.dollars,
cents - other.cents);
}
public int compareTo(USCurrency other) {
return dollars * 100 + cents - other.dollars * 100
- other.cents;
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void removeLeaves() {
root = removeLeaves(root);
}
private TreeNode removeLeaves(TreeNode root) {
if (root != null)
if (root.left == null && root.right == null)
root = null;
else {
root.left = removeLeaves(root.left);
root.right = removeLeaves(root.right);
}
return root;
}
7. Linked Lists. Below are two possible solutions. The second is shorter
because it is written recursively.
public void switchPairs() {
if (front != null && front.next != null) {
ListNode current = front.next;
front.next = current.next;
current.next = front;
front = current;
current = current.next;
while (current.next != null && current.next.next != null) {
ListNode temp = current.next.next;
current.next.next = temp.next;
temp.next = current.next;
current.next = temp;
current = temp.next;
}
}
}
public void switchPairs() {
front = switchPairs(front);
}
private ListNode switchPairs(ListNode list) {
if (list != null && list.next != null) {
ListNode temp = list.next;
list.next = temp.next;
temp.next = list;
list = temp;
list.next.next = switchPairs(list.next.next);
}
return list;
}
]]>