<![CDATA[
CSE143X Key to Final, Fall 2012 handout #39
1. 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. One possible solution appears below.
public void printTwos(int n) {
if (n < 1)
throw new IllegalArgumentException();
else if (n % 4 == 0) {
System.out.print("2 * ");
printTwos(n / 4);
System.out.print(" * 2");
} else if (n % 2 == 0) {
System.out.print("2 * ");
printTwos(n / 2);
} else {
System.out.print(n);
}
}
3. Statement Output
------------------------------------------------------------
var1.method2(); Pig 2
var2.method2(); Dog 2
var3.method2(); Dog 2
var4.method2(); compiler error
var5.method2(); Horse 2
var6.method2(); Pig 2
var1.method3(); Cat 3/Pig 2
var2.method3(); compiler error
var3.method3(); compiler error
var4.method3(); compiler error
var5.method3(); Cat 3/Horse 2
var6.method3(); Cat 3/Pig 2
((Pig)var5).method1(); runtime error
((Cat)var3).method3(); Cat 3/Dog 2
((Cat)var4).method1(); compiler error
((Pig)var1).method1(); Horse 1/Dog 2
((Horse)var4).method1(); Horse 1/Dog 2
((Cat)var2).method3(); runtime error
((Horse)var3).method1(); runtime error
((Dog)var4).method2(); Horse 2
4. One possible solution appears below.
public static boolean isSorted(Stack<Integer> s) {
if (s.size() <= 1)
return true;
else {
Queue<Integer> q = new LinkedList<Integer>();
int prev = s.pop();
q.add(prev);
boolean ok = true;
while (!s.isEmpty()) {
int next = s.pop();
if (prev < next)
ok = false;
q.add(next);
prev = next;
}
while (!q.isEmpty())
s.push(q.remove());
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
return ok;
}
}
5. One possible solution appears below.
public void printLeaves() {
if (overallRoot == null)
System.out.println("no leaves");
else {
System.out.print("leaves:");
printLeaves(overallRoot);
System.out.println();
}
}
private void printLeaves(IntTreeNode root) {
if (root != null)
if (root.left == null && root.right == null)
System.out.print(" " + root.data);
else {
printLeaves(root.right);
printLeaves(root.left);
}
}
6. One possible solution appears below.
public static Map<String, Set<String>> convert(Set<String> numbers) {
Map<String, Set<String>> result = new TreeMap<String, Set<String>>();
for (String s : numbers) {
String exchange = s.substring(0, 3);
String digits = s.substring(4);
if (!result.containsKey(exchange)) {
result.put(exchange, new TreeSet<String>());
}
result.get(exchange).add(digits);
}
return result;
}
7. 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() {
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);
}
}
8. One possible solution appears below.
public void makeFull() {
overallRoot = makeFull(overallRoot);
}
private IntTreeNode makeFull(IntTreeNode root) {
if (root != null) {
root.left = makeFull(root.left);
root.right = makeFull(root.right);
if (root.left == null && root.right != null)
root = root.right;
else if (root.left != null && root.right == null)
root = root.left;
}
return root;
}
9. One possible solution appears below.
public void reverse3() {
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;
}
}
}
]]>