<![CDATA[
CSE143 Key to Sample Final handout #34
1. Binary Tree Traversals, 6 points.
Preorder traversal 7, 2, 3, 8, 4, 1, 9, 6, 0, 5
Inorder traversal 3, 8, 2, 4, 1, 7, 6, 9, 5, 0
Postorder traversal 8, 3, 1, 4, 2, 6, 5, 0, 9, 7
2. Binary Search Tree, 4 points.
+------------+
| Grumpy |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Doc | | Happy |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Bashful | | Dopey | | Sneezy |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Sleepy |
+------------+
3. Binary Trees, 10 points. One possible solution appears below.
public boolean isFull() {
return (root == null) || isFull(root);
}
private boolean isFull(TreeNode root) {
if (root.left == null && root.right == null)
return true;
else
return root.left != null && root.right != null
&& isFull(root.left) && isFull(root.right);
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class SafeTransactionList extends TransactionList {
private boolean canModify;
public SafeTransactionList(AccountInfo info) {
super(info);
canModify = true;
}
public boolean getModifiable() {
return canModify;
}
public void setModifiable(boolean value) {
canModify = value;
}
public void add(Transaction t) {
checkModify();
super.add(t);
}
public void set(int index, Transaction t) {
checkModify();
super.set(index, t);
}
public Transaction remove(int index) {
checkModify();
return super.remove(index);
}
private void checkModify() {
if (!canModify)
throw new IllegalStateException();
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class Complex implements Comparable<Complex> {
private double x, y;
public Complex(double real, double imaginary) {
x = real;
y = imaginary;
}
public int compareTo(Complex other) {
double difference = abs() - other.abs();
if (difference < 0)
return -1;
else if (difference == 0)
return 0;
else // difference > 0
return 1;
}
public double getReal() {
return x;
}
public double getImaginary() {
return y;
}
public double abs() {
return Math.sqrt(x * x + y * y);
}
public String toString() {
if (y == 0)
return "" + x;
else if (x == 0)
return y + "i";
else if (y < 0)
return x + " - " + -y + "i";
else
return x + " + " + y + "i";
}
public Complex add(Complex other) {
return new Complex(x + other.x, y + other.y);
}
public Complex subtract(Complex other) {
return new Complex(x - other.x, y - other.y);
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void construct(int[] data) {
root = construct(data, 0, data.length - 1);
}
private TreeNode construct(int[] data, int start, int stop) {
if (start > stop)
return null;
else {
int mid = (start + stop + 1) / 2;
return new TreeNode(data[mid], construct(data, start, mid - 1),
construct(data, mid + 1, stop));
}
}
7. Linked Lists. One possible solution appears below.
public LinkedIntList removeEvens() {
LinkedIntList result = new LinkedIntList();
if (front != null) {
result.front = front;
front = front.next;
ListNode current = front;
ListNode resultLast = result.front;
while (current != null && current.next != null) {
resultLast.next = current.next;
resultLast = current.next;
current.next = current.next.next;
current = current.next;
}
resultLast.next = null;
}
return result;
}
]]>