<![CDATA[
CSE143 Sample Final (Part 1) handout #30
1. Binary Tree Traversals, 6 points. Consider the following tree.
+---+
| 2 |
+---+
/ \
/ \
+---+ +---+
| 6 | | 7 |
+---+ +---+
/ \ \
/ \ \
+---+ +---+ +---+
| 0 | | 1 | | 9 |
+---+ +---+ +---+
/ \ / \
/ \ / \
+---+ +---+ +---+ +---+
| 3 | | 5 | | 8 | | 4 |
+---+ +---+ +---+ +---+
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: Kirk, Spock, Scotty, McCoy,
Uhuru, Chekov, Sulu. Assume the search tree uses alphabetical ordering to
compare words.
3. Programming with inheritance, 20 points. You have been asked to extend a
Java class called DocumentList that is used to store a list of Document
objects. The DocumentList class has a set of methods that is similar to
those we have seen for the built-in ArrayList and LinkedList classes:
public DocumentList(int capacity) constructs an empty document list
of given capacity
public void add(Document d) appends d to end of list
public void add(int index, Document d) inserts d at given index
public void remove(int index) removes document at given index
public int indexOf(Document d) returns index of first occurrence
of d; -1 if not found
public int size() returns # of elements in the list
The class works correctly, but we are interested in analyzing how the list
changes over time. In particular, we are going to collect statistics about
the sequence of states the list goes through as it is modified. The list is
constructed as an empty list and this will be the first state we want to
keep track of. Then, each time that the list is modified, we want to keep
track of that new state. The list is modified each time a client calls
either of the add methods or the remove method. Each modification leads to
a new state even if the list ends up returning to a value it had previously.
For example, the list starts out as an empty list and it might go through a
series of modifications that lead it to be empty a second time, but we would
consider each to be a different state.
You are to define a new class called AnalyzingDocumentList that extends
through inheritance the DocumentList class so that it has the same
functionality described above while also keeping track of information about
the various states that the list goes through. In particular, it should
provide the following additional public methods:
public int totalStates() a count of the total number of states
this list has gone through
public int sizeCount(int size) a count of the number of states this
list has gone through in which its
size was the given size
For example, suppose that an AnalyzingDocumentList called lst is manipulated
in the following ways:
the list is constructed (size is 0)
a document is appended to the end of the list (size now 1)
a document is appended to the end of the list (size now 2)
a document is appended to the end of the list (size now 3)
a document is added at index 1 (size now 4)
the document at index 1 is removed (size now 3)
the document at index 0 is removed (size now 2)
a document is added at index 0 (size now 3)
a document is appended to the end of the list (size now 4)
Then the analyzing methods would return the following values:
lst.totalStates() returns 9 (initial state plus 8 modifications)
lst.sizeCount(0) returns 1 (1 state had size 0)
lst.sizeCount(1) returns 1 (1 state had size 1)
lst.sizeCount(2) returns 2 (2 states had size 2)
lst.sizeCount(3) returns 3 (3 states had size 3)
lst.sizeCount(4) returns 2 (2 states had size 4)
lst.sizeCount(5) returns 0 (no states had size 5)
...
4. Linked Lists, 20 points. Write a method 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>
}
You are writing a method that will become part of the LinkedIntList class.
You may not call any methods of the class to solve this problem, 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.
]]>