Name: ______
Midterm 2
CS 20
Fall 2008
Short Answer:_____/25
Output:_____/25
removeHead:_____/15
iterative countOccurrences_____/20
recursive countOccurrences_____/15
Total:_____/100
1) Write the base case and recursive case of each of the following problems (5 pts each):
a) Calculating the value 3x
Base Case:
Recursive Case:
b) Counting the number of occurrences of an element in a linked list
Base Case:
Recursive Case:
c)Your CD with initial balance b earns 3.5% interest per year. Calculate the value in year n.
Base Case:
Recursive Case:
2) 10 pts - Write the recursive method, in Java, to calculate the value 3x
public static int threeToTheX(int x)
{
}
3) (15 pts) (2-3-5-5)
public static int mystery(int x)
{
if (x <= 1)
return 5;
else
return (5 + mystery(x-1));
}
What is the output for mystery(1)?
What is the output for mystery(5)?
In one sentence, describe what the previous method calculates:
What is the computational complexity of the above method? Give an explanation.
4) 10 pts - What is the output of the following code?
element1 = 4;
element3 = 0;
element2 = element1 + 1;
queue.enqueue(element2);
queue.enqueue(element2+1);
queue.enqueue(element1);
element2 = queue.dequeue();
element1 = element2 + 1;
queue.enqueue(element1);
queue.enqueue(element3);
while (!queue.isEmpty());
{
element1 = queue.dequeue();
System.out.print(element1+”, “);
}
Output:
You have a doubly linked-list data structure to which you want to add some methods you will use to implement a queue. Some code is already done – defining the Node class, instance data, and the insertTail method.
public class MyDoublyLinkedList{
private class Node{
private String info = null;
private Node next = null;
private Node prev = null;
}
private Node head = null;
private Node tail = null;
public void insertTail(String s){
Node n = new Node();
n.info = s;
n.next = null;
n.prev = tail;
if (head == null)
head = n;
else
tail.next = n;
tail = n;
}
} // end of class MyDoublyLinkedList
5) 15 pts – add the method removeHead to class MyDoublyLinkedList – remove the first element from the linked list and return it.
public String removeHead()
{
}
6) (20 pts) – add a method CountOccurrences in MyDoublyLinkedList that counts the number of occurrences of the String s in the linked list. Implement this method iteratively.
public intcountOccurrences(String s)
{
} // end of method countOccurrences
7) (15 pts) – add a method CountOccurrences in the Node class that counts the number of occurrences of the String s in the linked list. Implement this method recursively. It would first be called on the head of the linked list.
private int countOccurrences(String s)
{
} // end of method countOccurrences