CSC 241- Exam 2        Name:

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

1. We can store Objects of any class in either implementations of Stack. True/False.
   
2. The dynamic version of Queue is better than its fixed version when you don't know how many elements you need to store in it. True/False.
   
3. You allocate one node in a linked list for each value inserted in it. True/False.
   
4. You can never remove the last node in a linked list. True/False.
   
5. interface and class mean the same thing in java. True/False.
   
6. orderedIntList implements intList, not extends it. True/False.
   
7. node header_; is a declaration in intList. Since there is no private or protected qualifier on header_, it can be accessed in any application thats uses intList. True/False.
   
8. current_ of an intList object always references the last node successfully inserted into it. True/False.
   
9. Consider A as an existing class and B as a class that extends it. Answer the following:
   • A Inherits B's methods.True/False.
     
   • You MAY NOT introduce new fields in B that already exist in A. True/False.
     

(30 Points) 2. Consider the following conceptual representation for a linked list. head references the first node in the list.

                       -----      -----      -----         ----- 
                      | 434 |===>| 231 |===>| 111 |===>...| 234 |===||
                       -----      -----      -----         ----- 
                      head

Here is the definition of our node class:

             class Node {
                int element_;
                Node next_;
            Node (Node n, int e) {
                  next_=n;
              element_=e;
                }
             }

1. What is head_.next_.element_ in the above list?
   
   
2. Assume Node temp; Write the instruction(s) that would make temp reference the 3rd node in the above list.
   
   
3. For the above list, write the Java instruction(s) that would create a node with the number 222 and place it between 434 and 231.
   
   
   
4. Write a method count that returns how many nodes there are in a linked list referenced by head. Start a temporary variable at the head of the list and loop as long as the temporary variable is not null. Use an int variable to count the number if iterations and return it at the end.

   
                int count (Node head) {
   
   
   
   
   
   
                }
   

Here are the definitions of node and intList classes from lab4:

public class node {
   int element_;
   node next_;
   node (int e, node n)
}

public class intList
{
  node header_;
  node current_;

  public intList( )

  public boolean isEmpty( )
  public void makeEmpty( )
  public void insert( int x ) throws Exception
  public void insertAtBeginning( int x )
  public boolean find( int x )
  public void remove( int x ) throws Exception
  public boolean validCurrent( )
  public int retrieve( )   throws Exception
  public void first( )
  public void advance( )
  public String dump ()
}

(10 Points) 3.Write a boolean method isLast for the intList class. This method throws an exception if current is invalid; otherwise, the next_ of the current node should be checked and either true or false returned based on it being null or not.

(10 Points) 4.Write a method update (int newValue) for the intList class. This method throws an exception if current is invalid; otherwise, it places newValue in the element_ of the current node.

(20 Points) 5. Suppose we have an application that maintains a list of salaries in an intList variable (list) with values like 10000, 40000, etc. Understand that you are in an application and have no access to current_ or header_ of list. Assume that the method update exists in intList. Write a code segment that loops through and updates every salary by giving each a 10% raise.

(10 Points) 6. Assume that the intList L has the following list in it, note that current_ is on the 1st node when this method is called:

                      current_
                       -----      -----      -----      ----- 
                      | 134 |===>| 231 |===>| 311 |===>| 434 |===||
                       -----      -----      -----      ----- 
                      head_

     int test2 (int i, intList L) {
       if (L.invalidCurrent()) return -1;
       try {
           if (L.retrieve() == i) return 0;
       }
       catch (Exception e){}
       
       int temp = test2(i,L); 
       if (temp == -1)
          return -1;
       else
          return temp+1;
     }

1. What would this method return as an answer, if called with test2(311,L)?
2. What would this method return as an answer, if called with test2(312,L)?