T Naughton, NUIM Back to CS210 home

Laboratory Exam 2 - Lab Group B 09:00 Tuesday 19 December 2000

Answer all problems within 100 minutes for the full 25 marks. Switch your computers off. Remove everything but pens/pencils from your desks. Paper will be provided. Hand up this sheet with your answers.

Student's name.............................................................. Student number.............................................

Notes for Section A: Array-based data structures.

Write out the functions completely. You may not make use of classes from the java.util package.

Notes for Section B: Multiple choice questions (MCQs).

Use the MCQ answer sheet for Section B. Write both your name and student id. number on the MCQ sheet (remember to precede your number with a zero). If you make a mistake, just ask for a new sheet. Each MCQ question has only one fully correct option. Negative marking will be enforced: +1 for a correct answer, -0.25 for an incorrect answer, 0 for a non attempt. This means that randomly guessing answers will average a mark of zero.

Section A: Array-based data structures.

Q1 Write three Java constructors for a class MyClass. (MyClass has a private data member array[] that is an array of Comparables and also has a public method toArray() that returns a reference to a copy of array[]'s references.) The first constructor you must write, the default constructor MyClass(), sets array[]'s length to zero. The conversion constructor, MyClass(Comparable e[]), copies e[] into array[]. The copy constructor, MyClass(MyClass m), copies the private array[] data member of m. [4 marks]

Q2 Write a Java function that takes a sorted array of Comparables called array[] and a Comparable e and returns true if e is in the array, false otherwise. Your algorithm must make no more than O(log n) comparisons in the worst case. [5 marks]

Q3 Write a Java function that takes two sorted unique-valued arrays of Comparables called a[] and b[], and returns a (unique-valued and sorted) merged array. Specificially, the returned array should be sorted, be the exact length to accomodate its elements, contain all elements that were in a[] and b[], and only contain unique elements (if an element is in both a[] and b[] then it appears only once in the returned array). [6 marks]

Section B: Multiple choice questions (MCQs).

Q1 Searching a full array for an element that is definitely in the array requires (n-1) comparisons in the worst case, where n is the length of the array. How many comparisons in the worst case if the array is not full?

(a) 1
(b) 2
(c) n-1
(d) n-2
(e) none of the above

(a) =O(log n)
(b) =O(n²)
(c) =O(2 + 4 + 3)
(d) all of the above
(e) none of the above

(a) O(log n)
(b) O(n)
(c) O(1)
(d) n-1
(e) none of the above

(a) O(log n)
(b) O(n)
(c) O(1)
(d) n-1
(e) none of the above

(a) O(log n) copy operations and O(n) comparisons between elements
(b) O(1) copy operations and O(n) comparisons between elements
(c) O(n) copy operations and O(log n) comparisons between elements
(d) O(n) copy operations and O(n) comparisons between elements
(e) none of the above

Q6 Adding an element to an array, that does not allow duplicates, requires how many copy operations in the worst case (assume the array is not yet full)?

(a) O(n) copy operations
(b) O(n - 1) copy operations
(c) O(log n) copy operations
(d) ⁿ/₂ copy operations
(e) none of the above

MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(5));
s.push(new Integer(6));
s.push(new Integer(7));
q.enqueue(s.pop());
q.enqueue(new Integer(5));
q.enqueue(new Integer(6));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());

(a) 567
(b) 556
(c) 765
(d) 755
(e) none of the above

MyQueue q;
MyStack s;
q = new MyQueue();
s = new MyStack();
s.push(new Integer(5));
s.push(new Integer(6));
s.push(new Integer(7));
q.enqueue(s.pop());
q.enqueue(s.pop());
q.enqueue(new Integer(5));
q.enqueue(new Integer(6));
System.out.print(q.dequeue());
s.push(q.dequeue());
System.out.print(s.pop());
System.out.print(s.pop());
System.out.print(s.pop());

(a) 5675
(b) 7655
(c) 7565
(d) 7556
(e) none of the above

Q9 What will be the result of executing the following function when, initially, a is an array of length 3 of Integers with data values {5, 6, 7} and b is an Integer with data value 6?

public static void example(Object a[], Object b) {
  /* This is not a useful comment.
  */
  int count; // a counter
  count = 0;
  while (count < a.length) {
    if (!a[count].equals(b)) {
      System.out.print(a[count].toString());
      a[count] = b;
    }
    count++; // this is equivalent to "count = count + 1"
  }
}

(a) "567" will be printed to the screen and a will be {5, 6, 7}
(b) "6" will be printed to the screen and a will be {5, 7}
(c) "57" will be printed to the screen and a will be {6, 6, 6}
(d) "666" will be printed to the screen and a will be {5, 6, 7}
(e) none of the above

(a) ⁿ/₂
(b) éⁿ/₂ù
(c) O(log n)
(d) n-1
(e) none of the above