<![CDATA[
CSE143X Sample Final, Autumn 2017
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 4 |
+---+
/ \
/ \
+---+ +---+
| 2 | | 1 |
+---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 7 | | 3 | | 8 | | 5 |
+---+ +---+ +---+ +---+
\ \ /
\ \ /
+---+ +---+ +---+
| 9 | | 6 | | 0 |
+---+ +---+ +---+
Fill in each of the traversals below:
Preorder traversal __________________________________________________
Inorder traversal __________________________________________________
Postorder traversal __________________________________________________
2. Recursive Programming, 9 points. Write a recursive method called
writeSquares that takes an integer n as a parameter and that writes the
first n squares to System.out separated by commas with the odd squares in
descending order followed by the even squares in ascending order. For
example, the call:
writeSquares(5);
should produce the following output:
25, 9, 1, 4, 16
The odd squares (25, 9, and 1) appear first in descending order followed by
the even squares (4 and 16) in ascending order. Notice that commas are used
to separate consecutive values in the list. Your method should send its
output to System.out and should not call println. For example, the
following calls:
writeSquares(5);
System.out.println(); // to complete the line of output
writeSquares(1);
System.out.println(); // to complete the line of output
writeSquares(8);
System.out.println(); // to complete the line of output
should produce exactly three lines of output:
25, 9, 1, 4, 16
1
49, 25, 9, 1, 4, 16, 36, 64
You must exactly reproduce the format of these examples. Your method should
throw an IllegalArgumentException if passed a value less than 1. 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 Fog extends Sleet {
public void method1() {
System.out.println("Fog 1");
}
public void method3() {
System.out.println("Fog 3");
}
}
public class Rain extends Snow {
public void method1() {
System.out.println("Rain 1");
}
public void method2() {
System.out.println("Rain 2");
}
}
public class Sleet extends Snow {
public void method2() {
System.out.println("Sleet 2");
super.method2();
method3();
}
public void method3() {
System.out.println("Sleet 3");
}
}
public class Snow {
public void method2() {
System.out.println("Snow 2");
}
public void method3() {
System.out.println("Snow 3");
}
}
And assuming the following variables have been defined:
Snow var1 = new Sleet();
Rain var2 = new Rain();
Snow var3 = new Fog();
Object var4 = new Snow();
Sleet var5 = new Fog();
Snow var6 = new Rain();
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 (you may abbreviate these as "ce" and "re" or "c.e." and "r.e.").
Statement Output
------------------------------------------------------------
var1.method1(); ____________________________
var2.method1(); ____________________________
var1.method2(); ____________________________
var2.method2(); ____________________________
var3.method2(); ____________________________
var4.method2(); ____________________________
var5.method2(); ____________________________
var1.method3(); ____________________________
var2.method3(); ____________________________
var3.method3(); ____________________________
var4.method3(); ____________________________
var5.method3(); ____________________________
((Rain)var4).method1(); ____________________________
((Fog)var5).method1(); ____________________________
((Sleet)var3).method1(); ____________________________
((Sleet)var3).method3(); ____________________________
((Fog)var6).method3(); ____________________________
((Snow)var4).method2(); ____________________________
((Sleet)var4).method3(); ____________________________
((Rain)var6.method3(); ____________________________
4. Collections Programming, 5 points. Write a method called extractEqual that
takes a set of Point objects and that returns a new set that contains all of
the Point objects where the x and y values are equal to each other. For
example, if a set called points contains the following values:
[[x=42,y=3], [x=4,y=2], [x=18,y=1], [x=7,y=8], [x=-2,y=-2], [x=3,y=3],
[x=7,y=7], [x=0,y=82], [x=14,y=14], [x=3,y=13], [x=-3,y=4], [x=1,y=3]]
then the call extractEqual(points) should return the following set:
[[x=-2,y=-2], [x=3,y=3], [x=7,y=7], [x=14,y=14]]
The original set should be unchanged and you should not construct any new
Point objects in solving this problem. As a result, both sets will end up
referring to the Point objects in which the x and y coordinates are equal.
Your method is expected to have reasonable efficiency in that it shouldn't
lead to more set operations than it needs to.
5. Stacks/Queues, 10 points. Write a method called parityMatches that takes
two stacks of integers as parameters and that returns a count of the number
of elements in corresponding positions that have the same parity. Two
numbers are considered to have the same parity if they are either both even
or both odd. Suppose, for example, that two stacks store these values:
s1: bottom [3, 4, 5] top s2: bottom [37, 14, 24] top
The method compares values in corresponding positions in the two stacks (3
and 37, 4 and 14, 5 and 24). Of these pairs, two have the same parity. The
third pair (5 and 24) do not have the same parity. Therefore the method
call parityMatches(s1, s2) would return 2.
Your method should throw an IllegalArgumentException if they have different
numbers of elements. You may also assume that all of the numbers stored in
the list are greater than or equal to 0. Your method is to examine the two
stacks but must return them to their original state before terminating.
You are to use one queue 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 also may
not solve the problem recursively. Your solution must run in O(n) time
where n is the size of the stacks. Use the Stack and Queue structures
described in the cheat sheet and obey the restrictions described there
(recall that you can't use the peek method or a foreach loop or iterator).
6. Binary Trees, 10 points. Write a method called purebredOdds that returns
the number of purebred odd values in a binary tree of integers. A purebred
odd is an odd number all of whose ancestors in the tree are also odd. For
example, suppose that a variable t refers to the following tree:
+----+
| 15 |
+----+
/ \
+----+ +----+
| 27 | | 34 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| 29 | | 75 | | 83 |
+----+ +----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 18 | | 33 | | 46 | | 51 |
+----+ +----+ +----+ +----+
Then the call t.purebredOdds() should return 5 because this tree has a total
of 5 purebred odd values: 15, 27, 29, 75, and 33. The values 83 and 51 are
odd numbers, but not purebred odd numbers because they have an even number
as an ancestor in the tree (the value 34). Notice that if the overall root
is an even number, then the tree will have no purebred odd numbers at all
because every other node has the overall root as an ancestor.
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 indexMap that
takes a list of strings as a parameter and that returns a map that
associates each string from the list to a list of indexes at which that
string occurs. For example, if a variable called list stores the following:
[to, be, or, not, to, be]
then the call indexMap(list) should return the following map:
{be=[1, 5], not=[3], or=[2], to=[0, 4]}
Notice that each string from the original list maps to a list of indexes.
For example, the string "to" appeared at index 0 and 4 in the original list,
so it maps to a list with the values 0 and 4. The map returned by your
method should be ordered alphabetically and the lists that each string maps
to should have indexes in increasing order, as in the example.
Your method should construct the new map and each of the lists contained in
the map and can construct iterators but should otherwise not construct any
new data structures. It should also not modify the list of words passed as
a parameter and it should be reasonably efficient.
8. Comparable class, 10 points. Define a class called BookData that keeps
track of information for a book and how it is rated by customers (real
numbers between 0.0 and 5.0). The class has the following public methods:
BookData(title) constructs a BookData object with the given title
review(rating) records a review for the book with given rating
getRating() returns the average of all ratings
toString() returns a String with title, average rating, # ratings
Below is an example for a book that has been reviewed four times:
BookData book = new BookData("1984");
book.review(4.7);
book.review(5);
book.review(4.9);
book.review(4.9);
After these calls, the call book.getRating() would return 4.875 (the average
of the ratings). The toString method should return a string of the form:
<title> <rating> (reviews: <count>)
For example, given the previous calls, book.toString() would produce:
"1984 4.875 (reviews: 4)"
You may assume that every book is reviewed at least once.
The BookData class should implement the Comparable<E> interface. Books that
have a higher average rating should be considered "less" than other books so
that they appear at the beginning of a sorted list. Books that have the
same average rating should be ordered by the number of reviews, with books
that have been reviewed more often considered "less" than books that have
been reviewed less frequently.
9. Binary Trees, 15 points. Write a method called stretch that stretches
each node that has only one child in a binary tree of integers. More
specifically, each node that has a single child should be replaced by a new
node storing the data 1 and with the old node as a child in the same
direction as the original node's child. For example, suppose a variable t
stores a reference to the following tree:
+----+
| 13 |
+----+
/ \
+----+ +----+
| 48 | | 17 |
+----+ +----+
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/ \
+----+ +----+
| 65 | | 10 |
+----+ +----+
There are two nodes in this tree that have a single child: the nodes storing
48 and 17. Each of those nodes is replaced in the tree with a new node
storing the value 1 and with the original node as a child in the same
direction as its only child. The node storing 48 has a left child, so it
appears to the left of a new node storing 1. The node 17 has a right child,
so it appears to the right of a new node storing 1. So after the call:
t.stretch();
The tree should look like this:
+----+
| 13 |
+----+
/ \
+----+ +----+
| 1 | | 1 |
+----+ +----+
/ \
+----+ +----+
| 48 | | 17 |
+----+ +----+
/ \
+----+ +----+
| 82 | | 23 |
+----+ +----+
/ \
+----+ +----+
| 65 | | 10 |
+----+ +----+
This stretching process should be performed on every node in the original
tree that has a single child.
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 the value 1 to be inserted into the tree and
you will change the links of the tree to include these new nodes.
10. Linked Lists, 15 points. Write a method of the LinkedIntList class called
mergeFrom that takes a list of integers as a parameter and that moves the
values from the second list into the first list so as to preserve sorted
order assuming that the two lists are in sorted (nondecreasing) order
initially. The resulting list should contain the values from both lists in
sorted order and the list passed as a parameter should be empty after the
call. For example, if the variables list1 and list2 store the following:
list1 = [-3, 0, 9, 12, 43, 54], list2 = [9, 9, 15, 98]
and you make the following call:
list1.mergeFrom(list2);
then the lists should store the following values after the call:
list1 = [-3, 0, 9, 9, 9, 12, 15, 43, 54, 98], list2 = []
Notice that list2 is empty after the call and that the values that were in
list2 have been moved into list1 so as to preserve sorted order. If the
call instead had been list2.mergeFrom(list1) then the result would be:
list1 = [], list2 = [-3, 0, 9, 9, 9, 12, 15, 43, 54, 98]
Either list might be empty, as in:
list1 = [5, 7, 7, 12, 15], list2 = []
in which case the call list1.mergeFrom(list2) would leave the lists
unchanged while list2.mergeFrom(list1) would leave you in this state:
list1 = [], list2 = [5, 7, 7, 12, 15]
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.
Both lists are of type LinkedIntList. 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 merged list. As in the examples above, assume that both
lists are in sorted order.
]]>