SAMPLE A 2001 Paper CS210 T Naughton, CS NUIM, March 2001 Section A.I ----------- 1 e 2 b 3 b 4 a 5 c 6 b 7 b 8 a 9 c 10 e 11 d 12 a 13 b 14 a 15 d Section A.II ------------ Question 1 [20 marks] int findSubseq(int a, int b, int c[]) { /* Return the index in c of the first occurrence of b ** consecutive copies of a. Otherwise return -1. ** Assume c will not be null. */ int countc; // counter for c int occ; // number of occurrences of a found boolean found; // found b consecutive copies of a? countc = 0; // start searching at the beginning of c found = false; // assume not found at beginning while ((countc < (c.length-b+1)) && (!found)) { occ = 0; while ((c[countc] == a) && (occ < b)) { occ++; // inc number of a's found countc++; // move on to next index } found = (occ == b); countc++; } if (found) { return (countc-b-1); } else { return -1; } } Question 2 [20 marks] public static MyQueue fn(MyQueue q) { /* This function returns a queue containing every third ** element in the reverse of q. */ MyStack s; // holds contents of q in reverse int count; // counter // copy queue into stack s = new MyStack(); while (!q.isEmpty()) { s.push(q.dequeue()); } // Pop every third element (q will be empty) count = 0; while (!s.isEmpty()) { if ((count % 3) == 0) { q.enqueue(s.pop()); } else { s.pop(); // discard } count++; } return q; } Question 3 [20 marks] NodeA mergeLists(NodeA a, NodeA b) { /* Return a list that contains copies of references to all elements ** of list a and list b, without duplicates, while preserving the ** ascending order. Assume neither list is empty. */ NodeA newlist; // reference to the merged list of elements NodeA tempref; /* Reference to traverse the merged list. Always ** points to the last element added to the list. */ /* The easiest thing is to let newlist to point to a temporary ** node that can be removed later. */ newlist = new NodeA(null); tempref = newlist; // initialise tempref to this node /* Perform a merging operation with the two lists, making a copy of ** each unique element. */ while ((a != null) || (b != null)) { /* Since both lists are sorted in ascending order, we can add to ** the merged list any element in one list that is lower than the ** lowest remaining element in the other list. If we find the ** same value in each, add one of them. ** If one list has been exhausted (== null), add all remaining ** elements of the other. */ if ((b == null) || (a.getData().compareTo(b.getData()) < 0)) { /* Since the current element in a is smaller than the smallest ** remaining element of b (or b is null), it cannot be in b. ** Add elements that appear only in list a. ** It is important that the `||' rather than the `|' logical OR is ** used here to avoid a runtime null reference exception occurring. */ tempref.setNext(new NodeA(a.getData())); // append a new node tempref = tempref.getNext(); // advance ref to this new node a = a.getNext(); // advance ref to next node to be tested } else if ((a == null) || (a.getData().compareTo(b.getData()) > 0)) { /* Since the current element in b is smaller than the smallest ** remaining element of a (or a is null), it cannot be in a. ** Add elements that appear only in b. ** It is important that the `||' rather than the `|' logical OR is ** used here to avoid a runtime null reference exception occurring. */ tempref.setNext(new NodeA(b.getData())); // append a new node tempref = tempref.getNext(); // advance ref to this new node b = b.getNext(); // advance ref to next node to be tested } else { /* The element appears in both a and b. Add one of them and ** advance both references. */ tempref.setNext(new NodeA(a.getData())); // append a new node tempref = tempref.getNext(); // advance ref to this new node a = a.getNext(); b = b.getNext(); } } /* Return the newly created list (ignoring the dummy node we created ** at the beginning). */ return newlist.getNext(); }