<![CDATA[
CSE143 Key to Final, Winter 2016 handout #28
1. Preorder traversal 8, 7, 2, 4, 9, 5, 1, 3, 6, 0
Inorder traversal 4, 2, 9, 7, 8, 3, 1, 6, 5, 0
Postorder traversal 4, 9, 2, 7, 3, 6, 1, 0, 5, 8
2. +------------+
| George |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Emma | | Jane |
+------------+ +------------+
/ \ / \
/ \ / \
/ \ / \
+------------+ +------------+ +------------+ +------------+
| Elton | | Frank | | Harriet | | Weston |
+------------+ +------------+ +------------+ +------------+
3. Method Call Contents of Set Returned
-----------------------------------------------
mystery(grid, 2, 2) [6, 7]
mystery(grid, 0, 2) [1, 2, 5, 8]
mystery(grid, 3, 3) [1, 2, 3, 7, 9]
4. One possible solution appears below.
public Set<Point> removeDuplicates(List<Point> list) {
Set<Point> result = new HashSet<Point>();
Iterator<Point> itr = list.iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (result.contains(p)) {
itr.remove();
} else {
result.add(p);
}
}
return result;
}
5. Binary Trees, 10 points. One possible solution appears below.
public int oddPathSum() {
return oddPathSum(overallRoot, 0);
}
public int oddPathSum(IntTreeNode root, int sum) {
if (root == null) {
return 0;
} else {
sum += root.data;
int result = oddPathSum(root.left, sum) +
oddPathSum(root.right, sum);
if (sum % 2 != 0) {
result++;
}
return result;
}
}
6. One possible solution appears below.
public void recordGrade(Map<String, Map<String, Double>> grades,
String id, double grade, String course) {
if (!grades.containsKey(id)) {
grades.put(id, new TreeMap<String, Double>());
}
Map<String, Double> next = grades.get(id);
if (next.containsKey(course)) {
grade = Math.max(grade, next.get(course));
}
next.put(course, grade);
}
7. One possible solution appears below.
public class AdmissionsEntry implements Comparable<AdmissionsEntry> {
private String ID;
private int ratings;
private double total;
private boolean discuss;
public AdmissionsEntry(String ID) {
this.ID = ID;
this.ratings = 0;
this.total = 0.0;
this.discuss = false;
}
public void rate(double rating) {
ratings++;
total += rating;
if (rating >= 4) {
discuss = true;
}
}
public void flag() {
discuss = true;
}
public String getID() {
return ID;
}
public double getRating() {
if (ratings == 0) {
return 0.0;
} else {
return total / ratings;
}
}
public String toString() {
return ID + ": " + Math.round(100 * getRating()) / 100.0;
}
public int compareTo(AdmissionsEntry other) {
if (discuss && !other.discuss) {
return -1;
} else if (!discuss && other.discuss) {
return 1;
} else if (getRating() > other.getRating()) {
return -1;
} else if (getRating() < other.getRating()) {
return 1;
} else {
return ID.compareTo(other.ID);
}
}
}
8. One possible solution appears below.
public void tighten() {
overallRoot = tighten(overallRoot);
}
private IntTreeNode tighten(IntTreeNode root) {
if (root != null) {
root.left = tighten(root.left);
root.right = tighten(root.right);
if (root.left == null && root.right != null) {
root = root.right;
} else if (root.left != null && root.right == null) {
root = root.left;
}
}
return root;
}
9. One possible solution appears below.
public LinkedIntList removeFirstOf3() {
LinkedIntList other = new LinkedIntList();
if (front != null) {
other.front = front;
ListNode back1 = other.front;
front = front.next;
ListNode current = front;
while (current != null && current.next != null &&
current.next.next != null) {
current = current.next;
back1.next = current.next;
back1 = back1.next;
current.next = current.next.next;
current = current.next;
}
back1.next = null;
}
return other;
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011