<![CDATA[
CSE143 Key to Final, Spring 2013 handout #37
1. 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. +------------+
| Karl |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Chris | | Simon |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Anton | | John | | Zoe |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Zach |
+------------+
3. Method Call Output Produced
------------------------------------------------
mystery(grid, 0, 2, 2); 10 11
mystery(grid, 2, 3, 2); 12 9 12
mystery(grid, 1, 4, 1); 4 8 2 3
4. One possible solution appears below.
public static void retainEvenLength(Set<String> set) {
Iterator<String> itr = set.iterator();
while (itr.hasNext()) {
String s = itr.next();
if (s.length() % 2 != 0) {
itr.remove();
}
}
}
5. Binary Trees, 10 points. One possible solution appears below.
public boolean hasPathSum(int sum) {
return hasPathSum(overallRoot, sum);
}
private boolean hasPathSum(IntTreeNode root, int sum) {
if (root == null)
return false;
if (root.data == sum)
return true;
int sum2 = sum - root.data;
return hasPathSum(root.left, sum2) || hasPathSum(root.right, sum2);
}
6. One possible solution appears below.
public static int recordDate(Map<String, List<String>> dates,
String name1, String name2) {
if (!dates.containsKey(name1)) {
dates.put(name1, new LinkedList<String>());
}
if (!dates.containsKey(name2)) {
dates.put(name2, new LinkedList<String>());
}
dates.get(name1).add(0, name2);
dates.get(name2).add(0, name1);
int n = 0;
for (String s : dates.get(name1)) {
if (s.equals(name2)) {
n++;
}
}
return n;
}
7. One possible solution appears below.
public class ClockTime implements Comparable<ClockTime> {
private int hours;
private int minutes;
private String amPm;
public ClockTime(int hours, int minutes, String amPm) {
this.hours = hours;
this.minutes = minutes;
this.amPm = amPm;
}
public int compareTo(ClockTime other) {
if (!amPm.equals(other.amPm))
return amPm.compareTo(other.amPm);
else if (hours != other.hours)
return hours % 12 - other.hours % 12;
else
return minutes - other.minutes;
}
public int getHours() {
return hours;
}
public int getMinutes() {
return minutes;
}
public String getAmPm() {
return amPm;
}
public String toString() {
String result = hours + ":";
if (minutes < 10)
result += "0" + minutes;
else
result += minutes;
result += " " + amPm;
return result;
}
}
8. One possible solution appears below.
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
root = new IntTreeNode(-level, root, root.right);
root.left.right = null;
} else if (root.left != null && root.right == null) {
root = new IntTreeNode(-level, root.left, root);
root.right.left = null;
}
root.left = makeFull(root.left, level + 1);
root.right = makeFull(root.right, level + 1);
}
return root;
}
9. Two possible solutions appear below. The second is shorter because it uses
recursion in an x=change(x) manner.
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;
}
}
}
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