<![CDATA[
CSE143 Key to Final, Fall 2014 handout #29
1. Preorder traversal 0, 3, 1, 2, 5, 8, 9, 4, 7, 6
Inorder traversal 1, 3, 5, 2, 8, 0, 9, 7, 4, 6
Postorder traversal 1, 5, 8, 2, 3, 7, 6, 4, 9, 0
2. +------------+
| Ephraim |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Ben | | Frank |
+------------+ +------------+
/ \ \
/ \ \
/ \ \
+------------+ +------------+ +------------+
| Adam | | Dan | | Gideon |
+------------+ +------------+ +------------+
/
/
/
+------------+
| Caleb |
+------------+
3. Method Call Value Returned
----------------------------------------
mystery(grid, 5) 5
mystery(grid, 3) 22
mystery(grid, 1) 24
4. One possible solution appears below.
public String acronymFor(List<String> words) {
String acronym = "";
for (String next : words) {
acronym += next.toUpperCase().charAt(0);
}
return acronym;
}
5. Binary Trees, 10 points. One possible solution appears below.
public void printLevel(int target) {
if (target < 1) {
throw new IllegalArgumentException();
}
System.out.print("nodes at level " + target + " =");
printLevel(overallRoot, target, 1);
System.out.println();
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.print(" " + root.data);
else {
printLevel(root.left, target, level + 1);
printLevel(root.right, target, level + 1);
}
}
6. One possible solution appears below.
public Map<String, Set<List<String>>> acronyms(
Set<List<String>> lists) {
Map<String, Set<List<String>>> result =
new TreeMap<String, Set<List<String>>>();
for (List<String> words : lists) {
String acronym = acronymFor(words);
if (!result.containsKey(acronym)) {
result.put(acronym, new HashSet<List<String>>());
}
result.get(acronym).add(words);
}
return result;
}
7. 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 = other.getRating() - getRating();
if (delta < 0)
return -1;
else if (delta > 0)
return 1;
else // delta == 0
return other.reviews - reviews;
}
}
8. One possible solution appears below.
public void limitLeaves(int min) {
overallRoot = limitLeaves(overallRoot, min);
}
private IntTreeNode limitLeaves(IntTreeNode root, int min) {
if (root != null) {
root.left = limitLeaves(root.left, min);
root.right = limitLeaves(root.right, min);
if (root.left == null && root.right == null && root.data <= min)
root = null;
}
return root;
}
9. One possible solution appears below.
public boolean bubble() {
boolean swap = false;
if (front != null && front.next != null) {
if (front.data > front.next.data) {
swap = true;
ListNode temp = front;
front = front.next;
temp.next = front.next;
front.next = temp;
}
ListNode current = front;
while (current.next != null && current.next.next != null) {
if (current.next.data > current.next.next.data) {
swap = true;
ListNode temp = current.next.next;
current.next.next = temp.next;
temp.next = current.next;
current.next = temp;
}
current = current.next;
}
}
return swap;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011