<![CDATA[
CSE143 Sample Final handout #34
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 3 |
+---+
\
\
+---+
| 5 |
+---+
/ \
/ \
+---+ +---+
| 9 | | 7 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 6 | | 8 | | 1 |
+---+ +---+ +---+
/ \ /
/ \ /
+---+ +---+ +---+
| 0 | | 2 | | 4 |
+---+ +---+ +---+
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 names into an empty
binary search tree in the following order: Johanna, Nehemiah, Rachel, Lacy,
Danny, Wes, Melinda.
3. Binary Trees, 10 points. Write a method numEmpty that returns the number of
empty subtrees in a binary tree. Every empty subtree is associated with a
particular parent node. A leaf node, instead of having children, has two
empty subtrees. A node with one nonempty child has one empty subtree. And
a node with two nonempty children has no empty subtrees that it is a direct
parent of. For example, in the tree below:
+---+
| 3 |
+---+
/ \
/ \
+---+ +---+
| 4 | | 7 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 0 | | 9 | | 2 |
+---+ +---+ +---+
/
/
+---+
| 8 |
+---+
The leaf nodes (0, 8, 2) each have two empty subtrees. The nodes with one
nonempty child (9, 7) each have one empty subtree. The nodes with two
nonempty children (3, 4) do not have any empty subtrees directly under them.
Therefore in this tree there are a total of 8 empty subtrees. By
definition, the empty tree has one empty subtree.
Assume that you are writing a public method for a binary tree class defined
as follows:
public class TreeNode {
public int data; // data stored in this node
public TreeNode left; // reference to left subtree
public TreeNode right; // reference to right subtree
<constructors>
}
public class Tree {
private TreeNode root; // reference to the overall root
<methods>
}
You are writing a method that will become part of the Tree class. You may
define private helper methods to solve this problem, but otherwise you may
not call any other methods of the class.
Write your solution to numEmpty below.
4. Programming with inheritance, 20 points. Assume that there is a class
called Stack that provides an implementation of a simple stack. In
particular, suppose that it has the following public methods.
public Stack() constructs an empty stack
public void push(Object v) pushes v onto the top of the stack
public Object pop() removes and returns the top of the stack
public boolean isEmpty() true if stack is empty, false otherwise
public int size() returns the # of elements in the stack
You are to write a class called UndoStack that extends the functionality of
the Stack class to allow an "undo" operation. The idea is that any push or
pop can be undone by a call to "undo." If several push and/or pop
operations have been performed, it should be possible to perform several
undo operations in a row, each one reversing the most recent operation that
hasn't yet been reversed. Notice that If no push or pop operations have
been performed, there is nothing to undo. Similarly, if all push and pop
operations have been undone, there will be nothing left to undo. Your class
has to provide a mechanism for checking whether or not there is something
left to undo. In particular, it should provide the methods above as well as
the following public methods:
public void undo() undoes the most recent push or pop that
hasn't already been undone
public boolean canUndo() returns true if there is something to
undo, false otherwise
If undo is called when canUndo returns false, it should throw an
IllegalStateException. Your class may have its own data structure(s), but
you may not reimplement the stack. Your new class must extend the existing
Stack class and must rely on the existing class to perform basic Stack
operations. All of the public operations for your new class must be O(1)
(assuming the original Stack operations are all O(1)).
Write your solution to UndoStack below.
5. Comparable class, 20 points. Define a class USCurrency that can be used to
store a currency amount in dollars and cents (both integers) where one
dollar equals 100 cents. Your class should include the following methods:
USCurrency(dollars, cents) constructs a currency object with given
dollars and cents
dollars() returns the dollars
cents() returns the cents
toString() returns a String in standard $d.cc notation
(-$d.cc for negative amounts)
add(other) returns the result of adding another
currency amount to this one
subtract(other) returns the result of subtracting another
currency amount from this one
A currency amount can be negative. The cents method should return values in
the range of 0 to 99 for nonnegative currency amounts and should return
values in the range of 0 to -99 for negative currency amounts.
The add and subtract methods should return new USCurrency objects that
represent the result of adding or subtracting the other currency amount.
Note that the toString method should return the amount in a standard format
($d.cc) with two digits for cents and with negative values indicated with a
single minus sign in front of the dollar sign (-$d.cc). For example, 4
dollars and 5 cents would be expressed as "$4.05" while -19 dollars and -43
cents would be expressed as "-$19.43".
In addition, your class should implement the Comparable interface.
USCurrency objects should be compared in the obvious way, with smaller
currency amounts considered "less" than larger currency amounts (e.g.,
-$13.45 < -$2.03 < $5.13 < $98.06).
Write your solution to USCurrency below.
6. Binary Trees, 20 points. Write a method removeLeaves that removes all of
the leaf nodes from a binary tree of integers. Remember that a leaf node is
a node that has empty left and right subtrees. For example, if a variable t
stores a reference to the following tree:
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 9 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 1 | | 4 | | 6 | | 8 |
+---+ +---+ +---+ +---+
\
\
+---+
| 0 |
+---+
Then the call:
t.removeLeaves();
should remove the four leaves from the tree (the nodes with data values 1,
4, 6 and 0), leaving the following tree:
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 9 |
+---+ +---+
\
\
+---+
| 8 |
+---+
A second call on the method would eliminate the two leaves in this tree (the
ones with data values 3 and 8):
+---+
| 7 |
+---+
\
\
+---+
| 9 |
+---+
Another call would eliminate the one leaf with data value 9:
+---+
| 7 |
+---+
Another call would leave an empty tree because the previous tree is composed
of exactly one leaf node. If called with an empty tree, the method does not
change the tree because there are no nodes of any kind (leaf or not).
Assume that you are writing a public method for a binary tree class defined
as follows:
public class TreeNode {
public int data; // data stored in this node
public TreeNode left; // reference to left subtree
public TreeNode right; // reference to right subtree
<constructors>
}
public class Tree {
private TreeNode root; // reference to the overall root
<methods>
}
You are writing a method that will become part of the Tree class. 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 create any new nodes
to solve this problem.
Write your solution to removeLeaves below.
7. Linked Lists, 20 points. Write a method switchPairs that switches the order
of elements in a linked list of integers in a pairwise fashion. Your method
should switch the order of the first two values, then switch the order of
the next two, switch the order of the next two, and so on.
For example, if the list initially stores these values:
(3, 7, 4, 9, 8, 12)
your method should switch the first pair (3, 7), the second pair (4, 9) and
the third pair (8, 12), to yield this list:
(7, 3, 9, 4, 12, 8)
If there are an odd number of values in the list, the final element is not
moved. For example, if the original list had been:
(3, 7, 4, 9, 8, 12, 2)
It would again switch pairs of values, but the final value (2) would not be
moved, yielding this list:
(7, 3, 9, 4, 12, 8, 2)
Assume that we are using a linked list that stores integers, as discussed in
lecture (handouts 8 and 9).
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 not call any other methods of the class to solve this problem. You
are not allowed to create any new nodes or to change the values stored in
data fields to solve this problem. You MUST solve it by rearranging the
links of the list.
Write your solution to switchPairs below.
]]>