<![CDATA[
CSE143X Key to Sample Final, Autumn 2024 handout #24
1. Preorder traversal 0, 4, 7, 9, 2, 6, 1, 8, 5, 3
Inorder traversal 4, 0, 2, 9, 7, 8, 1, 6, 5, 3
Postorder traversal 4, 2, 9, 8, 1, 3, 5, 6, 7, 0
2. +------------+
| Moira |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Alexis | | Stevie |
+------------+ +------------+
\ / \
\ / \
\ / \
+------------+ +------------+ +------------+
| Johnny | | Roland | | Ted |
+------------+ +------------+ +------------+
/
/
/
+------------+
| David |
+------------+
3. Method Call Contents of Set Returned
-----------------------------------------------
mystery(grid, 0) [2, 4]
mystery(grid, 1) [4, 5, 6, 9]
mystery(grid, 3) [4, 5, 6]
4. One possible solution appears below.
public void retainAll(Set<Integer> s1, Set<Integer> s2) {
Iterator<Integer> itr = s1.iterator();
while (itr.hasNext()) {
if (!s2.contains(itr.next())) {
itr.remove();
}
}
}
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 static Map<Point, List<Integer>> pointMap(List<Point> data) {
Map<Point, List<Integer>> map = new HashMap<>();
for (int i = 0; i < data.size(); i++) {
Point p = data.get(i);
if (!map.containsKey(p)) {
map.put(p, new ArrayList<>());
}
map.get(p).add(i);
}
return map;
}
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 add(IntTree other) {
overallRoot = add(overallRoot, other.overallRoot);
}
private IntTreeNode add(IntTreeNode root1, IntTreeNode root2) {
if (root2 != null) {
if (root1 == null) {
root1 = new IntTreeNode(0);
}
root1.data += root2.data;
root1.left = add(root1.left, root2.left);
root1.right = add(root1.right, root2.right);
}
return root1;
}
9. One possible solution appears below.
public void switchPairsOfPairs() {
if (front != null && front.next != null &&
front.next.next != null && front.next.next.next != null) {
ListNode current = front.next.next;
front.next.next = current.next.next;
current.next.next = front;
front = current;
current = current.next.next.next;
while (current.next != null && current.next.next != null &&
current.next.next.next != null &&
current.next.next.next.next != null) {
ListNode temp = current.next.next.next;
current.next.next.next = temp.next.next;
temp.next.next = current.next;
current.next = temp;
current = temp.next.next.next;
}
}
}
]]>