<![CDATA[
CSE143 Final
Spring 2013
Name of Student_______________________________________________________________
Section (e.g., AA)___________________ TA_____________________________________
The exam is divided into ten questions with the following points:
# Problem Area Points Score
-----------------------------------------------------
1 Binary Tree Traversal 6 _____
2 Binary Search Tree 4 _____
3 Collections Mystery 5 _____
4 Collections Programming 5 _____
5 Binary Trees 10 _____
6 Collections Programming 10 _____
7 Comparable class 20 _____
8 Binary Trees 20 _____
9 Linked Lists 20 _____
10 Fiction (bonus) 1 _____
----------------------------------
Total 100 _____
This is a closed-book/closed-note exam. Space is provided for your answers.
There is a 2-page "cheat sheet" at the end that you can use as scratch paper or
to write answers. You are not allowed to access any other paper during the
exam (not even scratch paper). Use the backs of the pages of this test if
necessary. Anyone caught with extra paper will lose at least 10 points.
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. Anyone caught using an electronic device will receive a
10 point penalty.
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 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 9 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 4 | | 6 | | 0 |
+---+ +---+ +---+ +---+
\ \ /
\ \ /
+---+ +---+ +---+
| 8 | | 1 | | 5 |
+---+ +---+ +---+
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: Karl, Chris, Simon, John, Zoe,
Anton, Zach. Assume the search tree uses alphabetical ordering to compare
words.
3. Collections Mystery, 5 points. Consider the following method:
public void mystery(int[][] data, int pos, int rows, int cols) {
for (int i = 0; i < rows; i++) {
int sum = 0;
for (int j = 0; j < cols; j++) {
sum = sum + data[pos + i][pos + j];
}
System.out.print(sum + " ");
}
System.out.println();
}
Suppose that a variable called grid has been declared as follows:
int[][] grid = {{4, 6, 8, 8, 2, 1}, {7, 4, 8, 8, 7, 7},
{7, 8, 6, 6, 7, 2}, {1, 2, 2, 7, 5, 7},
{8, 3, 6, 6, 1, 1}, {9, 7, 9, 6, 6, 1}};
which means it will store the following 6-by-6 grid of values:
4 6 8 8 2 1
7 4 8 8 7 7
7 8 6 6 7 2
1 2 2 7 5 7
8 3 6 6 1 1
9 7 9 6 6 1
For each call below, indicate what output is produced:
Method Call Output Produced
mystery(grid, 0, 2, 2); _______________________
mystery(grid, 2, 3, 2); _______________________
mystery(grid, 1, 4, 1); _______________________
4. Collections Programming, 5 points. Write a method called retainEvenLength
that takes a set of strings as a parameter and that retains only the strings
of even length from the set, removing all other strings. For example, if a
set called s stores the following values:
[I, Sam, am, and, do, eggs, green, ham, like, not, them]
and the following call is made:
retainEvenLength(s);
then s should store the following values after the call:
[am, do, eggs, like, them]
You may construct iterator objects, but you are not allowed to construct any
structured objects to solve the problem (no set, list, stack, queue, string,
etc).
5. Binary Trees, 10 points. Write a method called hasPathSum that takes an
integer n as a parameter and that returns true if there is some nonempty
path from the overall root of a tree to a node of the tree in which the sum
of the data stored in the nodes adds up to n (returning false if no such
path exists). For example if the variable t refers to the following tree:
+----+
| 5 |
+----+
/ \
+----+ +----+
| 1 | | 21 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| -9 | | 2 | | 20 |
+----+ +----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 3 | | 30 | | 13 | | 4 |
+----+ +----+ +----+ +----+
Below are various calls and an explanation for the value returned:
t.hasPathSum(8) returns true because of the path (5, 1, 2)
t.hasPathSum(26) returns true because of the path (5, 21)
t.hasPathSum(0) returns true because of the path (5, 1, -9, 3)
t.hasPathSum(5) returns true because of the path (5)
t.hasPathSum(1) returns false because no path with that sum exists
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
extra data structures to solve this problem.
6. Collections Programming, 10 points. Write a method called recordDate that
records information about a date between two people. For each person, the
map records an ordered list of people that person has dated. For example,
the map might record these entries for two people
Michael => [Ashley, Samantha, Joshua, Brittany, Amanda, Amanda]
Amanda => [Michael, Daniel, Michael]
The dates are listed in reverse order. The list for Michael indicates that
he most recently dated Ashley and before that Samantha and before that
Joshua, and so on. Notice that he has dated Amanda twice. The list for
Amanda incidates that she most recently dated Michael and before that Daniel
and before that Michael. All names are stored as string values.
The method takes three parameters: the map, the name of the first person,
and the name of the second person. It should record the date for each
person and should return what date number this is (1 for a first date, 2 for
a second date, and so on). Given the entries above, if we make this call:
int n = recordDate(dates, "Michael", "Amanda");
The method would record the new date at the front of each list:
Michael => [Amanda, Ashley, Samantha, Joshua, Brittany, Amanda, Amanda]
Amanda => [Michael, Michael, Daniel, Michael]
The method would return the value 3 indicating that this is the third date
for this pair of people. When someone is first added to the map, you
should construct a LinkedList object (we use LinkedList instead of
ArrayList because it has fast insertion at the front ot the list).
7. Comparable class, 20 points. Define a class called ClockTime that stores
information about time of day using a standard clock. Each ClockTime object
keeps track of hours, minutes, and a String to indicate "am" or "pm". It
has the following public methods:
ClockTime(hours, minutes, amPm) constructs a ClockTime with given
hours, minutes and amPm setting
getHours() returns the hours
getMinutes() returns the minutes
getAmPm() returns the am/pm setting
toString() returns a String representation of
the time
Assume that the values passed to your constructor are legal. In particular,
hours will be between 1 and 12 inclusive, minutes will be between 0 and 59
inclusive, and the am/pm parameter will be either the String "am" or the
String "pm". These values should be returned by the various "get" methods.
The toString method should return a String composed of the hours followed by
a colon followed by the minutes (2 digits) followed by a space followed by
the am/pm String. For example, given these declarations:
ClockTime time1 = new ClockTime(8, 31, "am");
ClockTime time2 = new ClockTime(12, 7, "pm");
time1.toString() should return "8:31 am" and time2.toString() should return
"12:07 pm". You must exactly reproduce the format of these examples.
Your class should implement the Comparable<E> interface with earlier times
consider "less." The earliest time is 12:00 am and the latest time is 11:59
pm. In between the time increases as it would in a standard clock. Keep in
mind that 12:59 am is followed by 1:00 am, that 11:59 am is followed by
12:00 pm, and that 12:59 pm is followed by 1:00 pm.
8. Binary Trees, 20 points. Write a method called makeFull that turns a binary
tree of integers into a full binary tree. A full binary tree is one in
which every node has either 0 or 2 children. Your method should produce a
full binary tree by replacing each node that has one child with a new node
that has the old node as a leaf where there used to be an empty tree. The
new node should store a value that indicates the level of the tree (-1 for
the first level of the tree, -2 for the second level of the tree, and so
on). For example, if a tree called t stores the following:
+----+
| 12 |
+----+
/
+----+
| 29 |
+----+
and we make the call:
t.makeFull();
then the tree should store the following after the call:
+----+
| -1 |
+----+
/ \
+----+ +----+
| 29 | | 12 |
+----+ +----+
Notice that the node storing 12 that used to be at the top of the tree is
now a leaf where there used to be an empty tree. In its place at the top of
the tree is a new node that stores the value -1 to indicate that it was
added at level 1 of the tree. Your method should perform this operation
at every level of the tree. For example, if t had instead stored:
+----+
| 12 |
+----+
/ \
+----+ +----+
| 28 | | 19 |
+----+ +----+
/ /
+----+ +----+
| 94 | | 32 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| 65 | | 18 | | 72 |
+----+ +----+ +----+
then after the call it would store:
+----+
| 12 |
+----+
/ \
+----+ +----+
| -2 | | -2 |
+----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 94 | | 28 | | -3 | | 19 |
+----+ +----+ +----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 65 | | 18 | | 32 | | 72 |
+----+ +----+ +----+ +----+
<continued on next page>
Notice that two nodes were added at level 2, and one at level 3.
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 an IntTreeNode 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;
<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 assume that any particular methods are available. YOU ARE NOT TO
CHANGE THE DATA FIELD OF THE EXISTING NODES IN THE TREE (what we called
"morphing" in assignments 7 and 8). You will, however, construct new nodes
containing negative values to be inserted into the tree and you will change
the links of the tree to restructure the tree as described.
9. Linked Lists, 20 points. Write a method called reverse3 that reverses each
successive sequence of 3 values in a list of integers. For example, suppose
that a variable called list stores the following sequence of values:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
and we make the following call:
list.reverse3();
Afterwards the list should store the following sequence of values:
[3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13]
The first sequence of 3 values (1, 2, 3) has been reversed to be (3, 2, 1).
The second sequence of 3 values (4, 5, 6) has been reverse to be (6, 5, 4).
And so on. If the list has extra values that are not part of a sequence of
3, those values are unchanged. For example, if the list had instead stored:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17]
The result would have been:
[3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13, 16, 17]
Notice that the values (16, 17) are unchanged in position because they were
not part of a sequence of three values.
These examples purposely used sequential integers to make the rearrangement
clear, but you should not expect that the list will store sequential
integers. For example, the following list:
[3, 8, 19, 42, 7, 26, 19, -8, 193, 204, 6, -4, 99]
would be rearranged as follows:
[19, 8, 3, 26, 7, 42, 193, -8, 19, -4, 6, 204, 99]
Your method should not change the list if it has fewer than three values.
You are writing a public method for a linked list class defined as follows:
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>
}
<continued on next page>
You are writing a method that will become part of the LinkedIntList class.
You may define private helper methods to solve this problem, but otherwise
you may not assume that any particular methods are available. You are
allowed to define your own variables of type ListNode, but 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 lists. Your solution must run in
O(n) time where n is the length of the list.
10. Fiction, 1 point (bonus). Your TA has woken up in jail. Explain why. You
may express your answer in any way you choose by writing a story, drawing a
picture, writing a poem, etc. 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