Unit 8 - Searching and Sorting

Consider the following method:

public String mystery(String myString, int index) {

   if (index >= myString.length()) {

      return myString;

   }

    return myString + mystery(myString.substring(index), index + 2);

}

What is printed as a result of executing the following line of code?

System.out.println(mystery("CSA is the best!", 0));

• CSA is the best!

• CSA is the best!CSA is the best!A is the best! the best!est!

• CSA is the best! A is the best! The best! est! est!

• CSA is the best!A is the best! The best!est!

• CSA is the best!A is the best! The best!

Consider the code to the left:

Which of the following replacements for /* missing code */ will cause the loop in the method to run the maximum number of iterations (method runs in the worst case)? 

I. {11, 28, 5, 25, 86}

II. {86, 25, 11, 5, 28}

III. {11, 25, 5, 99, 28}

• I only

• II only

• III only

• I and II only

• I and III only

The following method is intended to return the index of the location of target in the array arr, -1 otherwise:

 public int find(String[] arr, String target) {

   for (int i = arr.length - 1; i >= 0; i--) {

     if (target.equals(arr[i])){

       return i;

     }

     return -1;

   }

   return -1;

 }

Which of the following best explains why the method does not work as intended?

•  There are two return statements that return  -1

•  It starts traversing at the end of the array

• When the target is not the last element, it returns -1 instead of traversing the rest of the array

• The array index goes out of bounds

• There is no error; it works as intended

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

• 4

• 5

• 9

• 10

• 11

Consider the method to the left, which implements a recursive binary search that returns an index in arr where the value x appears if x appears in arr between arr[left] and arr[right], inclusive; otherwise returns -1.

The following code segment appears in a method in the same class as bSearch.

int[] nums = {2, 3, 3, 6, 7, 9};

int result = bSearch(nums, 0, nums.length - 1, 3);

What is the value of result after the code segment has been executed?

• 1

• 2

• 3

• 4

• 5

Consider the method to the left, 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.

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

[0, 5, 10, 15, 20, 25, 25, 25, 25]

What value will be returned by the call binarySearch(inputList, 0, 8, 25)?

• -1

• 5

• 6

• 7

• 9

 Consider the sort method to the left. This method correctly sorts the elements of array data into increasing order.

Assume that selectSort is called with the array {16, 13, 12, 50, 40, 10}. What will the value of data be after three passes of the outer loop (i.e., when j = 2 at the point indicated by /* End of outer loop */) ?

•  {10, 12, 12, 50, 40, 10}

• {10, 12, 13, 16, 40, 50}

• {10, 13, 12, 50, 40, 16}

•  {10, 12, 13, 50, 40, 16}

•  {10, 12, 13, 50, 40, 10}

Consider the correct implementation of the selection sort algorithm to the left.

The following declaration and method call appears in the same class as selectSort.

int[] vals = {5, 10, 2, 1, 12};

selectSort(vals);

How many times is the statement minIndex = k; in line 11 of the method executed as a result of the call to selectSort ?

• 0

• 1

• 2

• 3

• 4

Consider the following two statements about insertion sort:

I. After k iterations through the outside loop, the first k elements are sorted.

II. After k iterations through the outside loop, the first k elements are the smallest elements in the list.

• Statement I and II are both true

• Statement I is true, and statement II is false

• Statement I is false, and statement II is true

• Statements I and II are both false

Consider the following code segment, which appears in a method in the same class as mergeSortHelper and merge.

 int[] numbers = {18, 4, 8, 11};

 int[] temp = new int[numbers.length];

 mergeSortHelper(numbers, 0, numbers.length - 1, temp);

How many times will the merge method be called as a result of executing the code segment?

• 1

• 2

• 3

• 4

• 5