<![CDATA[
CSE143 Key to Sample Final, Fall 2008 handout #38
1. Binary Tree Traversals, 6 points.
Preorder traversal 2, 6, 0, 1, 3, 5, 7, 9, 8, 4
Inorder traversal 0, 6, 3, 1, 5, 2, 7, 8, 9, 4
Postorder traversal 0, 3, 5, 1, 6, 8, 4, 9, 7, 2
2. Binary Search Tree, 4 points.
+------------+
| Kirk |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Chekov | | Spock |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Scotty | | Uhuru |
+------------+ +------------+
/ /
/ /
/ /
+------------+ +------------+
| McCoy | | Sulu |
+------------+ +------------+
3. Binary Trees, 10 points. One possible solution appears below.
public int purebredOdds() {
return purebredOdds(overallRoot);
}
private int purebredOdds(IntTreeNode root) {
if (root == null || root.data % 2 == 0)
return 0;
else
return 1 + purebredOdds(root.left) + purebredOdds(root.right);
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class AnalyzingDocumentList extends DocumentList {
private Map<Integer, Integer> counts;
private int stateCount;
public AnalyzingDocumentList(int capacity) {
super(capacity);
counts = new HashMap<Integer, Integer>();
counts.put(0, 1);
stateCount = 1;
}
public void add(Document d) {
super.add(d);
stateUpdate();
}
public void add(int index, Document d) {
super.add(index, d);
stateUpdate();
}
public void remove(int index) {
super.remove(index);
stateUpdate();
}
private void stateUpdate() {
stateCount++;
int size = size();
if (!counts.containsKey(size))
counts.put(size, 1);
else
counts.put(size, counts.get(size) + 1);
}
public int totalStates() {
return stateCount;
}
public int sizeCount(int size) {
if (counts.containsKey(size))
return counts.get(size);
else
return 0;
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class FoodData implements Comparable<FoodData> {
private String name;
private double fat;
private double carbs;
private double protein;
public FoodData(String name, double fat, double carbs, double protein) {
if (fat < 0 || carbs < 0 || protein < 0)
throw new IllegalArgumentException();
this.name = name;
this.fat = fat;
this.carbs = carbs;
this.protein = protein;
}
public String getName() {
return name;
}
public double getCalories() {
return 9 * fat + 4 * (carbs + protein);
}
public double percentFat() {
if (getCalories() == 0)
return 0.0;
else
return 100.0 * (9 * fat / getCalories());
}
public String toString() {
return name + ": " + fat + "g fat, " + carbs +
"g carbohydrates, " + protein + "g protein";
}
public int compareTo(FoodData other) {
double difference = percentFat() - other.percentFat();
if (difference < 0)
return -1;
else if (difference > 0)
return 1;
else
return name.compareTo(other.name);
}
}
6. Binary Trees, 20 points. One possible solution appears below.
public void mirror() {
mirror(overallRoot);
}
private void mirror(IntTreeNode root) {
if (root != null) {
IntTreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirror(root.left);
mirror(root.right);
}
}
7. Linked Lists, 20 points. Two possible solutions appear below. The second
is much shorter because it uses recursion.
public void rotate3() {
if (front != null && front.next != null &&
front.next.next != null) {
ListNode temp = front;
front = front.next.next;
ListNode temp2 = front.next;
front.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
while (temp.next != null && temp.next.next != null &&
temp.next.next.next != null) {
temp2 = temp.next;
temp.next = temp.next.next.next;
temp = temp2;
temp2 = temp.next.next.next;
temp.next.next.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
}
}
}
public void reverse3() {
front = reverse3(front);
}
private ListNode reverse3(ListNode lst) {
if (lst != null && lst.next != null && lst.next.next != null) {
ListNode temp = lst;
lst = lst.next.next;
ListNode temp2 = lst.next;
lst.next = temp.next;
temp.next.next = temp;
temp.next = temp2;
temp.next = reverse3(temp.next);
}
return lst;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011