<![CDATA[
CSE143 Final
Winter 2016
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 "cheat sheet" at the end that you can use as scratch paper or to
write answers. You can also request scratch paper from a TA. You are not
allowed to access any of your own papers during the exam.
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, to declare variables and
parameters using interfaces when possible, and to avoid the use of break
statements, the diamond operator, and return from a void method. 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).
For standard Java classes such as Math and String, you are limited to the
methods listed on the cheat sheet. You are not allowed to use the Arrays or
Collections classes or other standard classes and methods that aren't included
on the cheat sheet.
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 a TA
and exit quietly.
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 8 |
+---+
/ \
/ \
+---+ +---+
| 7 | | 5 |
+---+ +---+
/ / \
/ / \
+---+ +---+ +---+
| 2 | | 1 | | 0 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 4 | | 9 | | 3 | | 6 |
+---+ +---+ +---+ +---+
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: George, Jane, Emma, Frank,
Harriet, Weston, Elton. Assume the search tree uses alphabetical ordering
to compare words.
3. Collections Mystery, 5 points. Consider the following method:
public Set<Integer> mystery(int[][] data, int pos, int n) {
Set<Integer> result = new TreeSet<Integer>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result.add(data[i + pos][j + pos]);
}
}
return result;
}
Suppose that a variable called grid has been declared as follows:
int[][] grid = {{8, 2, 7, 8, 2, 1}, {1, 5, 1, 7, 4, 7},
{5, 9, 6, 7, 3, 2}, {7, 8, 7, 7, 7, 9},
{4, 2, 6, 9, 2, 3}, {2, 2, 8, 1, 1, 3}};
which means it will store the following 6-by-6 grid of values:
8 2 7 8 2 1
1 5 1 7 4 7
5 9 6 7 3 2
7 8 7 7 7 9
4 2 6 9 2 3
2 2 8 1 1 3
For each call below, indicate what value is returned. If the method call
results in an exception being thrown, write "exception" instead.
Method Call Contents of Set Returned
mystery(grid, 2, 2) _________________________________
mystery(grid, 0, 2) _________________________________
mystery(grid, 3, 3) _________________________________
4. Collections Programming, 5 points. Write a method called removeDuplicates
that takes a list of Point objects and that removes duplicates from the
list, returning a set of the Point objects from the list. For example, if
a list called points contains the following values:
[[x=1,y=3], [x=7,y=7], [x=1,y=3], [x=7,y=8], [x=1,y=3], [x=7,y=7],
[x=7,y=8], [x=4,y=2], [x=7,y=8], [x=7,y=8], [x=4,y=2], [x= 4,y=2]]
then the call removeDuplicates(points) should leave the list storing:
[[x=1,y=3], [x=7,y=7], [x=7,y=8], [x=4,y=2]]
and the set returned should store the same values. Your method should
preserve the order of values in the list (removing duplicates that come
later in the list), but the values in the set can appear in any order.
You may construct iterators and the set to be returned, but you are not
allowed to construct other structured objects (no string, set, list, etc.).
5. Binary Trees, 10 points. Write a method called oddPathSum that returns
the number of nodes in a tree that have an odd path sum. The path sum of a
node is the sum of all values from the overall root to that node. For
example if the variable t refers to the following tree:
+----+
| 5 |
+----+
/ \
+----+ +----+
| 3 | | 12 |
+----+ +----+
/ \ \
+----+ +----+ +----+
| 1 | | 2 | | 7 |
+----+ +----+ +----+
/ \ / \
+----+ +----+ +----+ +----+
| 6 | | 11 | | 10 | | 4 |
+----+ +----+ +----+ +----+
Then t.oddPathSum() should return 4 indicating that 4 of these nodes have an
odd path sum (the nodes storing 5, 12, 1, and 6)
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 recordGrade that
takes as parameters a map of student grades, a student id, a numerical
grade, and a course, and that records the grade in the map. The student id
is used as a key for the overall map with each id associated with a map of
student grades. The map of student grades uses the course as a key and
associates each course with a numerical grade (stored in an object of type
Double). For example, suppose that a variable called grades stores a map
with information for two students each with grades in two courses:
{1212121={cse142=3.0, engl111=2.5}, 4444444={cse143=3.6, engl131=3.8}}
The following calls indicate a new grade for student 4444444 (3.2 in
phys121) and a grade for a new student (3.5 in math126 for student 1234567).
recordGrade(grades, "4444444", 3.2, "phys121");
recordGrade(grades, "1234567", 3.5, "math126");
After the call, the grades map would store:
{1212121={cse142=3.0, engl111=2.5}, 1234567={math126=3.5},
4444444={cse143=3.6, engl131=3.8, phys121=3.2}}
Notice that the map now includes grade information for student 1234567 and a
third grade for student 4444444. A student may take a course more than
once, in which case you should store the highest grade the student has
gotten for that course. For example, the call:
recordGrade(grades, "1212121", 2.8, "engl111");
would change the map to:
{1212121={cse142=3.0, engl111=2.8}, 1234567={math126=3.5},
4444444={cse143=3.6, engl131=3.8, phys121=3.2}}
If the call instead had been with a grade of 2.4 in engl111, the map would
have been unchanged because that grade is lower than the grade currently in
the map. The overall map has keys that are ordered by student ID and each
student's map of grades should be ordered by the course number.
Your method should construct a map for each student not already in the
overall map and you may construct iterators, but you are not allowed to
construct other structured objects (no string, set, list, etc.).
7. Comparable class, 20 points. Define a class called AdmissionsEntry that
keeps track of information for an admissions candidate and how that
candidate is rated by reviewers (real numbers between 0.0 and 5.0). The
class has the following public methods:
AdmissionsEntry(id) constructs an AdmissionsEntry object with given ID
rate(rating) records a rating for the candidate
flag() indicates that the candidate should be discussed
getID() returns the ID of the candidate
getRating() returns the average rating (0.0 if no ratings)
toString() returns a String with ID and average rating
Below is an example for a candidate that has been reviewed four times:
AdmissionsEntry entry = new AdmissionsEntry("2222222");
entry.rate(3.75);
entry.rate(3.65);
entry.rate(3.8);
entry.rate(3.75);
entry.flag();
After these calls, the call entry.getRating() would return 3.7375 (the
average of the ratings). The toString method should return a string
composed of the ID, a colon, and the average rating rounded to 2 digits
after the decimal point ("2222222: 3.74" for this example). If there are no
ratings, then getRating and toString should indicate a rating of 0.0.
Each AdmissionsEntry object should keep track of whether that candidate
should be discussed by the admissions committee. Any candidate who receives
a score of 4.0 or higher should be discussed even if their average rating is
below 4.0. Notice also that a candidate can be flagged for discussion even
if none of the ratings are 4.0 or higher, as in the example above.
The AdmissionsEntry class should implement the Comparable<E> interface.
Define the method so that when sorted, a list of entries will have students
to be discussed appearing first followed by students not to be discussed.
Within those groups, students with higher average ratings should appear
earlier in the list. Students with the same discussion status and the same
average rating should appear in increasing order by ID. Recall that values
considered "less" appear earlier in a sorted list. You may not use Double
objects or methods of the Double class to solve this problem.
You may begin your solution to AdmissionsEntry below, but an extra page is
provided for your answer after this page.
Continue your solution to AdmissionsEntry below.
8. Binary Trees, 20 points. Write a method tighten that eliminates branch
nodes that have only one child from a binary tree of integers. For example,
if a variable called t stores a reference to the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 28 | | 19 |
+----+ +----+
/ /
/ /
+----+ +----+
| 94 | | 32 |
+----+ +----+
/ \ \
/ \ \
+----+ +----+ +----+
| 65 | | -8 | | 72 |
+----+ +----+ +----+
\ / \
\ / \
+----+ +----+ +----+
| 10 | | 42 | | 50 |
+----+ +----+ +----+
then the call:
t.tighten();
should leave t storing the following tree:
+----+
| 12 |
+----+
/ \
/ \
+----+ +----+
| 94 | | 72 |
+----+ +----+
/ \ / \
/ \ / \
+----+ +----+ +----+ +----+
| 65 | | 10 | | 42 | | 50 |
+----+ +----+ +----+ +----+
Notice that the nodes that stored the values 28, 19, 32, and -8 have all
been eliminated from the tree because each had one child. When a node is
removed, it is replaced by its child. Notice that this can lead to multiple
replacements because the child might itself be replaced (as in the case of
19 which is replaced by its child 32 which is replaced by its child 72).
<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
<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 assume that any particular methods are available. You are not
allowed to change the data fields of the existing nodes in the tree (what we
called "morphing" in assignments 7 and 8), you are not allowed to construct
new nodes or additional data structures, and your solution must run in O(n)
time where n is the number of nodes in the tree.
9. Linked Lists, 20 points. Write a method called removeFirstOf3 that
removes the first value in successive groups of three from a list of
integers, returning those values in their original order as a new list. For
example if a variable called list1 stores these values:
[3, 19, 7, 45, -2, 8, 6, 18, 42, 5]
| | | | | |
+------+ +------+ +------+
group group group
Then the following call:
LinkedIntList list2 = list1.removeFirstOf3();
Should result in list1 and list2 storing the following values:
list1: [19, 7, -2, 8, 18, 42]
list2: [3, 45, 6, 5]
Notice that the values stored in list2 are the values that were the first
value in each of the groups of three in the original list. When a list has
one or two values at the end that are not part of a group of three, then the
first of those values is removed and included in the new list, as with the
value 5 in the example above.
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 will need to call the LinkedIntList constructor to construct the list to
be returned and 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 list.
Write your solution to removeFirstOf3 on the next page.
Write your solution to removeFirstOf3 below.
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