(21 Points) 1. Respond to the following true/false questions.
(24 Points) 2. Consider the following conceptual representation for a linked list. head references the first node in the list. Suppose that each node points to both the next and the previous nodes as shown.
---- ---- ---- ---- --
||===|hello|<===>|where|<===>|does|<===>|this |<===>|go|===||
---- ---- ---- ---- --
head
Here is the definition of our node class:
class Node {
String element_;
Node next_;
Node prev_;
Node (Node n, Node p, int e) {
next_=n;
prev_=p;
element_=e;
}
}
boolean find (Node head, String s) {
}
(15 Points) 3. Assume that the following array variable L and the
size variable exist.
--------------------------------------------
L | 134 | 322 | 11 | 343 | 88 | size=5
--------------------------------------------
0 1 2 3 4
Consider the recursive method test2
and assume that it has access to both L and size.
1 int test2 (int i) {
2 if (i==size) return L[i];
3 int temp = test2(i+1);
4 if (L[i] < temp)
5 return L[i];
6 else
7 return temp;
8 }
Complete the trace table below and give the final answer that this
method return is.
Line# Statement/Method Header Return Value
1 int test2(0)
3 int temp=test2(1)
1 int test2(1)
3 int temp=test2(2)
(20 Points) 4. Assume the following Stack & Queue interfaces as we used them in Lab#3:
public interface Stack {
public boolean empty();
public boolean full();
public Stack push (Object x) throws Exception;
public Stack pop() throws Exception;
public Object peek() throws Exception;
}
public interface Queue {
public boolean empty();
public boolean full();
public Queue enqueue(Object x) throws Exception;
public Queue dequeue() throws Exception;
public Object peek() throws Exception;
}
Complete the following method which is suppose to remove all elements of a Queue, one at a time, and place them in a newly created dynamicStack and return that Stack.
public Stack move_all(Queue q) {
Stack s = new dynamicStack();
return s;
}
(20 Points) 5. Here are the definitions of the stringLinkedList and the stringLinkedListItr classes:
public class stringLinkedList
{
public stringLinkedList( )
public boolean isEmpty( )
public void makeEmpty( )
}
public class stringLinkedListItr {
public stringLinkedListItr( stringLinkedList anyList )
public void insert( String x ) throws Exception
public void insertAtBeginning( String x )
public boolean find( String x )
public void remove( String x ) throws Exception
public boolean validCurrent( )
public String retrieve( )
public void first( )
public void advance( )
public String dump ()
}
Suppose we have an application that maintains a list of strings in a stringLinkedList variable. Write a method that finds the 1st occurence of a string in the list that starts with the letter 'H' and returns that string.
You need to create an iterator and use it to visit all elements in the list starting from the 1st one; once, the string returned from the iterator starts with an "H", that string is returned.
Keep in mind that charAt is the string method that returns the character in a specified location of the stirng. Also, keep in mind that the methods in stringLinkedListItr are what you have to work with.
String findH(stringLinkedList L) {
}