<![CDATA[
CSE143 Key to Final, Spring 2010 handout #36
1. Binary Tree Traversals, 6 points.
Preorder traversal 0, 3, 4, 7, 6, 2, 1, 5, 9, 8
Inorder traversal 7, 4, 6, 3, 2, 1, 0, 5, 8, 9
Postorder traversal 7, 6, 4, 1, 2, 3, 8, 9, 5, 0
2. Binary Search Tree, 4 points.
+------------+
| Jeff |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Britta | | Shirley |
+------------+ +------------+
/ / \
/ / \
/ / \
+------------+ +------------+ +------------+
| Abed | | Pierce | | Troy |
+------------+ +------------+ +------------+
\
\
\
+------------+
| Annie |
+------------+
3. Collections Mystery, 10 points.
Two-Dimensional Array Contents of Set Returned
------------------------------------------------------------------
[[1, 2], [3, 4]] [1, 2, 13, 14]
[[7], [], [8, 8, 9, 10]] [7, 28, 29, 30]
[[3, 14], [5, 13, 4], [4, 3, 1]] [3, 14, 15, 21, 23, 24]
4. Collections Programming, 5 points. One possible solution appears below.
public void retainAll(Set<Integer> s1, Set<Integer> s2) {
Iterator<Integer> i = s1.iterator();
while (i.hasNext()) {
if (!s2.contains(i.next()))
i.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. Collections Programming, 10 points. 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. Comparable class, 20 points. One possible solution appears below.
public class BookData implements Comparable<BookData> {
private String title;
private String author;
private int reviews;
private double total;
public BookData(String title, String author) {
this.title = title;
this.author = author;
this.reviews = 0;
this.total = 0.0;
}
public void review(double rating) {
reviews++;
total += rating;
}
public String getTitle() {
return title;
}
public double getRating() {
if (reviews == 0)
return 0.0;
else
return total / reviews;
}
public String toString() {
double rating = (int) (10.0 * getRating()) / 10.0;
String result = title + ", by " + author + ", " + rating + " (";
if (reviews == 1)
result += "1 review)";
else
result += reviews + " reviews)";
return result;
}
public int compareTo(BookData other) {
double delta = getRating() - other.getRating();
if (delta < 0)
return 1;
else if (delta > 0)
return -1;
else // delta == 0
return other.reviews - reviews;
}
}
8. Binary Trees, 20 points. One possible solution appears below.
public void removeLeftLeaves() {
removeLeftLeaves(overallRoot, false);
}
private IntTreeNode removeLeftLeaves(IntTreeNode root, boolean left) {
if (root != null) {
root.left = removeLeftLeaves(root.left, true);
removeLeftLeaves(root.right, false);
if (left && root.left == null && root.right == null)
root = null;
}
return root;
}
9. Linked Lists, 20 points. Two possible solutions appear below.
public void compressDuplicates() {
if (front != null) {
int count = 1;
while (front.next != null && front.data == front.next.data) {
count++;
front = front.next;
}
front = new ListNode(count, front);
ListNode current = front.next;
while (current.next != null) {
count = 1;
while (current.next.next != null &&
current.next.data == current.next.next.data) {
count++;
current.next = current.next.next;
}
current.next = new ListNode(count, current.next);
current = current.next.next;
}
}
}
public void compressDuplicates() {
front = compressDuplicates(front);
}
private ListNode compressDuplicates(ListNode node) {
if (node != null) {
int count = 1;
while (node.next != null && node.data == node.next.data) {
count++;
node = node.next;
}
node = new ListNode(count, node);
node.next.next = compressDuplicates(node.next.next);
}
return node;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011