<![CDATA[
CSE143 Sample Final handout #31
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 3 |
+---+
/ \
/ \
+---+ +---+
| 7 | | 4 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 2 | | 6 | | 0 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 1 | | 9 | | 5 | | 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 names into an empty
binary search tree in the following order: Dancer, Prancer, Vixen, Rudolph,
Comet, Cupid, Blitzen.
3. Binary Trees, 10 points. Write a method doublePositives that doubles all
data values greater than 0 in a binary tree of integers. For example, if a
variable t stores a reference to the following tree:
+----+
| 10 |
+----+
/ \
/ \
+----+ +----+
| 7 | | -4 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 0 | | 18 | | -7 |
+----+ +----+ +----+
Then the call:
t.doublePositives();
would double the positive values (10, 7 and 18):
+----+
| 20 |
+----+
/ \
/ \
+----+ +----+
| 14 | | -4 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 0 | | 36 | | -7 |
+----+ +----+ +----+
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
not call any other methods of the class to solve this problem.
Write your solution to doublePositives below.
4. Programming with inheritance, 20 points. A cash processing company has
developed a Java class called Account that can be used to process
transactions. It has many methods including the following:
public Account(Client c)
// the only constructor for an Account, takes as a parameter a
// a reference to a Client object that stores start-up information
public boolean process(Transaction t)
// processes the next transaction, returning true if the transaction
// was approved and returning false otherwise
The Transaction class also has many methods including:
public int value()
// returns the value of this transaction in pennies (could be
// negative, positive or zero)
Assume that all transactions enter the system by a call on the process
method described above. The company wishes to create a slight modification
to the Account class that filters out zero-valued transactions. You are to
design a new class called FilteredAccount whose instances can be used in
place of an Account object but which include the extra behavior of not
processing transactions with a value of 0. More specifically, the new class
should indicate that a zero-valued transaction was approved but shouldn't
call the process method in the Account class to process it. Your class
should have a single constructor that takes a parameter of type Client and
it should include the following method:
public double percentFiltered()
// returns the percent of transactions filtered out (between 0.0 and
// 100.0); returns 0.0 if no transactions of any kind have been
// submitted
Write your definition of class FilteredAccount below.
5. Comparable class, 20 points. Define a class Point that can be used to store
a 2-dimensional point with x and y coordinates (both doubles). Your class
should include the following methods:
Point() constructs the Point (0, 0)
Point(x, y) constructs a point with the given coordinates
setLocation(x, y) sets the coordinates to the given values
getX() returns the x coordinate
getY() returns the y coordinate
toString() returns a String in standard (x, y) notation
distanceFrom(Point p) returns the distance from another point
Remember that the distance between two points is defined as the square root
of the sum of the squares of the differences between the x and y
coordinates. The method Math.sqrt can be used to compute a square root.
In addition, your class should implement the Comparable interface. Points
should be compared relative to their distance from the origin with points
closer to the origin considered "less" than points farther from the origin.
6. Binary Trees, 20 points. Write a method grow that constructs a particular
kind of binary tree given an integer value n. If the method is passed a
value less than 1, it should construct an empty tree. If it is passed the
value 1, it should construct a tree composed of one leaf node with the value
1 in it. And if it is passed a value greater than 1, it should construct a
branch node with that value in it whose left and right subtrees are grown in
the same manner using half of the original value. If the value is odd, the
left subtree should be grown using a value one higher than the value used
for the right subtree.
For example, the call:
t.grow(4);
should grow the following tree:
+---+
| 4 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 2 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 1 | | 1 | | 1 | | 1 |
+---+ +---+ +---+ +---+
In the case above, the left subtrees end up having the same structure as the
right subtrees because we were dealing with only even numbers. Consider the
result if we grow a tree using the value 5:
+---+
| 5 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 2 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 2 | | 1 | | 1 | | 1 |
+---+ +---+ +---+ +---+
/ \
/ \
+---+ +---+
| 1 | | 1 |
+---+ +---+
In this case two of the left subtrees have one more node than their siblings
because we had to deal with odd numbers like 5 and 3.
(continued on next page)
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
// constructs a leaf with given data
TreeNode(int data) {
this(data, null, null);
}
// constructs a node with given data and links
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>
}
You are writing a method that will become part of the Tree class. You may
not call any other methods of the class to solve this problem.
Your method will end up replacing any tree that might already be stored in
the object. Write your solution to method grow below.
7. Linked Lists, 20 points. Write a method removeRange that removes a section
of a linked list of integers. We will use the Java convention of referring
to the first element of the list as having position 0, the second having
position 1 and so on. To call removeRange, you must specify two positions,
as in:
lst.removeRange(3, 8);
This requests the removal of all values between positions 3 and 8 inclusive.
For example, if the list had contained the following values before this
call:
(8, 13, 17, 4, 9, 12, 98, 41, 7, 23, 0, 92)
the values between position 3 (the value 4) and position 8 (the value 7) are
removed, leaving you with the following list:
(8, 13, 17, 23, 0, 92)
You should throw an IllegalArgumentException if either of the positions is
negative. Otherwise you may assume that the positions represent a legal
range of the list (0 <= low <= high < size of 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.
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 rearrange data fields to solve
this problem. You must solve it by rearranging the links of the list.
Write your solution to removeRange below.
]]>