<![CDATA[
Key to CSE143X Final, Fall 2016
1. Preorder traversal 4, 2, 7, 9, 3, 6, 1, 8, 5, 0
Inorder traversal 7, 9, 2, 3, 6, 4, 8, 1, 0, 5
Postorder traversal 9, 7, 6, 3, 2, 8, 0, 5, 1, 4
2. One possible solution appears below.
public void writeSquares(int n) {
if (n < 1) {
throw new IllegalArgumentException();
} else if (n == 1) {
System.out.print(1);
} else if (n % 2 == 1) {
System.out.print(n * n + ", ");
writeSquares(n - 1);
} else {
writeSquares(n - 1);
System.out.print(", " + n * n);
}
}
3. Statement Output
------------------------------------------------------------
var1.method1(); compiler error
var2.method1(); Rain 1
var1.method2(); Sleet 2/Snow 2/Sleet 3
var2.method2(); Rain 2
var3.method2(); Sleet 2/Snow 2/Fog 3
var4.method2(); compiler error
var5.method2(); Sleet 2/Snow 2/Fog 3
var1.method3(); Sleet 3
var2.method3(); Snow 3
var3.method3(); Fog 3
var4.method3(); compiler error
var5.method3(); Fog 3
((Rain)var4).method1(); runtime error
((Fog)var5).method1(); Fog 1
((Sleet)var3).method1(); compiler error
((Sleet)var3).method3(); Fog 3
((Fog)var6).method3(); runtime error
((Snow)var4).method2(); Snow 2
((Sleet)var4).method3(); runtime error
((Rain)var6).method3(); Snow 3
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 static int parityMatches(Stack<Integer> s1, Stack<Integer> s2) {
if (s1.size() != s2.size()) {
throw new IllegalArgumentException();
}
Queue<Integer> q = new LinkedList<Integer>();
int count = 0;
while (!s1.isEmpty()) {
int num1 = s1.pop();
int num2 = s2.pop();
if (num1 % 2 == num2 % 2)
count++;
q.add(num1);
q.add(num2);
}
while (!q.isEmpty())
s1.push(q.remove());
while (!s1.isEmpty())
q.add(s1.pop());
while (!q.isEmpty()) {
s2.push(q.remove());
s1.push(q.remove());
}
return count;
}
6. One possible solution appears below.
public int purebredOdds() {
return purebredOdds(overallRoot);
}
private int purebredOdds(IntTreeNode root) {
if (root == null || root.data % 2 == 0)
return 0;
else
return 1 + purebredOdds(root.left) + purebredOdds(root.right);
}
7. 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;
}
8. One possible solution appears below.
class BookData implements Comparable<BookData> {
private String title;
private int reviews;
private double total;
public BookData(String title) {
this.title = title;
this.reviews = 0;
this.total = 0.0;
}
public void review(double rating) {
reviews++;
total += rating;
}
public double getRating() {
return total / reviews;
}
public String toString() {
return title + " " + getRating() + " (reviews: " + reviews + ")";
}
public int compareTo(BookData other) {
if (getRating() > other.getRating()) {
return -1;
} else if (getRating() < other.getRating()) {
return 1;
} else {
return other.reviews - reviews;
}
}
}
9. One possible solution appears below.
public void stretch() {
overallRoot = stretch(overallRoot);
}
private IntTreeNode stretch(IntTreeNode root) {
if (root != null) {
root.left = stretch(root.left);
root.right = stretch(root.right);
if (root.left != null && root.right == null)
root = new IntTreeNode(1, root, null);
else if (root.left == null && root.right != null)
root = new IntTreeNode(1, null, root);
}
return root;
}
10. One possible solution appears below.
public void mergeFrom(LinkedIntList other) {
if (other.front != null) {
if (front == null)
front = other.front;
else {
ListNode current1 = front;
ListNode current2 = other.front;
if (front.data <= other.front.data) {
current1 = current1.next;
} else {
front = other.front;
current2 = current2.next;
}
ListNode current3 = front;
while (current1 != null && current2 != null) {
if (current1.data <= current2.data) {
current3.next = current1;
current1 = current1.next;
} else {
current3.next = current2;
current2 = current2.next;
}
current3 = current3.next;
}
if (current1 != null) {
current3.next = current1;
} else {
current3.next = current2;
}
}
other.front = null;
}
}
]]>