<![CDATA[
CSE143 Final
Autumn 2007
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, to use generics properly, and to declare variables and
parameters using interfaces when possible. 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.
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 6 | | 5 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 3 | | 0 | | 9 |
+---+ +---+ +---+
\ / \ \
\ / \ \
+---+ +---+ +---+ +---+
| 8 | | 2 | | 1 | | 4 |
+---+ +---+ +---+ +---+
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: Grammar, Logic, Rhetoric,
Geometry, Arithmetic, Music, Astronomy. Assume the search tree uses
alphabetical ordering to compare words.
3. Binary Trees, 10 points. Write a method inorderList that returns a list
containing the sequence of values obtained from an inorder traversal of a
binary tree of integers. For example, if a variable t stores a reference to
the following tree:
+---+
| 7 |
+---+
/ \
/ \
+---+ +---+
| 4 | | 2 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 9 | | 5 | | 0 |
+---+ +---+ +---+
then the call t.inorderList() should return the following list:
[9, 4, 7, 5, 2, 0]
Your method should construct an ArrayList<Integer> to return although the
return type should be List<Integer>. If the tree is empty, your method
should return an empty list.
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.
Write your solution to inorderList below.
4. Programming with inheritance, 20 points. You have been asked to extend a
Java class called SearchTool that is used to connect to a search engine like
Google or Yahoo. The SearchTool class has the following public methods:
public SearchTool(String engine) constructs a SearchTool object
for the given search engine
public List<String> search(String query) returns a list of results for
the given query
public int searchCount() returns the total number of
calls made to search
public String baseURL() returns the base URL of the
search engine
public Image icon() returns a graphical icon for
the search engine
Notice that a search tool is associated with a particular search engine that
is specified in the constructor. This class works correctly, but doesn't
keep track of any statistics about the user's search behavior other than a
count of the total number of searches made.
You are to define a new class called ExtendedSearchTool that extends this
class through inheritance. It should behave just like a SearchTool object
except that it should keep track of the average number of results returned
by calls on search and the distribution (as a percent) of queries by the
length of the query string. It should include the following new methods:
public double averageResultLength() returns the average number of
results obtained by calls on search
(0 if no calls have been made)
public double percent(int length) returns the percent of calls on
search that have been for strings of
the given length (0 if no calls have
been made)
Most queries are fairly short, so your class should consider queries of
length 25 or more to all be of length 25. You may assume that the value
passed to the percent method is between 0 and 25 inclusive. Write your
solution to ExtendedSearchTool below.
5. Comparable class, 20 points. Define a class MapLocation that stores
information about a point of interest on a map. Each MapLocation object
keeps track of a grid location (row and column) and a name. The MapLocation
class has the following public methods:
MapLocation(row, column, name) constructs a MapLocation object with
given location and name
getCoordinates() returns the map coordinates as a String
getName() returns the name of this MapLocation
toString() returns a String representation of the
MapLocation
Rows will be specified by character values in the range of A to Z inclusive
and column locations will be specified as integers greater than 0, as in:
MapLocation loc = new MapLocation('B', 8, "arboretum");
The MapLocation constructor should throw an IllegalArgumentException if the
row or column are illegal. The getCoordinates method should combine the row
and the column into a single String ("B8" in the example above). The
toString method should return a string composed of the name followed by the
coordinates in parentheses ("arboretum (B8)" in the example above).
Your class should implement the Comparable<E> interface. MapLocation
objects should be ordered first by increasing row and then by increasing
column and then alphabetically by name.
Write your solution to MapLocation below.
6. Binary Trees, 20 points. Write a method tighten that eliminates branch
nodes that have only one child from a binary tree of integers. For example,
if a variable called t stores a reference to the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 28 | | 19 |
+----+ +----+
/ /
/ /
+----+ +----+
| 94 | | 32 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 65 | | -8 | | 72 |
+----+ +----+ +----+
\ / \
\ / \
+----+ +----+ +----+
| 10 | | 42 | | 50 |
+----+ +----+ +----+
then the call:
t.tighten();
should leave t storing the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 94 | | 72 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 65 | | 10 | | 42 | | 50 |
+----+ +----+ +----+ +----+
Notice that the nodes that stored the values 28, 19, 32, and -8 have all
been eliminated from the tree because each had one child. When a node is
removed, it is replaced by its child. Notice that this can lead to multiple
replacements because the child might itself be replaced (as in the case of
19 which is replaced by its child 32 which is replaced by its child 72).
<continued on next page>
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. 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 tighten below.
7. Linked Lists, 20 points. Write a method removeDuplicates that removes any
duplicates from a list of integers. The resulting list should have the
values in the same relative order as their first occurrence in the original
list. In other words, a value i should appear before a value j in the final
list if and only if the first occurrence of i appears before the first
occurrence of j in the original list. For example, if a variable called
list stores the following list:
[14, 8, 14, 12, 1, 14, 11, 8, 8, 10, 4, 9, 1, 2, 5, 2, 4, 12, 12]
and the following call is made:
list.removeDuplicates();
then list should store these values after the call:
[14, 8, 12, 1, 11, 10, 4, 9, 2, 5]
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.
Write your solution to removeDuplicates 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