Vectorized Test

  1. Explain, by reference to abstract data types, why there is a room behind the milk shelves in the supermarket from which the milk is restocked.

  2. It is possible to change into a different sweatshirt in public without offending anyone, but not to change into a different set of underwear. Explain in terms of abstract data types why this is the case.

  3. Suppose that you use a priority queue to keep track of homework assignments. Describe what criteria you would use in Assignment's compareTo() method.

  4. Read through the method below.

    public Stack stackInOrder(Queue queue) {
       Stack stack = new LinkedList();
       stack.push(new Integer(0));
       while(!queue.isEmpty()) {
          Integer i = (Integer)queue.dequeue();
          System.out.print(i + " ");
          if(i.intValue() == ((Integer)stack.peek()).intValue() + 1) {
          } else {
       return stack;

    Suppose that I call the method with the queue [3, 1, 5, 6, 4, 2] (the 3 is the first to be removed, and they are all Integers). What will be printed out? (Not what will be returned - note the System.out.print() in the loop)

  5. Suppose that I have an ArrayList of Integers, all with different values, in which I want to find the nth smallest number. So, for example, if my ArrayList is [5, 2, 9, 1, 7] and n = 3, then I would return 5; if n were 2, I would return 2.

    Fill in the code of the nthSmallest() method below. You should make use of one of the abstract data types we learned in this unit.

    public int nthSmallest(ArrayList list, int n) {

  6. Suppose that I have a LinkedList class which has a dummy node, and I want to write a method that will remove from it anything that is not an Integer value. Fill in the code of the ints() method below.
    (Think through carefully what should happen when I remove a node. If I have just removed my next, what node needs to be told to ints() now so that everything will be checked?)

    public void ints() {

  7. Read through the method below, which is for a LinkedList with a dummy node.

    public void lessIndex(int n) {
       if(next == null || ((Integer)next.value).intValue() <= n) {
          return 0;
       } else {
          return next.lessIndex(n) + 1;

    Suppose that I do list.lessIndex(2), with list as shown below. What will be returned?