<![CDATA[
CSE143 Key to Final, Spring 2011 handout #37
1. Preorder traversal 3, 2, 4, 5, 7, 0, 1, 6, 9, 8
Inorder traversal 4, 2, 7, 5, 0, 3, 1, 9, 6, 8
Postorder traversal 4, 7, 0, 5, 2, 9, 8, 6, 1, 3
2. +------------+
| Lee |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Britt | | Vin |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Bernardo | | Chris |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Chico | | Harry |
+------------+ +------------+
3. list1: [b, l, u, e]
list2: [s, p, o, t]
map returned: {b=s, e=t, l=p, o=u, p=l, s=b, t=e, u=o}
list1: [k, e, e, p]
list2: [s, a, f, e]
map returned: {a=e, e=p, f=e, k=s, p=e, s=k}
list1: [s, o, b, e, r]
list2: [b, o, o, k, s]
map returned: {b=o, e=k, k=e, o=b, r=s, s=r}
4. One possible solution appears below.
public void removeEvenLength(Set<String> set) {
Iterator<String> itr = set.iterator();
while (itr.hasNext()) {
String s = itr.next();
if (s.length() % 2 == 0) {
itr.remove();
}
}
}
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 Map<Integer, Set<String>> split(Set<String> words) {
Map<Integer, Set<String>> buckets =
new TreeMap<Integer, Set<String>>();
for (String word : words) {
int n = word.length();
if (!buckets.containsKey(n)) {
buckets.put(n, new TreeSet<String>());
}
buckets.get(n).add(word);
}
return buckets;
}
7. One possible solution appears below.
public class TeamData implements Comparable<TeamData> {
private String name;
private int solved;
private int totalTime;
private int problems;
public TeamData(String name, int problems) {
this.name = name;
this.problems = problems;
this.totalTime = 0;
this.solved = 0;
}
public void success(int problem, int time) {
solved++;
totalTime += time;
}
public String toString() {
return name + " solved " + solved + " of " + problems + " in "
+ totalTime + " minutes";
}
public int solved() {
return solved;
}
public int time() {
return totalTime;
}
public double percentCorrect() {
return 100.0 * solved / problems;
}
public int compareTo(TeamData other) {
if (solved != other.solved)
return other.solved - solved;
else
return totalTime - other.totalTime;
}
}
8. One possible solution appears below.
public void stretch() {
overallRoot = stretch(overallRoot);
}
private IntTreeNode stretch(IntTreeNode root) {
if (root != null) {
root.left = stretch(root.left);
root.right = stretch(root.right);
if (root.left != null && root.right == null)
root = new IntTreeNode(1, root, null);
else if (root.left == null && root.right != null)
root = new IntTreeNode(1, null, root);
}
return root;
}
9. One possible solution appears below.
public void shift() {
if (front != null && front.next != null) {
ListNode otherFront = front;
ListNode otherBack = front;
front = front.next;
ListNode current = front;
while (current.next != null && current.next.next != null) {
otherBack.next = current.next;
otherBack = current.next;
current.next = current.next.next;
current = current.next;
}
if (current.next != null) {
otherBack.next = current.next;
otherBack = current.next;
}
current.next = otherFront;
otherBack.next = null;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011