CS 2401 Test #2

Date: Thursday, October 29, 2009.

Name: ___________________________________________________________________

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

public void insertLast(T newClass)
 	LinkedListNode newNode;
	newNode = new LinkedListNode(newItem, first);
    if (first == null)
		first = newNode;
		last = newNode;
		last = newNode;

  1. Trace the execution of the code above and explain why it is incorrect.
  2. Write a correct implementation of the insertLast(T) method.

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:

(8 + 3) * (5 + 4) + 2 * 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 count of type int.
  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, 5, and 6, and then delete one element from the queue.

8. Using the class UnorderedLinkedList as defined in the textbook, consider the following Java statements:
UnorderedLinkedList list = new UnorderedLinkedList();
What is the output of this program segment?