<![CDATA[
CSE143 Final
Winter 2006
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
This is an open-book/open-note exam. Space is provided for your answers. Use
the backs of pages if necessary. The exam is divided into eight questions with
the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Binary Tree Traversal 6 _____
2 Binary Search Tree 4 _____
3 Binary Trees 10 _____
4 Programming with Inheritance 20 _____
5 Comparable class 20 _____
6 Binary Trees 20 _____
7 Linked Lists 20 _____
8 Art (bonus) 1 _____
----------------------------------
Total 100 _____
In general the exam is not graded on style and you do not need to include
comments, although you are required to declare all data fields and helper
methods as private.
Do not begin work on this exam until instructed to do so. Any student who
starts early or who continues to work after time is called will receive a 10
point penalty.
If you finish the exam early, please hand your exam to the instructor and exit
quietly through the front door.
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 0 | | 3 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 5 | | 7 | | 4 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 1 | | 6 | | 9 | | 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: Pride, Envy, Greed, Lust,
Gluttony, Anger, Sloth.
3. Binary Trees, 10 points. Write a method printLevel that takes an integer n
as a parameter and that prints the values at level n from left to right.
The values should be printed to System.out, one per line. We will use the
convention that the overall root is at level 1, that it's children are at
level 2, and so on.
For example, if a variable t stores a reference to the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 19 | | 93 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 11 | | 14 | | 15 |
+----+ +----+ +----+
/
/
+----+
| 10 |
+----+
then the call:
t.printLevel(3);
would produce the output:
11
14
15
If there are no values at the level, your method should produce no output.
Your method should throw an IllegalArgumentException if passed a value for
level that is less than 1.
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 overallRoot; // 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.
Space is provided on the next page for your answer.
Write your solution to printLevel below.
4. Programming with inheritance, 20 points. A company has developed a class
called PhoneList that it uses for keeping track of phone calls. They have
found that they need data about which area codes are being used for calls.
A class called PhoneCall keeps track of where the call came from and where
it went to. It has the following public methods:
public int fromAreaCode() returns the area code of the caller
public String fromNumber() returns the phone number of the caller
public int toAreaCode() returns the area code of the person called
public String toNumber() returns the phone number of the person called
The PhoneList class has the following public methods:
public PhoneList(ArchiveData archive) constructs a phone list from the
given archive data
public void add(PhoneCall call) appends the given call to the end
of the list
public int size() returns the current list size
public PhoneCall get(int index) returns the call with given index
public String toString() returns a string representation
of the list
public ArchiveData makeArchive() returns an archive of the list
The company would like to create a new class called TallyPhoneList that
extends this functionality to include the following public methods:
public getFromCount(int area) returns a count of calls made from the
given area code
public getToCount(int area) returns a count of calls made to the
given area code
public int getTotalFrom() returns the total number of different
area codes that calls were made from
public int getTotalTo() returns the total number of different
area codes that calls were made to
The first pair of methods indicate the total number of calls for a given
area code (e.g., recording that 85 calls were made from area code 206 and
that 29 calls were made to area code 212). The second pair of methods keep
track of how many different area codes were involved (e.g., that calls were
made from 5 different area codes and that those calls went to 18 different
area codes). These four operations are required to run in O(1) time. You
may assume that all area codes are 3 digit numbers.
The company is interested in tallying only recent calls. As a result, these
four methods should consider only calls that have been made since the last
archive (i.e., since the list was constructed).
You are to write a class called TallyPhoneList that can be used in place of
PhoneList to provide this additional functionality. Your class can create
whatever data structures it needs to solve the problem (e.g., arrays,
ArrayLists, Maps, etc).
Space is provided on the next page for your answer.
Write your solution to TallyPhoneList below.
5. Comparable class, 20 points. Define a class RadioStation that can be used
to store information about radio stations. For each station, you must keep
track of its name (a string), its broadcast band (a string) and its station
number (a real number). For example, there is a local station called KUOW
that is an FM station broadcast on 94.9. Your class must have the following
public methods:
RadioStation(name, band, number) constructs a radio station with
given name, band and station number
getName() returns the name
getBand() returns the band
getNumber() returns the number
toString() returns a String representation of
the radio station
simulcast(other) records the fact that this station
and the other are simulcasts
The broadcast band can be any arbitrary string. For example, it might be
"AM" versus "FM" or might include subdivisions like "FM 1" and "FM 2" or
might include other text like "XM" for satellite radio.
The toString method should return a String composed of the station name
followed by the band followed by the station number. For example, if you
were to construct the following station:
RadioStation station = new RadioStation("KKNW", "AM", 1150.0);
then a call on station.toString() should return "KKNW AM 1150.0".
The simulcast method is used to record a relationship between two stations
that are broadcasting the same material, as in:
RadioStation station1 = new RadioStation("KUOW", "FM", 94.9);
RadioStation station2 = new RadioStation("KUOW", "AM", 1340);
station1.simulcast(station2);
The call on simulcast indicates a link between the two stations. The link
goes in both directions, so it shouldn't matter whether you make the call
above or if you instead make the following call:
station2.simulcast(station1);
A given station will have at most one simulcast relationship. When such a
relationship exists, it should be included in the result of toString. Given
the calls above, the call station1.toString() should return:
KUOW FM 94.9 (simulcast on AM 1340.0)
and the call station2.toString() should return:
KUOW AM 1340.0 (simulcast on FM 94.9)
Notice that the simulcast notation appears in parentheses and that we
include just the band and station number. You are to exactly reproduce this
format.
Your class should implement the Comparable<E> interface. Radio stations
should be grouped together by band (e.g., AM stations grouped together and
FM stations grouped together). Within a given band, the stations should be
sorted by station number (e.g., FM 94.9 less than FM 96.5).
Space is provided on the next page for your answer.
Please write your solution to RadioStation below.
6. Binary Trees, 20 points. Write a method completeToLevel that takes an
integer n as a parameter and that adds nodes to a binary tree so that the
first n levels are complete. A level is considered complete if it has every
possible node at that level. We will use the convention that the overall
root is at level 1, that it's children are at level 2, and so on. You
should preserve any existing nodes in the tree. Any new nodes added to the
tree should have -1 as their data.
For example, if a variable called t refers to the following tree:
+----+
| 17 |
+----+
/ \
/ \
+----+ +----+
| 83 | | 6 |
+----+ +----+
/ \
/ \
+----+ +----+
| 19 | | 87 |
+----+ +----+
\ /
\ /
+----+ +----+
| 48 | | 75 |
+----+ +----+
and you make the following call:
t.completeToLevel(3);
Then t should store the following tree after the call is made:
+----+
| 17 |
+----+
/ \
/ \
+----+ +----+
| 83 | | 6 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 19 | | -1 | | -1 | | 87 |
+----+ +----+ +----+ +----+
\ /
\ /
+----+ +----+
| 48 | | 75 |
+----+ +----+
In this case, the request was to fill in nodes as necessary to ensure that
the first 3 levels are complete. There were two nodes missing at level 3.
Notice that level 4 of this tree is not complete because the call requested
that nodes be filled in to level 3 only.
Your method should throw an IllegalArgumentException if passed a value for
level that is less than 1.
(continued on next page)
Your method might need to fill in several different levels. For example, if
t stores an empty tree and the same call is made then it should store the
following afterwards:
+----+
| -1 |
+----+
/ \
/ \
+----+ +----+
| -1 | | -1 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| -1 | | -1 | | -1 | | -1 |
+----+ +----+ +----+ +----+
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 overallRoot; // 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 completeToLevel below.
7. Linked Lists, 20 points. Write a method doubleList that doubles the size of
a list by appending a copy of the original sequence to the end of the list.
For example, if a variable called list stores this sequence of values:
(1, 3, 2, 7)
and we make the following call:
list.doubleList();
then it should store the following values after the call:
(1, 3, 2, 7, 1, 3, 2, 7)
Notice that it has been doubled in size by having the original sequence
appearing two times in a row.
You may not make assumptions about how many elements are in the list.
Assume that we are using a linked list that stores integers, as discussed in
lecture (handouts 7 and 8).
public class ListNode {
public int data; // data stored in this node
public ListNode next; // link to next node in the list
public ListNode() {
this(0, null);
}
public ListNode(int data) {
this(data, null);
}
public ListNode(int data, ListNode next) {
this.data = data;
this.next = next;
}
}
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. If the
original list contains n nodes, then you should construct exactly n nodes to
be added to the list. You may not use any auxiliary data structures to
solve this problem (no array, ArrayList, stack, queue, String, etc). Your
method should run in O(n) time where n is the number of nodes in the list.
Write your solution to doubleList below.
8. Art, 1 point (bonus). Give an artistic rendering of your TA. You may
either write a poem or draw a picture. If your answer below indicates at
least 1 minute of effort, you will receive full credit, although your TA
would probably appreciate it if you put in a little more effort.
]]>
Stuart Reges
Last modified: Fri Sep 16 16:16:07 PDT 2011