CS 2401 Test #2

Date: Thursday, April 1, 2010.

Name: ___________________________________________________________________

1-2. The code below is an incorrect implementation of the search(T) method of the class LinkedListClass described in the textbook. 


public void search(T searchItem)
{
    LinkedListNode current;
    boolean found;
    current = first;
    found = false;
    while (current != null && !found)
    {
        current = current.link;
        if (current.info.equals(SearchItem))
           {found = true;}
    }
    return found;
}
  1. Trace the execution of the code above and explain why it is not always correct.
  2. Write a correct implementation of the search(T) method.
3. In the array and linked list implementations of a stack, write pieces of code for pushing an element "April" onto an arbitrary stack of strings. Trace both your codes on the example of a stack which originally has elements "January", "February", and "March", with "March" being the top element.
4-5. Consider the following arithmetic expression:

(4 - 1) * (20 - 10) - 10
  1. Rewrite the expression above using postfix notation
  2. Using the peek(), pop(), and push() methods, show how a stack can be used to support the evaluation of the expression in its postfix representation.
6. The implementation of the LinkedListClass in the textbook includes an instance variable called first of type LinkedListNode.
  1. Explain the role of this instance variable in supporting methods in the class.
  2. Explain the consequence(s) of LinkedListClass not having this instance variable.
7. Let us have a queue that represents the order in which a student works on CS 2401 Labs. Let us assume that this queue is implemented as an array of size 3. Originally, the queue is empty. Show, step-by-step, what will happen if we first add, to the queue, elements "Lab 1", "Lab 2", and "Lab 3", then delete "Lab 1" (done), then delete "Lab 2" (done), and then add "Lab 4" and "Lab 5".
8. Using the class UnorderedLinkedList as defined in the textbook, consider the following Java statements: 
UnorderedLinkedList list = new UnorderedLinkedList();
list.insertLast("January");
list.insertFirst(list.back());
list.insertLast("February");
list.insertFirst("March");
list.insertFirst("April");
list.insertLast(list.back());
list.print();
What is the output of this program segment?