<![CDATA[
CSE143X Sample Final, Autumn 2016
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. Collections Programming, 5 points. Write a method called retainAll that
takes two sets of integers as parameters and that removes any values in the
first set that are not found in the second set. For example, given sets:
s1: [0, 19, 8, 9, 12, 13, 14, 15]
s2: [0, 19, 2, 4, 5, 9, 10, 11]
If the following call is made:
retainAll(s1, s2);
after the call, the sets would store the following values:
s1: [0, 19, 9]
s2: [0, 19, 2, 4, 5, 9, 10, 11]
You are implementing a two-argument alternative to the standard Set method
called retainAll, so you are not allowed to call that method to solve this
problem. You are also not allowed to construct any structured objects to
solve the problem (no set, list, stack, queue, string, etc) although you can
construct iterators. Your method should not change the second set passed
as a parameter.
5. 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.
6. 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.
7. 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).
8. Comparable class, 10 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) constructs a TeamData object with the given team name
success(time) records the successful completion of a problem with the
given time
toString() returns a String with team name, problems solved, and
total time
Each time a team solves a problem, the success method for the team will be
called exactly once to record that solved problem and the amount of time the
team took to solve it. The TeamData object must keep track of the total
number of problems solved and the sum of all of the times. Below is an
example of a typical usage:
TeamData team1 = new TeamData("UW Red");
team1.success(18);
team1.success(82);
team1.success(130);
System.out.println(team1);
The println should produce the following output:
UW Red solved 3 in 230 minutes
Your toString method must exactly reproduce this format. 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.
9. 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 |
+----+ +----+ +----+ +----+
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.
10. 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.
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.
]]>