<![CDATA[
CSE143 Sample Final handout #14
Fall 2009
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 2 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 7 | | 9 | | 5 |
+---+ +---+ +---+
/ \ / /
/ \ / /
+---+ +---+ +---+ +---+
| 4 | | 6 | | 1 | | 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: Kenny, Stan, Cartman, Kyle,
Tweek, Wendy, Timmy. Assume the search tree uses alphabetical ordering to
compare words.
3. Binary Trees, 10 points. Write a method countMultiples that returns a count
of the number of multiples of a particular value in a binary tree of
integers. Given a number n, a value m is considered a multiple of n if it
can be expressed as (k * n) for some integer k. For example, suppose that a
variable t stores a reference to the following tree:
+---+
| 6 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 9 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 5 | | 3 | | 4 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 8 | | 6 | | 7 | | 0 |
+---+ +---+ +---+ +---+
The table below shows various calls and the values returned.
method call returns explanation
-------------------------------------------------------------------
t.countMultiples(2) 6 six multiples of 2: 6, 2, 4, 8, 6, 0
t.countMultiples(4) 3 three multiples of 4: 4, 8, 0
t.countMultiples(3) 5 five multiples of 3: 6, 9, 3, 6, 0
t.countMultiples(1) 10 all ten numbers are multiples of 1
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 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 call any other methods of the class.
Your method should throw an IllegalArgumentException if passed the value 0.
4. Programming with inheritance, 20 points. You have been asked to extend the
ArrayIntList class that we have been studying. Recall that it has a
constant called DEFAULT_CAPACITY and includes the following public methods:
public ArrayIntList() constructs an empty list with
capacity equal to DEFAULT_CAPACITY
public ArrayIntList(int capacity) constructs an empty list of given
capacity
public void add(int value) adds given value at end of list
public void add(int index, int value) adds given value at given index
public void remove(int index) removes value at given index
public int size() returns current number of elements
public boolean isEmpty() returns whether list is empty
public String toString() returns a comma-separated version
of the list in square brackets
You are to define a new class called HistoryList that extends this
class through inheritance. It should behave just like an ArrayIntList
except that it should keep track of the modification history of the list.
In particular, a HistoryList object should keep track of a sequence of
String values that indicate how the object was modified. For example, if
the following operations are performed:
HistoryList list = new HistoryList();
list.add(18);
list.add (27);
list.add(0, 17);
list.remove(0);
list.add(9);
Then the HistoryList object should keep track of this sequence of Strings:
initial list = []
add(18), list = [18]
add(27), list = [18, 27]
add(0, 17), list = [17, 18, 27]
remove(0), list = [18, 27]
add(9), list = [18, 27, 9]
When a HistoryList is constructed, the first String in the list above should
be added to its history. Then, each time the remove method is called or
either of the add methods is called, a new entry is added to the history
showing the call that is being made and the value of the list after the
call. You must exactly reproduce the format shown above.
These Strings that are part of the history will be accessed by clients using
the following new public methods:
public int historySize() Returns the number of Strings in the
history
public String history(int index) Returns the given history String (0
for the first, 1 for the second, etc)
In the example above, after executing the sample code, the history size will
be 6 and the six different history Strings can be accessed by calls on
list.history passing indexes between 0 and 5. For example, to print all
strings in the history, the client might say:
for (int i = 0; i < list.historySize(); i++)
System.out.println(list.history(i));
5. Comparable class, 20 points. Define a class ClockTime that stores
information about time of day using a standard clock. Each ClockTime
object keeps track of hours, minutes, and a String to indicate "am" or
"pm". It has the following public methods:
ClockTime(hours, minutes, amPm) constructs a ClockTime with given
hours, minutes and amPm setting
getHours() returns the hours
getMinutes() returns the minutes
getAmPm() returns the am/pm setting
toString() returns a String representation of
the time
Assume that the values passed to your constructor are legal. In particular,
hours will be between 1 and 12 inclusive, minutes will be between 0 and 59
inclusive, and the am/pm parameter will be either the String "am" or the
String "pm". These values should be returned by the various "get" methods.
The toString method should return a String composed of the hours followed by
a colon followed by the minutes (2 digits) followed by a space followed by
the am/pm String. For example, given these declarations:
ClockTime time1 = new ClockTime(8, 31, "am");
ClockTime time2 = new ClockTime(12, 7, "pm");
time1.toString() should return "8:31 am" and time2.toString() should return
"12:07 pm". You must exactly reproduce the format of these examples.
Your class should implement the Comparable<E> interface. The earliest time
is 12:00 am and the latest time is 11:59 pm. In between the time increases
as it would in a standard clock. Keep in mind that 12:59 am is followed by
1:00 am, that 11:59 am is followed by 12:00 pm, and that 12:59 pm is
followed by 1:00 pm.
6. Binary Trees, 20 points. Write a method matches that returns a count of the
number of nodes in one tree that match nodes in another tree. A match is
defined as a pair of nodes that are in the same position in the two trees
relative to their overall root and that store the same data. Consider, for
example, the following trees.
+---+ | +---+
tree1-> | 3 | | tree2-> | 3 |
+---+ | +---+
/ \ | / \
/ \ | / \
+---+ +---+ | +---+ +---+
| 4 | | 7 | | | 6 | | 7 |
+---+ +---+ | +---+ +---+
/ \ \ | / / \
/ \ \ | / / \
+---+ +---+ +---+ | +---+ +---+ +---+
| 0 | | 9 | | 2 | | | 0 | | 9 | | 2 |
+---+ +---+ +---+ | +---+ +---+ +---+
\ | \
\ | \
+---+ | +---+
| 8 | | | 8 |
+---+ | +---+
The overall root of the two trees match (both are 3). The nodes at the top
of the left subtrees of the overall root do not match (one is 4 and one is
6). The top of the right subtrees of the overall root match (both are 7).
The next level of the tree has 2 matches for the nodes storing 0 and 2
(there are two nodes that each store 9 at this level, but they are in
different positions relative to the overall root of the tree). The nodes at
the lowest level both store 8, but they aren't a match because they are in
different positions. Therefore, these two trees have a total of 4 matches.
Thus, tree1.matches(tree2) and tree2.matches(tree1) would each return 4.
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 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 call any other methods of the class.
7. Linked Lists, 20 points. Write a method removeFrom that efficiently removes
from a sorted list of integers all values appearing in a second sorted list
of integers. For example, suppose that variables list1 and list2 refer to
the following lists:
list1: [1, 3, 5, 7]
list2: [1, 2, 3, 4, 5]
If the following call is made:
list1.removeFrom(list2);
then the lists should store the following values after the call:
list1: [7]
list2: [1, 2, 3, 4, 5]
Notice that all of the values from list1 that appear in list2 have been
removed and that list2 is unchanged. If the call instead had been:
list2.removeFrom(list1);
then the lists would have these values afterwards:
list1: [1, 3, 5, 7]
list2: [2, 4]
Both lists are guaranteed to be in sorted nondecreasing) order, although
there might be duplicates in either list. Because the lists are sorted, you
can solve this problem very efficiently with a single pass through the data.
Your solution is required to run in O(m + n) time where m and n are the
lengths of the two lists.
Assume that you are using a linked list that stores integers, as discussed
in lecture:
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 methods of the class to solve this problem, 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.
]]>