<![CDATA[
CSE143X Final
Autumn 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 Recursive Programming 9 _____
3 Details of Inheritance 10 _____
4 Stacks/Queues 10 _____
5 Binary Trees 10 _____
6 Collections Programming 10 _____
7 Comparable class 15 _____
8 Binary Trees 15 _____
9 Linked Lists 15 _____
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. The cheat sheet mentions important
restrictions on Stacks and Queues that you must follow. You do not have to
include any import statements. You are allowed to abbreviate "compiler error"
and "runtime error" for the inheritance question (as in "ce" and "re" or "c.e."
and "r.e."), but you should otherwise NOT use any abbreviations on the exam.
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.
+---+
| 0 |
+---+
/ \
/ \
+---+ +---+
| 3 | | 4 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 2 | | 1 | | 7 |
+---+ +---+ +---+
\ / \ \
\ / \ \
+---+ +---+ +---+ +---+
| 9 | | 6 | | 5 | | 8 |
+---+ +---+ +---+ +---+
Fill in each of the traversals below:
Preorder traversal __________________________________________________
Inorder traversal __________________________________________________
Postorder traversal __________________________________________________
2. Recursive Programming, 9 points. Write a recursive method called digitMatch
that takes two nonnegative integers as parameters and that returns the
number of digits that match between them. Two digits match if they are
equal and have the same relative position starting from the end of the
number (i.e., starting with the ones digit). In other words, the method
should compare the last digits of each number, the second-to-last digits of
each number, the third-to-last digits of each number, and so forth, counting
how many pairs match. For example, digitMatch(1072503891, 62530841) would
compare as follows:
1 0 7 2 5 0 3 8 9 1
| | | | | | | |
6 2 5 3 0 8 4 1
The method should return 4 in this case because 4 of these pairs match (2-2,
5-5, 8-8, and 1-1). Below are more examples:
Method call Result Method call Result
-------------------------------- --------------------------------
digitMatch(38, 34) 1 digitMatch(5, 5552) 0
digitMatch(892, 892) 3 digitMatch(1234567, 67) 2
digitMatch(298892, 7892) 3 digitMatch(380, 0) 1
digitMatch(123456, 654321) 0 digitMatch(0, 4) 0
digitMatch(42, 24) 0 digitMatch(0, 0) 1
Your method should throw an IllegalArgumentException if either of the two
parameters is negative. You are not allowed to construct any structured
objects to solve this problem (no array, String, StringBuilder, ArrayList,
etc) and you may not use a while loop, for loop or do/while loop to solve
this problem; you must use recursion.
3. Details of inheritance, 10 points. Assuming that the following classes have
been defined:
public class Scoop extends Spoon {
public void method1() {
System.out.println("Scoop 1");
}
public void method3() {
System.out.println("Scoop 3");
}
}
public class Cone {
public void method1() {
System.out.println("Cone 1");
}
public void method2() {
System.out.println("Cone 2");
method1();
}
}
public class Spoon extends Cone {
public void method1() {
System.out.println("Spoon 1");
super.method1();
}
}
public class Cup extends Cone {
public void method3() {
System.out.println("Cup 3");
}
}
And assuming the following variables have been defined:
Cone var1 = new Scoop();
Cone var2 = new Spoon();
Cone var3 = new Cone();
Object var4 = new Spoon();
Spoon var5 = new Scoop();
Object var6 = new Cup();
In the table below, indicate in the right-hand column the output produced by
the statement in the left-hand column. If the statement produces more than one
line of output, indicate the line breaks with slashes as in "a/b/c" to indicate
three lines of output with "a" followed by "b" followed by "c". If the
statement causes an error, fill in the right-hand column with either the phrase
"compiler error" or "runtime error" to indicate when the error would be
detected.
Statement Output
------------------------------------------------------------
var1.method1(); ____________________________
var2.method1(); ____________________________
var3.method1(); ____________________________
var4.method1(); ____________________________
var5.method1(); ____________________________
var6.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var6.method2(); ____________________________
((Spoon)var1).method3(); ____________________________
((Cup)var6).method3(); ____________________________
((Scoop)var4).method1(); ____________________________
((Cone)var6).method2(); ____________________________
((Cone)var4).method1(); ____________________________
((Scoop)var6).method3(); ____________________________
((Scoop)var3).method3(); ____________________________
((Scoop)var5).method3(); ____________________________
4. Stacks/Queues, 10 points. Write a method called reverseByN that takes a
queue of integers and an integer n as parameters and that reverses each
successive sequence of length n in the queue. For example, suppose that a
variable called q stores the following sequence of values:
front [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] back
and we make the following call:
reverseByN(q, 3);
Then q should store the following values after the call:
front [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10, 15, 14, 13] back
Notice that the first three values (1, 2, 3) have been reversed, as have the
next three values (4, 5, 6), the next three values (7, 8, 9), and so on. If
the size of the queue is not an even multiple of n, then there will be a
sequence of fewer than n values at the end. This sequence should be
reversed as well. For example, if q stores this sequence:
front [8, 9, 15, 27, -3, 14, 42, 8, 73, 19] back
and we make the call:
reverseByN(q, 4);
Then q should store the following values after the call:
front [27, 15, 9, 8, 8, 42, 14, -3, 19, 73] back
Notice that the two sequences of length 4 have been reversed along with the
sequence of two values at the end (73, 19). If n is greater than the size
of the queue, then the method should reverse the entire sequence.
You are to use one stack as auxiliary storage to solve this problem. You
may not use any other auxiliary data structures to solve this problem,
although you can have as many simple variables as you like. You may not use
recursion to solve this problem and your solution must run in O(n) time.
Use the Stack and Queue structures described in the cheat sheet and obey the
restrictions described there.
5. Binary Trees, 10 points. Write a method called printLevel that takes an
integer n as a parameter and that prints the values at level n from right to
left. The values should be printed one per line. By definition, the
overall root is at level 1, 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 |
+----+ +----+ +----+
then the call:
t.printLevel(3);
would produce the output:
15
14
11
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.
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 may define private helper methods to solve this problem, but otherwise
you may not call any other methods of the class. You may not define any
auxiliary 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 indicates 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 of the list).
7. Comparable class, 15 points. Define a class TeamData that keeps track of
information for a team of students competing in a programming contest. The
class has the following public methods:
TeamData(name, problems) constructs a TeamData object with the given
team name and the given number of problems
success(problem, time) record the successful completion of the
given problem with the given time
solved() returns the total number of problems solved
time() returns the total time for problems solved
percentCorrect() returns the percent of problems solved
toString() returns a String with name, problems
solved, total problems, and total time
Each time a team solves a problem, the success method for the team will be
called once giving the problem number and the time for that problem. The
TeamData object must keep track of the total number of problems solved and
the sum of all of the times. It does NOT have to keep track of which
problems have been solved. Below is an example of a typical usage:
TeamData team1 = new TeamData("UW Red", 8);
team1.success(3, 18);
team1.success(4, 82);
team1.success(6, 130);
System.out.println(team1);
The println should produce the following output:
UW Red solved 3 of 8 in 230 minutes
Your toString method must exactly reproduce this format. After this
interaction, the call team1.solved() would return 3, the call team1.time()
would return 230, and the call team1.percentCorrect() would return 37.5.
The TeamData class should implement the Comparable<E> interface. Teams that
perform better should be considered to be "less" than other teams so that
they appear at the beginning of a sorted list. In general, the team that
solves the most problems is considered the best, but when there is a tie for
the number of problems solved, then total time determines the winner. The
team with the lower total time wins in the case of a tie for total problems
solved.
You may assume that all values passed to your methods are valid and that the
total number of problems is greater than 0.
Write your solution to TeamData on the next page.
Write your solution to TeamData below.
8. Binary Trees, 15 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. 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, 15 points. Write a method called 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)
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>
}
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