<![CDATA[
CSE143 Sample Final handout #32
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 9 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 4 | | 6 | | 0 |
+---+ +---+ +---+ +---+
\ \ /
\ \ /
+---+ +---+ +---+
| 8 | | 1 | | 5 |
+---+ +---+ +---+
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: Grumpy, Doc, Dopey, Bashful,
Happy, Sneezy, Sleepy.
3. Binary Trees, 10 points. Write a method isFull that returns whether or not
a binary tree is full (true if it is, false otherwise). A full binary tree
is one in which every node has 0 or 2 children. The QuestionTree of
assignment #7 and the HuffmanTree of assignment #8 are examples of full
binary trees. Below are examples of each.
full tree not a full tree
+---+ +---+
| 2 | | 7 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 1 | | 4 | | 0 |
+---+ +---+ +---+ +---+
/ \ / \ \
/ \ / \ \
+---+ +---+ +---+ +---+ +---+
| 8 | | 7 | | 9 | | 2 | | 8 |
+---+ +---+ +---+ +---+ +---+
The right-hand tree is not full because the node with 0 in it has one child.
By definition, the empty tree is considered full.
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 isFull below.
4. Programming with inheritance, 20 points. A company has developed a class
called TransactionList that it uses for storing transactions. They find
that they need to be able to control whether or not the list can be
modified. Rather than rewrite the code, they have decided to write a new
version called SafeTransactionList that provides this functionality. The
existing TransactionList has the following public methods:
public TransactionList(AccountInfo info) constructs an empty list
public void add(Transaction t) adds a transaction
public Transaction get(int index) gets the transaction at the
given index
public int indexOf(Transaction t) returns the index of the given
transaction, -1 if not found
public Transaction remove(int index) removes and returns the
transaction at the given index
public void set(int index, Transaction t) replaces the transaction at the
given index with "t"
public int size() returns the size of the list
You are to write a class called SafeTransactionList that extends this class,
providing the same functionality and also providing a mechanism for
controlling whether or not the list can be modified. When the list is set
to be modifiable, the methods operate normally. When the list is set to be
not modifiable, any attempt to modify the state of the list should generate
an IllegalStateException. The methods that change the state of the list are
the methods that add, remove and set transactions.
When constructed, the list should be modifiable. The new class should have
the following public methods that will allow the client to control whether
or not the list is considered to be modifiable:
public void setModifiable(boolean value) uses given value to set whether
or not the list is modifiable
public boolean getModifiable() returns whether or not the
list is currently modifiable
Write your solution to SafeTransactionList below.
5. Comparable class, 20 points. Define a class Complex that can be used to
store complex numbers. In Mathematics, complex numbers are those that can
be written as (x + y * i) where x and y are real numbers and i is the square
root of minus one. In other words, complex numbers have a real part (x) and
an imaginary part (y). Your class should include the following methods:
Complex(x, y) constructs a complex number x + y * i
getReal() returns the real part of the number
getImaginary() returns the imaginary part of the number
abs() returns the absolute value of the number
toString() returns a String representation of the number
add(other) returns the result of adding another Complex number
to this one
subtract(other) returns the result of subtracting another Complex
number from this one
The absolute value of a complex number is defined to be the square root of
the sum of the squares of x and y. Recall that Java has a method Math.sqrt
for computing square roots.
The add and subtract methods should return new Complex objects that
represent the result of adding or subtracting the other complex number. You
add two complex numbers by adding their real and imaginary parts. You
subtract two complex numbers by subtracting their real and imaginary parts.
The toString method should generally return numbers in the form "x + yi", as
in "3.6 + 4.5i" or "-3.6 + 2.7i". If the imaginary part is 0, then it
should return just the real part, as in "3.6" or "-3.6". If the imaginary
part is negative, it should return something of the form "3.6 - 4.5i" rather
than "3.6 + -4.5i". If the real part is zero and the imaginary part is
nonzero, it should return just the imaginary part, as in "4.5i" or "-4.5i".
Your class should implement the Comparable<E> interface. Complex objects
should be compared using absolute value with numbers of smaller absolute
value considered "less" than numbers of higher absolute value.
Write your solution to Complex below.
6. Binary Trees, 20 points. Write a method construct that takes a sorted array
of integers as a parameter and that constructs a balanced binary search tree
containing those integers. The tree that is constructed should have the
property that for every node in the tree, either the left and right subtrees
have the same number of nodes or the left subtree has one more node than the
right subtree.
For example, if an array called list stores the values (1, 2, 3, 4, 5, 6, 7)
and the following call is made for a variable t of type Tree:
t.construct(list);
Then t should store the following tree after the call is made:
+---+
| 4 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 6 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 1 | | 3 | | 5 | | 7 |
+---+ +---+ +---+ +---+
If the array had instead stored (3, 8, 19, 27, 34, 42, 49, 53, 67, 74), then
the following tree would have been constructed:
+----+
| 42 |
+----+
/ \
/ \
+----+ +----+
| 19 | | 67 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 8 | | 34 | | 53 | | 74 |
+----+ +----+ +----+ +----+
/ / /
/ / /
+----+ +----+ +----+
| 3 | | 27 | | 49 |
+----+ +----+ +----+
Notice that when it is not possible to have left and right subtrees of equal
size, the extra value always ends up in the left subtree, as in the overall
tree which has 5 nodes in the left subtree and 4 in the right.
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
// post: constructs a leaf node with given data
public TreeNode(int data) {
this(data, null, null);
}
// post: constructs a TreeNode with the given data and links
public TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public class Tree {
private TreeNode root; // reference to the overall root
<methods>
}
This problem involves constructing a new tree from an array of values. If
there are "n" values in the array, then you should construct exactly "n"
tree nodes. The new tree should replace any old tree. You are not allowed
to use any other data structures (arrays, lists, Strings, etc) to solve this
problem, you are not allowed to alter the array that you are passed and your
solution must run in O(n) time. You can, however, assume that the values in
the array appear in sorted (nondecreasing) order.
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 construct below.
7. Linked Lists, 20 points. Write a method removeEvens that removes the values
in even-numbered positions from a list, returning those values in their
original order as a new list. For example if a variable called list1 stores
these values:
list1: (8, 13, 17, 4, 9, 12, 98, 41, 7, 23, 0, 92)
Then the following call:
LinkedIntList list2 = list1.removeEvens();
Should result in list1 and list2 storing the following values:
list1: (13, 4, 12, 41, 23, 92)
list2: (8, 17, 9, 98, 7, 0)
Notice that the values stored in list2 are the values that were originally
in even-valued positions (index 0, index 2, index 4, and so on) and that
these values appear in the same order as in the original list. Also notice
that the values left in list1 also appear in the same order as in the
original list.
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.
Recall that is has a zero-argument constructor that returns an empty list.
You may not call any methods of the class other than the constructor 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 removeEvens below.
]]>