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);

}