<![CDATA[
CSE143 Key to Final, Autumn 2007 handout #38
1. Binary Tree Traversals, 6 points.
Preorder traversal 7, 6, 3, 8, 5, 0, 2, 1, 9, 4
Inorder traversal 3, 8, 6, 7, 2, 0, 1, 5, 9, 4
Postorder traversal 8, 3, 6, 2, 1, 0, 4, 9, 5, 7
2. Binary Search Tree, 4 points.
+------------+
| Grammar |
+------------+
/ \
/ \
/ \
+------------+ +------------+
| Geometry | | Logic |
+------------+ +------------+
/ \
/ \
/ \
+------------+ +------------+
| Arithmetic | | Rhetoric |
+------------+ +------------+
\ /
\ /
\ /
+------------+ +------------+
| Astronomy | | Music |
+------------+ +------------+
3. Binary Trees, 10 points. One possible solution appears below.
public List<Integer> inorderList() {
List<Integer> result = new ArrayList<Integer>();
inorderList(result, overallRoot);
return result;
}
private void inorderList(List<Integer> result, IntTreeNode root) {
if (root != null) {
inorderList(result, root.left);
result.add(root.data);
inorderList(result, root.right);
}
}
4. Programming with inheritance, 20 points. One possible solution appears
below.
public class ExtendedSearchTool extends SearchTool {
private int[] queryCount;
private int resultCount;
public ExtendedSearchTool(String engine) {
super(engine);
queryCount = new int[26];
}
public List<String> search(String query) {
if (query.length() >= 25)
queryCount[25]++;
else
queryCount[query.length()]++;
List<String> result = super.search(query);
resultCount += result.size();
return result;
}
public double averageResultLength() {
if (searchCount() == 0)
return 0.0;
else
return (double) resultCount / searchCount();
}
public double percent(int length) {
if (searchCount() == 0)
return 0.0;
else
return 100.0 * queryCount[length] / searchCount();
}
}
5. Comparable class, 20 points. One possible solution appears below.
public class MapLocation implements Comparable<MapLocation> {
private char row;
private int column;
private String name;
public MapLocation(char row, int column, String name) {
if (row < 'A' || row > 'Z' || column < 1)
throw new IllegalArgumentException();
this.row = row;
this.column = column;
this.name = name;
}
public String getCoordinates() {
return "" + row + column;
}
public String getName() {
return name;
}
public int compareTo(MapLocation other) {
if (row != other.row)
return row - other.row;
else if (column != other.column)
return column - other.column;
else
return name.compareTo(other.name);
}
public String toString() {
return name + " (" + row + column + ")";
}
}
6. Binary Trees, 20 points. 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;
}
7. Linked Lists. One possible solution appears below.
public void removeDuplicates() {
ListNode current = front;
while (current != null && current.next != null) {
ListNode current2 = current;
while (current2.next != null) {
if (current2.next.data == current.data)
current2.next = current2.next.next;
else
current2 = current2.next;
}
current = current.next;
}
}
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011