QUIZ

CHAPTER 15

15.1 If the linear search in Section 15.2 was to be used to search an array of integers, what line would you change?

(a) throw new ItemNotFoundException();
(b) for (int i=0; i<a.length;i++)>
(c) if (x.equals(a[i])
(d) none

15.2 In the following list of numbers:

8 17 25 35 41 52 60 75 86

how many comparisons would binary search take to find 35?

(a) 4
(b) 3
(c) 5
(d) 2

15.3 Binary search is always faster than linear search when the item being sought is

(a) at the end of the list
(b) at the start of the list
(c) not in the list
(d) in the second half of the list

15.4 If we pushed the numbers 1 to 10 onto two stacks, S1 and S2 alternately, and then took all of S1 followed by all of S2 off, what would be printed out? The code is:

Stack S1 = new Stack(5);
Stack S2 = new Stack(6);
for (int i = 1; i<=10; i+=2) {
S1.push(i);
S2.push(i+1);
}
while (!S1.empty())
System.out.print(S1.pop()+" ");
while (!S2.empty())
System.out.print(S2.pop()+" ");

(a) 10 9 8 7 6 5 4 3 2 1
(b) 9 10 7 8 5 6 3 5 1 2
(c) 9 7 5 3 1 10 8 6 4 2
(d) 10 8 7 6 4 2 9 7 5 3 2 1

15.5 In the doctor's waiting room example (15.3), assume that each time period is 2 minutes. In the run shown here, how many minutes has the patient now first in the queue been waiting when the simulation ends?

(a) 2
(b) 12
(c) 10
(d) 20

15.6 To add a new item somewhere in the middle of a linked list, we

(a) have to iterate from the front to find the right place to use add(index, object)
(b) answer (a) or could maintain the current position and use it if relevant with add(index, object)
(c) use contains to find the right position as a reference and use that
(d) use binarySearch to find the right position and then use add(index, object)

15.7 In the waiting room example (15.3) how many time slots did patient number 12 wait before seeing the doctor?

(a) 10
(b) 9
(c) 11
(d) 1

15.8 The technique whereby a method can call itself is called

(a) iteration
(b) recursion
(c) introspection
(d) inverstion

15.9 Give a definition of a new bit set that will keep track of all courses taken by anyone in the training schedules example (15.5).

(a) Bitset allCourses = new BitSet (courseMax);
(b) BitSet allCourses [] = new BitSet (courseMax);
(c) Bitset allCourses = new BitSet [courseMax];
(d) BitSet allcourses.setMax (courseMax);

15.10 What would be a statement that can be added to the readIn method to update this set of all courses while a student's course particulars are being processed?

(a) allCourses.bitOn(c)
(b) allCourses [c].set()
(c) allCourses.set(c)
(d) none of these