<![CDATA[
CSE143 Final
Spring 2008
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.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 4 | | 7 |
+---+ +---+
/ \
/ \
+---+ +---+
| 9 | | 6 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 2 | | 1 | | 5 |
+---+ +---+ +---+
/ \
/ \
+---+ +---+
| 8 | | 3 |
+---+ +---+
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: Lisa, Bart, Marge, Homer, Maggie,
Flanders, Smithers. Assume the search tree uses alphabetical ordering to
compare words.
3. Binary Trees, 10 points. Write a method equals that compares two binary
trees of integers to see if they are equal to each other (i.e., if they have
the same structure and store the same values). For example, if two
variables of type IntTree called t1 and t2 have been initialized, then the
call:
t1.equals(t2)
will return true if the trees are equal and will return false otherwise.
Two trees are considered equal if each node in either tree has a
corresponding node in the other tree in the same location relative to the
root and storing the same value. If both trees are empty, they are
considered equal.
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 not change
either of the two trees it is comparing for equality.
Write your solution to equals below.
4. Programming with inheritance, 20 points. You have been asked to extend a
Java class called SongList that is used to associate song titles with MP3
objects (a digital recording of the song). The SongList class has the
following public methods:
public SongList(UserData data) constructs a song list from data
public MP3 get(String name) returns the MP3 for this song name
public void put(String name, MP3 mp) records the association of this
song name with this MP3 object
public boolean contains(String name) returns if this song is in list
public int size() returns size of list
public boolean isEmpty() returns if this list is empty
The class works correctly, but we want to add functionality for keeping
track of recently accessed songs. The get method is slow because it has to
read the song information from a file to construct an appropriate MP3
object. It would be helpful to keep track of the most recently accessed
songs (this is often referred to as a "cache"). The MP3 objects take up a
lot of space in memory, so you should keep track of at most 10 such songs.
You are to define a new class called CachedSongList that extends through
inheritance the SongList class so that it has the same functionality
described above and so that it stores the most recently referenced song
titles by calls on get (up to 10 different songs). It should keep track of
the corresponding MP3 objects for these song titles so that it can return
them without calling the superclass get method. It should never store more
than 10 song titles and their MP3 objects. It should also provide the
following public methods:
public int recentSize() Returns the number of distinct
songs in the cache
public String getRecent(int index) Returns the name of the most
recently played songs (0 for most
recent, 1 for 2nd most recent, etc)
A song might be accessed multiple times, but getRecent should return it just
once. For example, if a song is played four times in a row, then its name
should be returned by a call on getRecent(0), but not by a call on
getRecent(1). The call on getRecent(1) should return the song most recently
accessed before the other song. As another example, suppose that you
construct a CachedSongList and make twenty calls on get that mention only
three different songs (because the same songs are being accessed over and
over again). In that case, the recent size should be 3 and the getRecent
method should return them in the order in which they were most recently
accessed. Similarly, you might construct a CachedSongList and make 350
calls on get that access only 10 different songs. All 10 of those songs and
their corresponding MP3 objects should be stored in the cache until some new
song (an eleventh song) is accessed through get, in which case it goes to
the top of the list of the most recent songs and one of the previous ten is
removed, so that you are always keeping track of the ten distinct songs most
recently referred to by a call on get.
Write your solution to CachedSongList on the next page.
Write your solution to CachedSongList below.
5. Comparable class, 20 points. Define a class ItemOrder that stores
information about an item being ordered. Each ItemOrder object keeps track
of its item number (a string), an integer quantity, and a price per item
expressed as an integer number of pennies. For example:
ItemOrder item1 = new ItemOrder("007", 3, 36);
The quantity is passed as a parameter before the price in the constructor,
so this indicates an order for item number 007 with a quantity of 3 at 36
cents each. The total price for this order would be 108 cents. An
ItemOrder can also store an optional note (a string) that appears in the
constructor after the item number, as in:
ItemOrder item2 = new ItemOrder("182", "red", 2, 1895);
This indicates an order for item number 182 with the note "red" and with a
quantity of 2 at 1895 cents per item. In addition to these two
constructors, the class should include the following public methods:
getItem() returns the item number for this item (without optional note)
getPrice() returns the total price for this order in pennies
toString() returns a String representation of the order
Listed below are patterns for formatting the toString result--the first
for items with no optional text, the second for orders with optional text.
item #<item>: <quantity>@$<price per> = $<total price>
item #<item> (<note>): <quantity>@$<price per> = $<total price>
For example, given the two variables defined above, item1.toString() should
return "item #007: 3@$0.36 = $1.08" and item2.toString() should return
"item #182 (red): 2@$18.95 = $37.90". Notice that prices are expressed as
dollars and cents in the usual format with 2 digits for pennies.
Your class should also implement the Comparable interface. Items should be
ordered first by item number (sorted alphabetically) and then by total price
(sorted in reverse order with highest price first, lowest price last).
6. Binary Trees, 20 points. Write a method combineWith that constructs a
binary tree of integers by combining two other trees. The combined tree
should have each of the nodes that appears in either of the two trees. The
nodes of the new tree should store an integer indicating which of the
original trees had a node at that position (1 if just the first tree had the
node, 2 if just the second tree had the node, 3 if both trees had the node).
Consider, for example, the following trees.
+---+ | +---+
t1-> | 9 | | t2-> | 0 |
+---+ | +---+
/ \ | / \
/ \ | / \
+---+ +---+ | +---+ +---+
| 6 | | 14| | | -3| | 8 |
+---+ +---+ | +---+ +---+
/ \ \ | / / \
/ \ \ | / / \
+---+ +---+ +---+ | +---+ +---+ +---+
| 9 | | 2 | | 11| | | 8 | | 5 | | 6 |
+---+ +---+ +---+ | +---+ +---+ +---+
/ | \
/ | \
+---+ | +---+
| 4 | | | 1 |
+---+ | +---+
Suppose the following call is made:
IntTree t3 = t1.combineWith(t2);
The variable t3 will refer to the following tree:
+---+
t3-> | 3 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 3 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 1 | | 2 | | 3 |
+---+ +---+ +---+ +---+
/ \
/ \
+---+ +---+
| 1 | | 2 |
+---+ +---+
Notice that the two nodes in t1 that have no corresponding nodes in t2 (the
nodes storing 2 and 4) store the value 1 in the newly constructed tree while
the two nodes in t2 that have no corresponding nodes in t1 (the nodes
storing 5 and 1) store the value 2 in the newly constructed tree. All other
nodes store the value 3 to indicate that they appeared in both of the
original trees.
<continued on next page>
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
// post: constructs a leaf node with given data
public IntTreeNode(int data) {
this(data, null, null);
}
// post: constructs a branch node with the given data and links
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}
public class IntTree {
private IntTreeNode overallRoot;
// post: constructs an empty tree
public IntTree() {
overallRoot = null;
}
<other 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 other than the constructor. You
will need to construct IntTreeNode objects to construct the new tree, but
you should not change either of the two original trees.
Write your solution to method combineWith below.
7. Linked Lists, 20 points. Write a method reorder that rearranges a list of
integers into sorted (nondecreasing) order assuming that the list is already
sorted by absolute value. For example, suppose that a variable called list
stores the following sequence of values:
[0, -3, 3, -5, 7, -9, -10, 10, -11, -11, -11, 12, -13]
Notice that the values appear in sorted order if you ignore the sign of the
numbers. The following call:
list.reorder();
should reorder the values so that the list stores this sequence of values:
[-13, -11, -11, -11, -10, -9, -5, -3, 0, 3, 7, 10, 12]
Notice that the values now appear in sorted order (including sign).
Because the list is sorted by absolute value, you can solve this problem
very efficiently. Your solution is required to run in O(n) time where n is
the length of the list. 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.
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