CS 2401 Test #2

Date: Monday, March 29, 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 (!found)
        {if (current.info.equals(SearchItem))
           found = true;
        else current = current.link;}
    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 "Monday" onto an arbitrary stack of strings. Trace both your codes on the example of a stack which originally has elements "Saturday" and "Sunday", with "Sunday" being the top element.
4-5. Consider the following arithmetic expression:

(3 - 29) * (20 - 10) + 10 - 11 + 20
  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 instance variables count of type int and last of type LinkedListNode
  1. Explain the role of these instance variable in supporting methods in the class.
  2. Explain the consequence(s) of LinkedListClass not having these instance variables.
7. Let us have a queue that represents the order in which a student prepares for tests at different classes. Let us assume that this queue is implemented as an array of size 4. Originally, the queue is empty. Show, step-by-step, what will happen if we first add, to the queue, elements "CS 2401", "Discrete Math", and "History", then delete "CS 2401" (test is over), then delete "Discrete Math" (test is over), and then again add "CS 2401" and "Discrete Math" (test 2 is coming).
8. Using the class UnorderedLinkedList as defined in the textbook, consider the following Java statements: 
UnorderedLinkedList list = new UnorderedLinkedList();
list.insertLast("Saturday");
list.insertFirst(list.back());
list.insertLast("Sunday");
list.insertFirst("Monday");
list.insertFirst("Tuesday");
list.print();
list.insertLast(list.front());
What is the output of this program segment?