CSE143 Sample Final handout #33
Spring 2008
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
}
public class IntTree {
private IntTreeNode overallRoot;
}
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 TimeSpan that stores
information about a period of time based on a 24-hour clock. Each TimeSpan
object keeps track of a starting time and a duration (e.g., starting at 1:30
and lasting 140 minutes). The class has the following public methods:
TimeSpan(hour, min, duration) constructs a TimeSpan object with the
given starting time and duration
getStart() returns the starting time as a String
getStop() returns the stopping time as a String
toString() returns a String composed of the starting
time followed by a dash followed by the
stopping time
Times should be reported in standard 24-hour clock format with hours between
0 and 23 and minutes between 0 and 59. The earliest time will be expressed
as 0 hours and 0 minutes (0:00), which represents midnight. The latest time
will be expressed as 23 hours and 59 minutes (23:59), which represents one
minute before midnight. For example, given the following:
TimeSpan span = new TimeSpan(23, 5, 75);
The call span.getStart() would return "23:05", the call span.getStop() would
return "0:20" and the call span.toString() would return "23:05-0:20".
Notice that minutes are always indicated with two digits and that it is
possible for a stopping time to cross midnight.
The TimeSpan constructor should throw an IllegalArgumentException if passed
an illegal value (hour not 0 to 23, minutes not 0 to 59, negative duration).
TimeSpan should implement the Comparable interface, with TimeSpan objects
ordered first by increasing start time and then by increasing duration.
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
}
public class IntTree {
private IntTreeNode overallRoot;
}
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
}
public class LinkedIntList {
private ListNode front;
}
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.