CSC 241- Exam 2        Name:

(20 Points) 1. Respond to the following true/false questions.

1. We can store any Object in a fixedStack. True/False.
   
2. The fixed version of Queue is better than its dynamic version when you don't know what your storage space needs are (i.e. how much room to put aside for the elements). True/False.
   
3. The memory alloacted in a dynamic data structure will grow and shrink as data is added or removed from it, respectively.
4. You can have constructors in an interface. True/False.
   
5. You can have constructors in a class. True/False.
   
6. Consider A as an existing class and B as a class that extends it. Answer the following:
   • B Inherits all methods and fields from A. True/False.
     
   • You may override any methods from A in class B by writing a method with the same name, parameters, and return value in B. True/False.
     

(30 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 (Node n, int e) {
                  next_=n;
              element_=e;
                }
             }

1. What is the value of head.next_.next_.element_?
   
   
2. What is the value of head.element_?
   
   
3. For the above list, write the Java instruction(s) that would create a node with the string "there" and place it before the nodes that contain "hello". Keep in mind that head must reference the new node and the next_ of the new node must refernce the "old head".
   
   
   
4. Write a method removeLast that removes the last node from the list referenced by head. Assume that there are at least two nodes in the list; write a method that starts a temporary variable at the head of the list and loops as long as the next_ field of the next node is not null, at that time, next_ of the node referenced by the temporary variable is set to null.

   
                boolean removeLast (Node head) {
   
   
   
   
   
   
                }
   

(20 Points) 3. Assume the following Queue interface as we used it in Lab#3:

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

Write a method that removes all elements of a Queue, one at a time, and return the last one found on the queue. This method returns null if the queue is empty. Don't forget your try/catch.

     public Object remove_all_and_return_last(Queue q) {







         return ----;
     }

(30 Points) 4. 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 ()
}

1. Suppose we have an application that maintains a list of strings in a stringLinkedList variable. The following method displays the content of the list. Change the method so that it would also remove every element in the list.

   
               // Print contents of theList
               static public void printList( stringLinkedList theList ){
                 stringLinkedListItr itr = new stringLinkedListItr( theList );
                 
                 if( theList.isEmpty( ) )
                   System.out.println( "Empty list" );
                 else
                   for( ; itr.validCurrent( ); itr.advance( ) )
                     System.out.println( itr.retrieve( ) );
               }
   

   
   
   
   

   ---

2. Add a new method to stringLinkedListItr that would make current_ reference the last node in the list. Keep in mind that you have a current_ field which is a ListNode as well as a myLists_ which is a stringLinkedList. Also remember that stringLinkedList has a head_ field that refernences the 1st node in the list. Assume, that there is at least one node in the list.