SAMPLE B 2001

Paper CS210

T Naughton, CS NUIM, March 2001



Section A.I

-----------

1  b

2  b

3  c

4  c

5  c

6  b

7  e

8  d

9  c

10 b

11 c

12 e

13 c

14 b

15 e





Section A.II

------------



Question 1(a) [10 marks]



Object [] centreElements(Object a[]) {

  /* Return the central floor(a.length/2) elements of a.

  ** Assume a will not be null.

  */

  int aref;          // reference to a's elements

  Object newArray[]; // newly created array

  int newref;        // reference to newArray's elements



  newArray = new Object[(int)(a.length/2)]; // create the new array



  // start copying the references

  aref = (int)((a.length - newArray.length)/2);

  newref = 0;

  while (newref < newArray.length) {

    newArray[newref] = a[aref];

    newref++;

    aref++;

  }

  return newArray;

}





Question 1(b) [10 marks]



int [] mySort(int a[]) {

  /* Return array a sorted in ascending order.

  ** This method makes a pass through the array for each index i. At

  ** each pass i's element is swapped with each smaller element found

  ** to the right of i. After each pass, index i contains its final

  ** sorted element.

  */

  int i; // index currently under consideration

  int c; // counter for all indexes greater than i

  int temp;   // temporary storage



  i = 0;

  while (i < a.length) {

    c = i + 1;

    while (c < a.length) {

      if (a[c] < a[i]) {

        temp = a[i];

        a[i] = a[c];

        a[c] = temp;

      }

      c++;

    }

    i++;

  }

  return a;

}





Question 2 [20 marks]



public static MyQueue fn(MyQueue q, int n) {

    /* This function returns a queue with (in order) the

    ** last n elements of q. If q contains less than n

    ** elements, return a queue with the elements

    ** unchanged. 

    */

    MyStack s1; // holds contents of q in reverse

    MyStack s2; // holds last n elements in correct order

    int count;  // a counter 0..n



    // copy queue into stack

    s1 = new MyStack();

    while (!q.isEmpty()) {

      s1.push(q.dequeue());

    }



    /* Pop n elements into s2. Take into account situation

    ** where n is greater than size of s1.

    */

    s2 = new MyStack();

    count = 0;

    while ((count < n) && (!s1.isEmpty())) {

      s2.push(s1.pop());

      count++;

    }



    // pop all elements into q (q will be empty)

    while (!s2.isEmpty()) {

      q.enqueue(s2.pop());

    }

    return q;

  }





Question 3 [20 marks]



  public boolean isElementOf(Comparable e) {

    /* Return true if e is in the set, otherwise false.

    ** If e is null return false.

    */

    boolean found; // has element been found?

    LLSNode temp;  // reference to set elements

    if ((e == null) || (pList == null){

      return false;

    } else {

      found = false;

      temp = pList;

      while ((temp != null) && (!found)) {

        found = temp.getData().equals(e);

        temp = temp.getNext();

      }

      return found;

    }

  }



  public Comparable min() {

    /* Return the minimum element. If the set is empty return null.

    */

    if (pList == null) {

      return null;

    } else {

      return pList.getData();

    }

  }