AnswersC Sc 227 to Practice Final, Summer 2012
1 Any answer will do: a, b, c, or d
2 a) one
b) three
c) first
d) System.out.println(first.data);
Node ref = first;
while(ref != first) {
ref = ref.next;
System.out.println(ref.data);
}
3. Write the code that would generate the linked structure shown below.
Node back = new Node("B");
back.next = new Node("A");
back.next.next = back;
4a public void reverse() {
Object[] temp = new Object[size()]; // or [n]
Node ref = first;
for (int i = 0; i < size(); i++) {
temp[i] = ref.data;
ref = ref.next;
}
ref = first;
for (int i = size() - 1; i >= 0; i--) {
ref.data = (E) temp[i]; // missing cast would not loose points
ref = ref.next;
}
}
4b public void addLast(E element) {
if (first == null) {
first = new Node(element);
} else {
Node ref = first;
while (ref.next != null) {
ref = ref.next;
}
ref.next = new Node(element);
}
n++; // would lose 2 points if n++ is missing
}
5
y
y
false
6 public void doubleStack(Stack<Integer> s) {
Stack<Integer> temp = new Stack<Integer>();
while (!s.isEmpty())
temp.push(s.pop());
while (!temp.isEmpty()) {
s.push(temp.peek());
s.push(temp.pop());
}
}
7. Write the return values from each call to the method named mystery. (8pts)
_1__mystery(0) _ 4__mystery(1) __ 7__mystery(2) __ 10__mystery(3) __13_mystery(4)
8. Write the output of stars with arguments 1, 2, and 3 (8pts)
9.
0
X<2
X<4
X<6
10. Or use two private helper methods, one for oddDown and a 2nd for even up. That would be easier than this:
public void oddDownEvenUp(int n) {
if (n > 0) {
if (n % 2 == 1)
System.out.print(n + " ");
oddDownEvenUp(n - 1);
if (n % 2 == 0)
System.out.print(n + " ");
}
}
Longer to write, but perhaps easier to visualize
public void oddDownEvenUp(int n) {
if (n % 2 == 0) {
oddDown(n - 1);
evenUp(n);
}
else {
oddDown(n);
evenUp(n - 1);
}
}
private void oddDown(int n) {
if (n > 0) {
System.out.print(n + " ");
oddDown(n - 2);
}
}
private void evenUp(int n) {
if (n > 0) {
evenUp(n - 2);
System.out.print(n + " ");
}
}
11. Use the following binary tree to write out each of the three traversals indicated below.
Preorder traversal 1 2 4 3 5 6
Inorder traversal 2 4 1 5 3 4
Postorder traversal 4 2 5 6 3 1
12. _No_ (must be unique)
13. _No_ (reverse order)
14. Draw a picture of the data that results from the following code on the BinarySearchTree
root
Matrix
/ \
Antz Shaft
\ / \
Bean Scream Titanic
15. You may use collection classes like Lists in answers.
public K nthLargest(int n) {
if(n < 0 || n >= size())
return null;
ArrayList<K> list = new ArrayList<K>();
build(list, root);
return list.get(n);
}
private void build(ArrayList<K> list, TreeNode t) {
if(t != null) {
build(list, t.left);
list.add(t.key);
build(list, t.right);
}
16. bottomLevelFiled ???
17
-5 -5 12 23
===
true
false
-5
23
18
3
B
C // this is the new value mapped to the key 50. The old value is gone
D
null // get returns null when the key is not found
[25, 50, 75] // with TreeMaps, keys are in order
[B, C, D] // and values are added with the inorder traversal of the BST
19 public List<Integer> intersection(List<Integer> s1, List<Integer> s2) {
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < s1.size(); i++) {
int current_s1 = s1.get(i);
// Add current_s1 if it not already in temp and is also in s2
if (!temp.contains(current_s1) s2.contains(current_s1))
temp.add(current_s1);
}
return temp;
}
19a) Write the public and private methods using a recursive solution.
public E maxKey() {
return maxKey(root);
}
private K maxKey(TreeNode t) {
if (t == null) // special case of an empty tree,the if could be in public maxKey
return null;
if (t.right == null)
return t.data;
else
return maxKey(t.right);
}