<![CDATA[
CSE143X Sample Final, Fall 2012 handout #34
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. Recursive Programming, 9 points. Write a recursive method called
printDashed that takes an integer as a parameter and that prints the integer
with dashes in between the digits.
The table below shows sample calls and the output that should be produced:
Method call Output Method call Output
------------------------------ ---------------------------------
printDashed(-834) -8-3-4 printDashed(6) 6
printDashed(-17) -1-7 printDashed(42) 4-2
printDashed(-4) -4 printDashed(983) 9-8-3
printDashed(0) 0 printDashed(29348) 2-9-3-4-8
Notice that no dashes are printed for positive one-digit numbers and that a
leading dash is printed only for negative numbers. You are not allowed to
construct any structured objects (no array, ArrayList, String,
StringBuilder, etc) and you may not use a while loop, for loop, or do/while
loop to solve this problem; you must use recursion.
3. Details of inheritance, 10 points. Assuming that the following classes have
been defined:
public class Gorge extends Cliff {
public void method2() {
System.out.println("Gorge 2");
}
public void method3() {
System.out.println("Gorge 3");
}
}
public class Hill extends Peak {
public void method2() {
System.out.println("Hill 2");
}
public void method3() {
System.out.println("Hill 3");
}
}
public class Peak {
public void method1() {
System.out.println("Peak 1");
method3();
}
public void method3() {
System.out.println("Peak 3");
}
}
public class Cliff extends Peak {
public void method3() {
System.out.println("Cliff 3");
super.method3();
}
}
And assuming the following variables have been defined:
Peak var1 = new Cliff();
Gorge var2 = new Gorge();
Peak var3 = new Hill();
Peak var4 = new Gorge();
Peak var5 = new Peak();
Object var6 = new Cliff();
In the table below, indicate in the right-hand column the output produced by
the statement in the left-hand column. If the statement produces more than
one line of output, indicate the line breaks with slashes as in "a/b/c" to
indicate three lines of output with "a" followed by "b" followed by "c". If
the statement causes an error, fill in the right-hand column with either the
phrase "compiler error" or "runtime error" to indicate when the error would
be detected.
Statement Output
------------------------------------------------------------
var1.method1(); ____________________________
var2.method1(); ____________________________
var3.method1(); ____________________________
var4.method1(); ____________________________
var5.method1(); ____________________________
var6.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
((Gorge)var6).method1(); ____________________________
((Cliff)var3).method2(); ____________________________
((Gorge)var4).method2(); ____________________________
((Gorge)var3).method2(); ____________________________
((Hill)var3).method2(); ____________________________
((Gorge)var1).method1(); ____________________________
((Cliff)var4).method3(); ____________________________
((Peak)var6).method3(); ____________________________
4. Stacks/Queues, 10 points. Write a method called removeMin that takes a
stack of integers as a parameter and that removes and returns the smallest
value from the stack. For example, if a variable called s stores the
following sequence of values:
bottom [2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, -8, 4] top
and you make the following call:
int n = removeMin(s);
the method removes and returns the value -8 from the stack, so that the
variable n will be -8 after the call and s will store the following values:
bottom [2, 8, 3, 19, 7, 3, 2, 42, 9, 3, 2, 7, 12, 4] top
If the minimum value appears more than once, all occurrences of the minimum
should be removed from the stack. For example, given the ending value of
the stack above, if we again call removeMin(s), the method would return 2
and would leave the stack in the following state:
bottom [8, 3, 19, 7, 3, 42, 9, 3, 7, 12, 4] top
You are to use one queue as auxiliary storage to solve this problem. You
may not use any other auxiliary data structures to solve this problem,
although you can have as many simple variables as you like. You also may
not solve the problem recursively. Your solution must run in O(n) time
where n is the size of the stack. Use the Stack and Queue structures
described in the cheat sheet and obey the restrictions described there.
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, 15 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, 15 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, 15 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.
]]>