T Naughton, NUIM
Back to CS210 home

Laboratory Exam 2

The following questions are representative of the questions that will appear in the exam. In the exam, there will be three questions in Section A and ten questions in Section B.

Laboratory Exam 2 - Lab Group X XX 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.

QA Write a Java function that takes an array of Objects as an argument and returns an array of the same length but with the elements in reverse order.

QB Write a Java function that takes an array of Objects called o[] and returns a single String containing the string representations of every second element (starting at index 0) of o[]. Assume all Objects have a toString() method.

QC 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. [Java solution]

QD Given a solution to the above problem, how would the constructors need to be changed if class MyClass had a public method asArray() instead of the aforementioned toArray(). asArray() returns a copy of the reference to array[] rather than a copy of the references to array[]'s elements.

QE Write a Java function that takes an array of Objects called o[] and returns a newly allocated array, of length é(o.length)/2ù, filled with references to the first half of the elements of o[].

QF Write a Java function that takes an array of Comparables and returns true if the array is sorted in ascending order, otherwise false.

QG Write a Java function that takes a sorted array of Comparables and returns true if the array is sorted in ascending order, and false if it is sorted in descending order.

QH 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. [Java solution]

QI 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). [Java solution]

QJ Write a Java function that takes two sorted unique-valued arrays of Comparables called a[] and b[], and returns a (unique-valued and sorted) array of all elements in a[] that do not appear in b[]. Specificially, the returned array should be sorted, be the exact length to accomodate its elements, contain all elements that were in a[] but not in b[], and only contain unique elements (each element appears only once in the returned array).

Section B: Multiple choice questions (MCQs).

QA Inserting an element into an arbitrary array of length n that is full requires how many copy operations and how many comparisons between elements in the worst case? (Assume you must add it to the array and cannot simply return an error message.)

(a) O(log n) copy operations and O(n) comparisons between elements
(b) O(n) copy operations and O(1) comparisons between elements
(c) O(1) 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

(a) O(log n) copy operations and O(n) comparisons between elements
(b) O(n) copy operations and O(1) comparisons between elements
(c) O(1) 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

(a) O(n) comparisons between elements
(b) n - 1 comparisons between elements
(c) O(log n) comparisons between elements
(d) ⁿ/₂ comparisons between elements
(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));
System.out.print(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());

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

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) O(log n), where n is the length of the array
(b) (ⁿ/₂) + n + 1 = (³/₂)n + 1, where n is the length of the array
(c) O(n), where n is the length of the array
(d) all of the above
(e) none of the above