Unit 8

Suppose the binarySearch method is called with an array containing 20 elements sorted in increasing order. What is the maximum number of times that the statement indicated by /* calculate midpoint */ could execute?

public static int binarySearch(int[] a, int target) {

int left = 0;

int right = a.length - 1;

while (left <= right) {

int mid = (left + right) / 2; /* calculate midpoint */

if (a[mid] < target) {

left = mid + 1;

}

else if (a[mid] > target) {

right = mid - 1;

}

else {

return mid;

}

}

return -1;

}

• 21

• 20

• 19

• 10

• 5

Which of the following are NOT true of insertion and selection sort?

• When an element is moved to the sorted list in insertion sort, it may move again if a smaller item is found.

• Selection sort is generally slower than insertion sort on a randomized list.

• When an element is moved in selection sort, it is put into a sorted position and will not move again.

• Insertion sort is generally faster for a nearly sorted array.

• Selection sort is generally faster for a reverse sorted array.

Consider the following implementation of the selection sort algorithm.

public static void selectionSort(int[] elements) {

for (int j = 0; j < elements.length - 1; j++) {

int minIndex = j;

for (int k = j + 1; k < elements.length; k++) {

if (elements[k] < elements[minIndex]) {

minIndex = k;

}

}

if (j != minIndex) {

int temp = elements[j];

elements[j] = elements[minIndex];

elements[minIndex] = temp; // Line 19 } } }

The following declaration and method call appear in a method in the same class as selectionSort.

int[] ss = {10, 9, 8, 7, 6}; selectionSort(ss);

How many times is the statement elements[minIndex] = temp; in Line 19 of the method executed as a result of the call to selectionSort?

• 1

• 2

• 3

• 4

• 5

Consider the following method, which implements a recursive binary search that returns an index in myList where target appears, if target appears in myList between the elements at indices low and high, inclusive; otherwise returns -1.

public static int bSearch(ArrayList<Integer> myList, int low, int high, int target) {

int mid = (high + low) / 2;

if (target < myList.get(mid)) {

return binarySearch(myList, low, mid - 1, target);

}

else if (target > myList.get(mid)) {

return binarySearch(myList, mid + 1, high, target);

} else if (myList.get(mid).equals(target)) {

return mid;

}

return -1;

}

Assume that inputList is an ArrayList of Integer objects that contains the following values.

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

What value will be returned by the call bSearch(inputList, 0, 9, 55)?

• -1

• 1

• 3

• 5

• 9

Consider the following instance variable and method.

private int[] numbers;

public static int mystery(int num) {

for (int k = 0; k < numbers.length; k++) {

if (numbers[k] > num) {

return k;

}

}

return numbers.length;

}

Which of the following best describes the contents of numbers after the following statement has been executed?

int m = mystery(n);

• The array is in sorted order up to position k.

• The smallest value is at position k.

• The largest value is at position k.

• All values in position 0 to m-1 are greater than num.

• All values in position 0 to m-1 are less than or equal to num.

Consider the following method.

public static String mystery(String[] arr, String[] arr2) {

for (String s : arr) {

boolean check = true;

for (String c : arr2) {

if (s.indexOf(c) < 0) {

check = false;

}

}

if (check) {

return s;

}

}

return null;

}

What would the following code segment print?

String[] s = {"night", "evening", "afternoon", "morning"}; String[] t = {"ni", "rn"}; System.out.println(mystery(s, t));

• night

• evening

• afternoon

• morning

• null

What is the worst case oder of complexity for a linear search?

• O(N)

• O(N log N)

• O(1)

• O(N2)

Consider a list:

{9, 2, 6, 8, -3}

If a linear search for the value 2 is performed, what will be returned?

• -1

• 5

• 1

• 2

Consider a list:

{-3, 5, 9, 12, 24, 31, 46, 48}

If a binary search for the value 33 is performed on this list, how many comparisons will occur before an answer is returned?

• 3

• 4

• 6

• 5

Consider a list:

{-3, 5, 9, 12, 24, 31, 46, 48}

If a binary search for the value 48 is performed on this list, how many comparisons will occur before an answer is returned?

• 8

• 3

• 1

• 4