Name: ______
Midterm 2
CS 20
Winter 2009
Short Answer:_____/25
Output:_____/25
removeHead:_____/15
iterative countLessThan_____/20
recursive countLessThan_____/15
Total:_____/100
1) Write the base case and recursive case of each of the following problems (5 pts each):
a) Calculating the value log2(x)
Base Case:
Recursive Case:
b) Calculating the value 2x
Base Case:
Recursive Case:
c) Sum all of the numbers in an array..
Base Case:
Recursive Case:
2) 10 pts - Write the recursive method, in Java, to calculate the value log2(x). If you don’t know how to do that, write the recursive version of 2x for 90% credit.
public static int logTwoOfX(int x)
{
}
3) (15 pts) (2-3-5-5)
public static int mystery(int x)
{
if (x <= 0)
return 0;
else
return (mystery(x-1) - 5);
}
What is the output for mystery(1)?
What is the output for mystery(3)?
Give the equation of what mystery 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 = 7;
element3 = 3;
element2 = element1 + 2;
queue.enqueue(element2);
queue.enqueue(element2+4);
queue.enqueue(element1);
element2 = queue.dequeue();
element1 = element2 + 2;
queue.enqueue(element1);
queue.enqueue(element3);
while (!queue.isEmpty());
{
element1 = queue.dequeue();
System.out.print(element1+”, “);
}
Output:
You have a circular 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. You may assume standard setter and getter methods in the Node class if you wishIf you don’t remember what a circular linked list is, make a note and implement problems 5, 6, and 7 for a doubly linked list with both head and tail pointer. You will receive 85% credit on problem 5 and full credit on the rest.
public class MyCircularLinkedList{
private class Node{
private Comparable info = null;
private Node next = null;
public Node (Comparable c)
{ info = c;}
}
private Node tail = null;
public void insertTail(Comparable c){
Node n = new Node(c);
if (tail == null)
tail = n;
else
{
n.next = tail.next;
tail.next = n;
tail = n;
}
}
} // end of class MyCircularLinkedList
5) 15 pts – add the method removeHead to class MyCircularLinkedList – remove the first element from the linked list and return it.
public Comparable removeHead()
{
}
6) (20 pts) – add a method countLessThan in MyCircularLinkedList that counts the number of elements in the linked list that are considered smaller than the input parameter c. Think carefully about what “smaller” means with respect to the Comparable interface. Implement this method iteratively.
public int countLessThan(Comparable c)
{
} // end of method countLessThan
7) (15 pts) – add a method countLessThan in MyCircularLinkedList that counts the number of elements in the linked list that are considered smaller than the input parameter c. Implement this method recursively. Fill in the code for both the public method and the private helper method.
public int countLessThan (Comparable c)
{
}
// fill in the input parameters and the code for the helper method
private int countLessThanRec(
{
} // end of method countLessThan