CS 2401 Test #2

Date: Friday, October 30, 2009.

Name: ___________________________________________________________________

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


public void insertFirst(T newClass)
{
    LinkedListNode newNode;
    newNode = new LinkedListNode(newItem, first);
    if (last==null)
       first=newNode;
    count++;
}
  1. Trace the execution of the code above and use the trace to explain why the code is incorrect.
  2. Write a correct implementation for the method insertFirst(T) .
3. In the linked list implementation of a stack, write a code for pushing an element 1. Trace your code on the example of a stack which originally has elements 2 and 3, with 2 being the top element.
4-5. Consider the following arithmetic expression:

(50 + 3) * 3 + (5 +4) * 2
  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 last 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. In the array implementation of a queue, show what will happen if you first add to the queue elements 3, 4, and 5, and then delete two elements from the queue.
8. Using the class UnorderedLinkedList as defined in the textbook, consider the following Java statements: 
UnorderedLinkedList list = new UnorderedLinkedList();
list.insertFirst(2);
list.insertLast(1);
list.insertFirst(list.back());
list.insertLast(list.back());
list.insertFirst(6);
list.insertLast(5);
list.print();
What is the output of this program segment?