C Sc 127B Practice Test 2 Spring 13Answers
1. Write the output generated by the following code. (6pts)
OurQueue<String> q = new LinkedQueue<String>();
q.add("a");
q.add("b");
q.add("c");
while(! q.isEmpty()) {
System.out.println(q.isEmpty() + " " + q.remove());
}
2. Complete method doubleQueue that will cause every element in the OurQueue argument to be duplicated.
public void doubleQueue(OurQueue<String> q) {
OurQueue<String> temp = new OurQueue<String>();
while (!q.isEmpty()) {
String front = q.remove();
temp.add(front);
temp.add(front);
}
// This loop is required. It would be incorrect to use q = temp
while (!temp.isEmpty())
q.add(temp.remove());
}
3. Write the return values from each call to the method named mystery. (6pts)
___1___mystery(25) ____6___mystery(19) _____9__mystery(9)
public int mystery(int n) {
if (n > 20)
return 1;
else if (n > 10)
return 5 + mystery(n + 5);
else
return 3 + mystery(n + 8);
}
4. Write the output generated by the method call mystery2("X", 6); ______(4pts)
public void mystery2(String s, int digit) {
if(digit <= 1)
System.out.println(digit);
else {
s = s + "<";
mystery2(s, digit - 2);
System.out.println(s + digit);
}
}
5. Implement the trib method recursively. (6pts)
public int trib(int n) {
if(n <= 3)
return 1;
else
return trib(n-1) + trib(n-2) + trib(n-3);
}
6. Use recursion to complete method oddDownEvenUp so it first prints all odd integers from the largest odd number <= argument down to 1.
oddDownEvenUp(4); // 3 1 2 4
oddDownEvenUp(9); // 9 7 5 3 1 2 4 6 8
public void oddDownEvenUp(int n) { // Or have two private helpers
if (n > 0) {
if (n % 2 == 1)
System.out.print(n + " ");
oddDownEvenUp(n - 1);
if (n % 2 == 0)
System.out.print(n + " ");
}
}
7. Complete occurrencesOfto return how often an int element occurs in an array on integer. Use
int[] a = { 1, 2, 1, 2, 4, 2 };
assertEquals(2, occurrencesOf(1, a);
public int occurrencesOf(int value, int[] x) {
return occurrencesOf(value, x, 0);
}
private int occurrencesOf(int value, int[] x, int index) {
if (index == x.length)
return 0;
else {
int foundOne = 0;
if (x[index] == value)
foundOne = 1;
return foundOne + occurrencesOf(value, x, index + 1);
}
}
8. Complete sum to return the sum of the array elements. Use recursion. Do not use any loop. (12pts)
int[] a = { 1, 2, 3, 4 };
assertEquals(10, sum(a));
public int sum(int[] nums) {
return sum(nums, 0);
}
private int sum(int[] nums, int index) {
if(index == x.length)
return 0;
else
return nums[index] + sum(nums, index + 1); // never use index++
}
9.To class LinkedListusing a singly-linked structure, add method removeAll(E element) so all
assertEquals("B X B", list.toString());
list.removeAll("B");
assertEquals("X", list.toString());
assertEquals(1, list.size());
public void removeAll(E el) {
removeAll(first, el);
}
privatevoid removeAll(Node ref, E el) {
if (ref == null) // base case
return;
elseif (el.equals(first.data)) { // see if first needs to be adjusted
first = first.next;
n--;
removeAll(first, el);
}
elseif (ref.next != null & el.equals(ref.next.data)) { // peek ahead if there is one
ref.next = ref.next.next;
n--;
removeAll(ref, el);
}
else
removeAll(ref.next, el); // didn't match, so removeAll beginning at the next node
}
}
10) Write the output generated by this code (9pts)
public void hardCodeATree() {
root = new TreeNode("root");
root.left = new TreeNode("c");
root.left.left = new TreeNode("s");
root.left.right = new TreeNode("1");
root.right = new TreeNode("2");
root.right.left = new TreeNode("7");
root.right.right = new TreeNode("B");
}
private void toString(TreeNode t) {
if (t != null) {
result += t.data + " ";
toString(t.left);
toString(t.right);
}
}
}
11. Use the following binary tree to write out each of the three traversals indicated below. (9pts)
/ Preorder traversal __A B D E CInorder traversal __D B E A C
Postorder traversal __D E B C A
1