CS 2401 Test #2

Date: Thursday, April 2, 2009.

Name: ___________________________________________________________________

1. Suppose that a linked list is implemented as a node

public class Node{
  public int info;
  public Node link;
}
Write a piece of code for deleting the first element of the list. Feel free to assume that the list is not empty. Draw the corresponding pictures on the example of a list consisting of integers 5 and 7.













































2. Suppose that you already have an implementation of a stack, with operations push and pop implemented. Write down a method that uses the stack operations to check that in a given expression, every opening bracket [ has a matching closing bracket ]. Trace your code on the example of an expression [a[bc]].




















































3. In the array implementation of a stack, write a code for popping an element. Trace your code on the example of a stack which originally has elements 1 and 2, with 1 being the top element.


























































4. In the linked list implementation of a stack, write a code for popping an element. Trace your code on the example of a stack which originally has elements 1 and 2, with 1 being the top element.

























































5. In the array implementation of a queue, show what will happen if you first enqueue elements 3 and 4, and then dequeue the first element.


























































6. What is an abstract data type (ADT)? What are the advantages of using ADTs? Give an example of two different implementation of the same ADT. In Java, how do we implement an ADT so as to guarantee that we can access the corresponding objects only via appropriate operations?