<![CDATA[
CSE143X Key to Sample Final, Fall 2012 handout #38
1. Preorder traversal 2, 7, 9, 0, 5, 3, 6, 1, 4, 8
Inorder traversal 9, 7, 5, 0, 3, 2, 6, 4, 1, 8
Postorder traversal 9, 5, 3, 0, 7, 4, 8, 1, 6, 2
2. One possible solution appears below.
public void printDashed(int n) {
if (n < 0) {
System.out.print("-");
printDashed(-n);
} else if (n < 10) {
System.out.print(n);
} else {
printDashed(n / 10);
System.out.print("-" + n % 10);
}
}
3. Statement Output
------------------------------------------------------------
var1.method1(); Peak 1/Cliff 3/Peak 3
var2.method1(); Peak 1/Gorge 3
var3.method1(); Peak 1/Hill 3
var4.method1(); Peak 1/Gorge 3
var5.method1(); Peak 1/Peak 3
var6.method1(); compiler error
var1.method2(); compiler error
var2.method2(); Gorge 2
var3.method2(); compiler error
var1.method3(); Cliff 3/Peak 3
var2.method3(); Gorge 3
var3.method3(); Hill 3
((Gorge)var6).method1(); runtime error
((Cliff)var3).method2(); compiler error
((Gorge)var4).method2(); Gorge 2
((Gorge)var3).method2(); runtime error
((Hill)var3).method2(); Hill 2
((Gorge)var1).method1(); runtime error
((Cliff)var4).method3(); Gorge 3
((Peak)var6).method3(); Cliff 3/Peak 3
4. One possible solution appears below.
public int removeMin(Stack<Integer> s) {
Queue<Integer> q = new LinkedList<Integer>();
int min = s.pop();
q.add(min);
while (!s.isEmpty()) {
int next = s.pop();
if (next < min)
min = next;
q.add(next);
}
while (!q.isEmpty()) {
int next = q.remove();
if (next != min)
s.push(next);
}
while (!s.isEmpty())
q.add(s.pop());
while (!q.isEmpty())
s.push(q.remove());
return min;
}
5. One possible solution appears below.
public String toString() {
return toString(overallRoot);
}
private String toString(IntTreeNode root) {
if (root == null)
return "empty";
else if (root.left == null && root.right == null)
return "" + root.data;
else
return "(" + root.data + ", " + toString(root.left)
+ ", " + toString(root.right) + ")";
}
6. One possible solution appears below.
public static Map<Point, Integer> sumStrings(Map<String, Point> data) {
Map<Point, Integer> result = new HashMap<Point, Integer>();
for (String s : data.keySet()) {
Point p = data.get(s);
if (!result.containsKey(p)) {
result.put(p, s.length());
} else {
result.put(p, result.get(p) + s.length());
}
}
return result;
}
7. Two possible solutions appear below.
public class TimeSpan implements Comparable<TimeSpan> {
private int totalSeconds;
public TimeSpan(int hours, int minutes, int seconds) {
if (hours < 0 || minutes < 0 || seconds < 0) {
throw new IllegalArgumentException();
}
totalSeconds = seconds + 60 * (minutes + 60 * hours);
}
public int hours() {
return totalSeconds / 3600;
}
public int minutes() {
return totalSeconds % 3600 / 60;
}
public int seconds() {
return totalSeconds % 60;
}
public int totalSeconds() {
return totalSeconds;
}
public String toString() {
return hours() + ":" + minutes() / 10 + minutes() % 10 + ":" +
seconds() / 10 + seconds() % 10;
}
public TimeSpan add(TimeSpan other) {
TimeSpan result = new TimeSpan(0, 0, 0);
result.totalSeconds = totalSeconds + other.totalSeconds;
return result;
}
public int compareTo(TimeSpan other) {
return this.totalSeconds - other.totalSeconds;
}
}
public class TimeSpan implements Comparable<TimeSpan> {
private int hours, minutes, seconds;
public TimeSpan(int hours, int minutes, int seconds) {
if (hours < 0 || minutes < 0 || seconds < 0) {
throw new IllegalArgumentException();
}
int total = seconds + 60 * (minutes + 60 * hours);
this.seconds = total % 60;
this.minutes = total / 60 % 60;
this.hours = total / 3600;
}
public int hours() {
return hours;
}
public int minutes() {
return minutes;
}
public int seconds() {
return seconds;
}
public int totalSeconds() {
return seconds + 60 * (minutes + 60 * hours);
}
public String toString() {
return hours + ":" + minutes / 10 + minutes % 10 + ":" +
seconds / 10 + seconds % 10;
}
public TimeSpan add(TimeSpan other) {
return new TimeSpan(hours + other.hours, minutes + other.minutes,
seconds + other.seconds);
}
public int compareTo(TimeSpan other) {
if (hours != other.hours)
return hours - other.hours;
else if (minutes != other.minutes)
return minutes - other.minutes;
else
return seconds - other.seconds;
}
}
8. One possible solution appears below.
public void add(IntTree other) {
overallRoot = add(overallRoot, other.overallRoot);
}
private IntTreeNode add(IntTreeNode root1, IntTreeNode root2) {
if (root2 != null) {
if (root1 == null)
root1 = new IntTreeNode(0);
root1.data += root2.data;
root1.left = add(root1.left, root2.left);
root1.right = add(root1.right, root2.right);
}
return root1;
}
9. One possible solution appears below.
public void rearrange() {
if (front != null && front.next != null) {
ListNode current = front.next;
while (current != null && current.next != null) {
ListNode temp = current.next;
current.next = current.next.next;
temp.next = front;
front = temp;
current = current.next;
}
}
}
]]>