<![CDATA[
CSE143 Key to Final, Fall 2011 handout #41
1. Preorder traversal 0, 3, 2, 9, 4, 1, 6, 5, 7, 8
Inorder traversal 2, 9, 3, 0, 6, 1, 5, 4, 7, 8
Postorder traversal 9, 2, 3, 6, 5, 1, 8, 7, 4, 0
2. +------------+
| Leonard |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Howard | | Penny |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Amy | | Sheldon |
+------------+ +------------+
\ /
\ /
\ /
+------------+ +------------+
| Bernadette | | Raj |
+------------+ +------------+
3. map1: {bar=1, baz=2, foo=3, mumble=4}
map2: {1=earth, 2=wind, 3=air, 4=fire}
map returned: {bar=earth, baz=wind, foo=air, mumble=fire}
map1: {five=105, four=104, one=101, six=106, three=103, two=102}
map2: {99=uno, 101=dos, 103=tres, 105=quatro}
map returned: {five=quatro, one=dos, three=tres}
map1: {a=42, b=9, c=7, d=15, e=11, f=24, g=7}
map2: {1=four, 3=score, 5=and, 7=seven, 9=years, 11=ago}
map returned: {b=years, c=seven, e=ago, g=seven}
4. Two possible solutions appear below.
public Set<Point> extractEqual(Set<Point> data) {
Set<Point> result = new HashSet<Point>();
for (Point p : data)
if (p.getX() == p.getY())
result.add(p);
return result;
}
public Set<Point> extractEqual(Set<Point> data) {
Set<Point> result = new HashSet<Point>();
Iterator<Point> i = data.iterator();
while (i.hasNext()) {
Point p = i.next();
if (p.getX() == p.getY())
result.add(p);
}
return result;
}
5. One possible solution appears below.
public void printLevel(int target) {
if (target < 1)
throw new IllegalArgumentException();
printLevel(overallRoot, target, 1);
}
private void printLevel(IntTreeNode root, int target, int level) {
if (root != null)
if (level == target)
System.out.println(root.data);
else {
printLevel(root.left, target, level + 1);
printLevel(root.right, target, level + 1);
}
}
6. One possible solution appears below.
public Map<String, List<Integer>> indexMap(List<String> data) {
Map<String, List<Integer>> result =
new TreeMap<String, List<Integer>>();
for (int i = 0; i < data.size(); i++) {
String next = data.get(i);
if (!result.containsKey(next))
result.put(next, new ArrayList<Integer>());
result.get(next).add(i);
}
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 = getRating() - other.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 max) {
overallRoot = limitLeaves(overallRoot, max);
}
private IntTreeNode limitLeaves(IntTreeNode root, int max) {
if (root != null) {
root.left = limitLeaves(root.left, max);
root.right = limitLeaves(root.right, max);
if (root.left == null && root.right == null && root.data >= max)
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