<![CDATA[
CSE143 Final
Autumn 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. You do not have to include any import statements. Do not
abbreviate any code that you write (e.g., S.o.p versus System.out.print).
You are not allowed to use a calculator or other electronic device while
working on this exam.
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.
+---+
| 8 |
+---+
/ \
/ \
+---+ +---+
| 7 | | 5 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 2 | | 1 | | 0 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 4 | | 9 | | 3 | | 6 |
+---+ +---+ +---+ +---+
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: Monday, Tuesday, Wednesday,
Thursday, Friday, Saturday, Sunday. Assume the search tree uses
alphabetical ordering to compare words.
3. Binary Trees, 10 points. Write a method printLeaves that prints to
System.out the leaves of a binary tree from right to left. More
specifically, the leaves should be printed in the reverse order that they
would be printed using any of the standard traversals. For example, if a
variable t stores a reference to the following tree:
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 8 | | 1 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 0 | | 7 | | 6 |
+---+ +---+ +---+
/ \
/ \
+---+ +---+
| 4 | | 9 |
+---+ +---+
/ \
/ \
+---+ +---+
| 3 | | 5 |
+---+ +---+
then the call:
t.printLeaves();
should produce the following output:
leaves: 9 5 3 0
You must exactly reproduce the format above for a nonempty tree. If the
tree is empty, your method should produce the output "no leaves". Your
method should always produce exactly one line of output.
Assume that 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.
Space is provided on the next page for your answer.
Write your solution to printLeaves below.
4. Programming with inheritance, 20 points. You have been asked to extend a
Java class that controls a network router so that it can be used to perform
experiments. Routers are asked to transmit a series of data objects known
as packets. Sometimes the router is unable to transmit the packet, which is
known as dropping a packet. Assume that a class called Router has been
defined with the following public methods:
public Router(NetworkData d) constructs a Router for given network
public boolean route(Packet p) attempts to route given packet; returns
true if packet successfully transmitted
public int dropped() total number of packets dropped
public int packetCount() total number of packets submitted
Any given packet has some data that is being routed from a source to a
destination, each of which has an IP address. Assume that the Packet class
has the following public methods:
public String getData() returns data for this packet
public String getSource() returns IP address of source
public String getDestination() returns IP address of destination
You are to define a new class called TestableRouter that can be used to
test the rate at which packets are getting through from a particular
source. A TestableRouter object should behave just like a Router except
that it should have the following additional public methods:
public void test(String source) begin an experiment for given source
public boolean rateAvailable() returns true if experiment is complete
public double getRate() return the rate of successful
transmission as a percent (0 to 100)
When the test method is called, your router should begin gathering data for
the experiment. The experiment involves following the next 1000 packets
from that particular source to determine the success rate (the percent of
packets that were successfully transmitted). Notice that packets might come
in from other sources while the experiment is in progress. The
rateAvailable method indicates whether or not the experiment is complete.
Once the experiment is complete, a client should be able to call the getRate
method to get the result of the most recent experiment. The rateAvailable
method should return false if the router is in the middle of an experiment
or if it hasn't run any experiments. The getRate method should throw an
IllegalStateException if no rate is available.
Space is provided on the next page for your answer.
Write your solution to TestableRouter below.
5. Comparable class, 20 points. Define a class Location that can be used
to store information about global locations. For each location, you must
keep track of its name (a string), its latitude (a real), and its longitude
(a real). Your class must have the following public methods:
Location(name, longitude, latitude) constructs a location with given
name, longitude and latitude
getName() returns the name
getLongitude() returns the longitude
getLatitude() returns the latitude
toString() returns a String representation of
the location
Longitudes are expressed relative to the equator with negative longitudes
considered to be in the southern hemisphere and positive longitudes
considered to be in the northern hemisphere. Thus, 0 represents the
equator, -90 represents the South Pole and 90 represents the North Pole.
Latitudes are expressed relative to what is known as the prime meridian (the
line of latitude that runs through Greenwich, England), with positive
latitudes considered to be in the western hemisphere and negative latitudes
considered to be in the eastern hemisphere. Latitudes can range from -180
to 180.
The toString method should return a String composed of the location name
followed by the longitude and latitude. Longitude is expressed as a
positive number followed by either the letter N or S to indicate whether it
is in the northern or southern hemisphere. Latitude is expressed as a
positive number followed by either the letter W or E to indicate whether it
is in the western or eastern hemisphere. For example, we might construct
two locations as follows:
Location loc1 = new Location("Seattle", 47.65, 122.3);
Location loc2 = new Location("Sydney", -34.1, -151.1);
The toString method should return "Seattle 47.65N 122.3W" for loc1 and
should return "Sydney 34.1S 151.1E" for loc2. You must exactly reproduce
the format of these examples. You may adopt any convention you like in
terms of north/south and east/west for the ambiguous cases (0 longitude, 0
latitude, 180 latitude, -180 latitude).
Your class should implement the Comparable<E> interface. Locations should
be ordered first by longitude with locations closer to the equator
considered less than locations farther from the equator. When the
longitudes are equal, you should examine latitudes with locations closer to
the prime meridian considered less than locations farther from the prime
meridian.
You may assume that your constructor is passed legal values for latitude and
longitude. You are allowed to use the Math.abs method to find the absolute
value of a number.
Space is provided on the next page for your answer.
Write your solution to Location below.
6. Binary Trees, 20 points. Write a method countNodes that takes two integers
x and y as parameters and that returns a count of the number of nodes whose
path from the root includes exactly x left links and exactly y right links
(order is unimportant). For example, if a variable called t refers to the
following tree:
+----+
| 73 |
+----+
/ \
/ \
+----+ +----+
| 19 | | 42 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| -7 | | 13 | | 68 | | 95 |
+----+ +----+ +----+ +----+
\ / /
\ / /
+----+ +----+ +----+
| 50 | | 36 | | 17 |
+----+ +----+ +----+
The call t.countNodes(1, 1) requests a count of the number of nodes that are
1 left link and 1 right link from the root. It should return 2 because
there are two such nodes: the node that stores 13 and the node that stores
68. Notice that the order of the links is unimportant.
If you request t.countNodes(2, 1), the method should return 2 because there
are two such nodes: the node that stores 50 (path is left/left/right) and
the node that stores 36 (path is right/left/left). Again, the order of the
links is unimportant as long as the path from the root includes the correct
number of left and right links.
The call t.countNodes(0, 0) would return 1 for this tree because there is
exactly one node that is 0 left links and 0 right links from the root (the
root itself).
Your method should throw an IllegalArgumentException if either value passed
to it is less than 0. Your method also must be reasonably efficient in that
it should not explore deep into the tree if it doesn't have to.
Assume that 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>
}
(continued on next page)
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. 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).
Write your solution to countNodes below.
7. Linked Lists, 20 points. Write a method interleave that combines elements
from two lists in an alternating fashion to form a single list. For
example, suppose the the variables list1 and list2 refer to lists that
contain the following values:
list1: (1, 8, 3, 9)
list2: (2, 12, 6, 14)
If the following call is made:
list1.interleave(list2);
The method should move values from list2 into list1 so that list1 contains
the combined list in alternating order (1st value of list1, followed by 1st
value of list2, followed by 2nd value of list1, followed by 2nd value of
list2, etc):
list1: (1, 2, 8, 12, 3, 6, 9, 14)
list2: ()
Notice that list2 is empty after the call. If the call instead had been:
list2.interleave(list1);
The method would have moved the elements of list1 into list2:
list1: ()
list2: (2, 1, 12, 8, 6, 3, 14, 9)
One list might be longer than the other, in which case any extra values from
the longer list should simply be appended at the end of the result. For
example, given the following lists:
list1: (1, 8, 3, 9)
list2: (82, 7, 4, 2, 1, 6, 5, 0, 18)
The call:
list1.interleave(list2);
should produce the following result:
list1: (1, 82, 8, 7, 3, 4, 9, 2, 1, 6, 5, 0, 18)
list2: ()
Notice that the first four values of the two lists have been interleaved
and the excess values from the second list (1, 6, 5, 0, 18) have been
included at the end of the result. If the call had instead been:
list2.interleave(list1);
The result would be:
list1: ()
list2: (82, 1, 7, 8, 4, 3, 2, 9, 1, 6, 5, 0, 18)
Again, the two lists have been interleaved with the excess values appearing
at the end of the result.
(continued on next page)
Assume that you 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 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).
Write your solution to interleave 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