<![CDATA[
CSE143 Sample Final, Fall 2012 handout #32
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 7 | | 6 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 9 | | 0 | | 1 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 5 | | 3 | | 4 | | 8 |
+---+ +---+ +---+ +---+
Fill in each of the traversals below:
Preorder traversal __________________________________________________
Inorder traversal __________________________________________________
Postorder traversal __________________________________________________
2. Binary Search Tree, 4 points. Draw a picture below of the binary search
tree that would result from inserting the following words into an empty
binary search tree in the following order: Legolas, Frodo, Sam, Merry,
Pippin, Aragorn, Gimli, Boromir.
3. Collections Mystery, 5 points. Consider the following method:
public List<Integer> mystery(int[][] data) {
List<Integer> result = new LinkedList<Integer>();
for (int i = 0; i < data.length; i++) {
int sum = 0;
for (int j = 0; j < data[i].length; j++) {
sum = sum + j * data[i][j];
}
result.add(sum);
}
return result;
}
In the left-hand column below are specific two-dimensional arrays. Indicate
in the right-hand column what values would be stored in the list returned by
method mystery if the array in the left-hand column is passed as a parameter
to mystery.
Two-Dimensional Array Contents of List Returned
---------------------------------------------------------------------
[[1, 2, 3], [4, 5, 6]] ______________________________
[[3, 4], [1, 2, 3], [], [5, 6]] ______________________________
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] ______________________________
4. Collections Programming, 5 points. Write a method called convert that takes
an array of integers as a parameter and that returns a map that contains the
nonzero elements of the array (mapping an integer index to an integer
value). For example, if an array called list stores these values:
[0, 19, 4, 0, 0, 0, 12, 0, 0, 0, 9, 18]
then the call convert(list) should return the following map:
{1=19, 2=4, 6=12, 10=9, 11=18}
Your map should store the keys in increasing numerical order. The array
passed as a parameter should be not be changed.
5. Binary Trees, 10 points. Write a toString method for a binary tree of
integers. The method should return "empty" for an empty tree. For a leaf
node, it should return the data in the node as a String. For a branch node,
it should return a parenthesized String that has three elements separated by
commas: the data at the root followed by a String representation of the left
subtree followed by a String representation of the right subtree. For
example, if a variable t stores a reference to the following tree:
+---+
| 2 |
+---+
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ \
+---+ +---+
| 4 | | 9 |
+---+ +---+
then the call t.toString() should return the following String:
"(2, (8, 0, empty), (1, (7, 4, empty), (6, empty, 9)))"
The quotes above are used to indicate that this is a String but should not
be included in the String that you return.
You are writing a public method for a binary tree class defined as follows:
public class IntTreeNode {
public int data; // data stored in this node
public IntTreeNode left; // reference to left subtree
public IntTreeNode right; // reference to right subtree
<constructors>
}
public class IntTree {
private IntTreeNode overallRoot;
<methods>
}
You may define private helper methods to solve this problem, but otherwise
you may not call any other methods of the class. You may not define any
auxiliary data structures to solve this problem.
6. Collections Programming, 10 points. Write a method called sumStrings takes
a map whose keys are strings and whose values are points and that returns a
map that associates each point with the sum of the lengths of the strings it
is associated with in the first map.
For example, suppose that a map called data has the following associations:
{a=[x=1,y=3], apple=[x=7,y=7], be=[x=4,y=7], bear=[x=7,y=4],
carpet=[x=2,y=19], cat=[x=1,y=3], dog=[x=2,y=18], specialty=[x=7,y=4],
student=[x=1,y=3], umbrella=[x=42,y=8]}
Then the call sumStrings(data) should return the following map:
{[x=7,y=7]=5, [x=42,y=8]=8, [x=2,y=18]=3, [x=1,y=3]=11, [x=2,y=19]=6,
[x=7,y=4]=13, [x=4,y=7]=2}
Notice that the point [x=7,y=7] maps to 5 in the result because it was
associated with a string of length 5 in the original ("apple"). Notice that
[x=1,y=3] maps to 11 because it was associated with three strings ("a",
"cat", "student") whose lengths add up to 11 (1, 3, 7).
Your method should construct the new map and can construct iterators but
should otherwise not construct any new data structures. It should also not
modify the map passed as a parameter and it should be reasonably efficient.
7. Comparable class, 20 points. Define a class called TimeSpan that keeps
track of an amount of time. A time span can be thought of in two ways. You
can think of it as being a certain number of hours, minutes, and seconds
where each hour is composed of 60 minutes and each minute is composed of 60
seconds. Or you can think of it as the total number of seconds. The class
has the following public methods:
TimeSpan(hrs, min, sec) constructs a TimeSpan object with the given
hours, minutes, and seconds
hours() returns the number of hours
minutes() returns the number of minutes (0 to 59)
seconds() returns the number of seconds (0 to 59)
totalSeconds() returns the total number of seconds including
the minutes and hours components
add(other) returns a new TimeSpan object formed by adding
this TimeSpan to the other TimeSpan
toString() returns a string in the form "hhh:mm:ss"
For example, the following code constructs three TimeSpan objects:
TimeSpan t1 = new TimeSpan(18, 3, 54);
TimeSpan t2 = new TimeSpan(95, 58, 7);
TimeSpan t3 = t1.add(t2);
The first TimeSpan object is expressed as 18 hours, 3 minutes, and 54
seconds. The totalSeconds method would report this as 65034 seconds. The
call t1.toString() should produce "18:03:54". Notice that the minutes are
reported as two digits even when it is a single digit. The same should be
true of the seconds, so t2.toString() should produce the string "95:58:07".
Your class should make sure that minutes and seconds are always reported as
being between 0 and 59. When t1 and t2 are added together to produce t3,
the resulting time should be reported as 114 hours, 2 minutes, and 1 second,
with t3.toString() returning "114:02:01".
Your constructor should throw an IllegalArgumentException if any value
passed to it is negative. It should fix values of minutes and seconds that
are higher than 59, adjusting hours and minutes appropriately. For example,
given the following call:
TimeSpan t4 = new TimeSpan(4, 65, 100);
the resulting TimeSpan object should be reported as 5 hours, 6 minutes, and
40 seconds with t4.toString() returning "5:06:40".
The TimeSpan class should implement the Comparable<E> interface, where a
shorter amount of time is considered less than a longer amount of time.
8. Binary Trees, 20 points. Write a method called add that takes as a
parameter a reference to a second binary tree and that adds the values in
the second tree to this tree. If the method is called as follows:
tree1.add(tree2);
it should add all values in tree2 to the corresponding nodes in tree1. In
other words, the value stored at the root of tree2 should be added to the
value stored at the root of tree1 and the values in tree2's left and right
subtrees should be added to the corresponding positions in tree1's left and
right subtrees. The values in tree2 should not be changed by your method.
initial tree1 initial tree2 final tree1
+---+ +---+ +---+
| 1 | | 2 | | 3 |
+---+ +---+ +---+
/ \ / \ / \
+---+ +---+ +---+ +---+ +---+ +---+
| 4 | | 7 | | 3 | | 1 | | 7 | | 8 |
+---+ +---+ +---+ +---+ +---+ +---+
If tree1 has a node that has no corresponding node in tree2, then that node
is unchanged. For example, if tree2 is empty, tree1 is not changed at all.
It is also possible that tree2 will have one or more nodes that have no
corresponding node in tree1. For each such node, create a new node in tree1
in the corresponding position with the value stored in tree2's node. For
example:
initial tree1 initial tree2 final tree1
+---+ +---+ +---+
| 6 | | 1 | | 7 |
+---+ +---+ +---+
/ / \ / \
+---+ +---+ +---+ +---+ +---+
| 2 | | 4 | | 5 | | 6 | | 5 |
+---+ +---+ +---+ +---+ +---+
/ \ / \
+---+ +---+ +---+ +---+
| 8 | | 2 | | 8 | | 2 |
+---+ +---+ +---+ +---+
You are writing a public method for a binary tree class defined as follows:
public class IntTreeNode {
public int data; // data stored in this node
public IntTreeNode left; // reference to left subtree
public IntTreeNode right; // reference to right subtree
// post: constructs an IntTreeNode with the given data and links
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public class IntTree {
private IntTreeNode overallRoot;
<methods>
}
You are writing a method that will become part of the IntTree class. You
may define private helper methods to solve this problem, but otherwise you
may not assume that any particular methods are available. You are NOT to
replace any of the existing nodes in the tree. You will, however, construct
new nodes to be inserted into the tree as described above.
9. Linked Lists, 20 points. Write a method called rearrange that rearranges
the order of a list of integers so that all of the values in even-numbered
positions appear in reverse order followed by all of the values in
odd-numbered positions in forward order. We are using zero-based indexing,
as with Java arrays and lists, where the first element is considered to be
at position 0. For example, if a variable called list stores these values:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
and you make the following call:
list.rearrange();
the list should store the following values after the call:
[8, 6, 4, 2, 0, 1, 3, 5, 7, 9]
In this example the values in the original list were equal to their
positions and there were an even number of elements, but that won't
necessarily be the case. For example, if the list had instead stored:
[3, 8, 15, 9, 4, 42, 5]
then after a call on rearrange it would store:
[5, 4, 15, 3, 8, 9, 42]
If the list has fewer than two elements, it should be unchanged by a call on
rearrange.
You are writing a public method for a linked list class defined as follows:
public class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
<constructors>
}
public class LinkedIntList {
private ListNode front;
<methods>
}
You are writing a method that will become part of the LinkedIntList class.
You may define private helper methods to solve this problem, but otherwise
you may not assume that any particular methods are available. You are
allowed to define your own variables of type ListNode, but you may not
construct any new nodes, and you may not use any auxiliary data structure to
solve this problem (no array, ArrayList, stack, queue, String, etc). You
also may not change any data fields of the nodes. You MUST solve this
problem by rearranging the links of the list. Your solution must run in
O(n) time where n is the length of the list.
]]>