# 7.11.5. Medium Search/Sort Multiple Choice Questions¶

These problems are similar to those you will see on the AP CS A exam.

7-11-5-1: Which of the following correctly shows the iterations of an ascending (from left to right) insertion sort on an array with the following elements: {7,3,8,5,2}?

• {3,7,8,5,2}, {3,7,8,5,2}, {3,5,7,8,2}, {2,3,5,7,8}
• The insertion sort starts at index 1 and inserts each value into the sorted list to the left by moving any larger values right.
• {2,3,8,5,7}, {2,3,8,5,7}, {2,3,5,8,7}, {2,3,5,7,8}
• This would be true if it was a selection sort.
• {3,7,8,5,2}, {3,5,7,8,2}, {2,3,5,7,8}
• This looks like an insertion sort, but it is missing one step.
• {2,3,8,5,7}, {2,3,5,8,7}, {2,3,5,7,8}
• This looks like a selection sort, but it is missing one step.
• {2,7,3,8,5}, {2,3,7,8,5}, {2,3,5,7,8}
• This is more like a selection sort, but not a correct one.

You can step through an insertion sort with this data by clicking on the following Ex-12-8-1.

7-11-5-2: What is printed when the following main method is executed?

public class Searcher
{
private int[] arr = {1,3,5,8,9};

public int mystery(int low, int high, int num)
{
int mid = (low + high) / 2;
if (low > high) {
return -1;   }
else if (arr[mid] < num) {
return mystery(mid + 1, high, num);   }
else if (arr[mid] > num) {
return mystery(low, mid - 1, num);   }
else
return mid;
}

public static void main(String[] args)
{
Searcher s = new Searcher();
System.out.println(s.mystery(0,4,3));
}
}

• -1
• This would be true if the third value was something that wasn't in the array.
• 0
• This would be true if the third value was 1
• 1
• This is a binary search and it returns the index of the value 3, which is 1.
• 2
• This would be true if the third value was 5.
• 3
• This would be true if the third value was 8.

You can step through the code above by clicking on the following Ex-12-8-2.

7-11-5-3: Which of the following correctly shows the iterations of an ascending (from left to right) selection sort on an array with the following elements: {10, 6, 3, 2, 8}?

• {6,10,3,2,8}, {3,6,10,2,8}, {2,3,6,10,8}, {2,3,6,8,10}
• This would be true if it was an insertion sort.
• {6,10,3,2,8}, {3,6,10,2,8}, {2,3,6,8,10}
• This would be true if it was an insertion sort, but you are also missing a step.
• {2,6,3,10,8}, {2,3,6,10,8}, {2,3,6,8,10}
• This is almost right, but is missing one step.
• {2,6,3,10,8}, {2,3,6,10,8}, {2,3,6,10,8}, {2,3,6,8,10}
• This is the result from a selection sort.

You can step through the code above by clicking on the folloiwng Ex-12-8-3.

7-11-5-4: Which of the following could be used to replace // missing code // in the code so that the method always sorts the array elem in ascending order?

public class Searcher
{

public static void sort(int[] elem)
{
for (int j = 0; j < elem.length - 1; j++)
{
int minIndex = j;

for (// missing code //)
{
if (elem [k] < elem [minIndex])
{
minIndex = k;
}
}
int temp = elem[j];
elem[j] = elem[minIndex];
elem[minIndex] = temp;
}
}

public static void main(String[] args)
{
int[] nums = {28, -3, 2, 14, 30};
Searcher.sort(nums);
}
}

• int k = j - 1; k >= 0; k--
• The inner loop starts at the outer loop value plus one, not minus one.
• int k = j + 1; k < elem.length; k++
• The inner loop starts at the outer loop value plus one and ends at the last element.
• int k = j; k < elem.length; k++
• The inner loop should start at the outer loop value plus one.
• int k = j; k >= 0; k--
• The inner loop should start at the outer loop value plus one and increment.
• int k = j - 1; k > 0; k--
• The inner loop should start at the outer loop value plus one and increment.

You can step through the code above (with answer a in place of the missing code) by clicking on the following Ex-12-8-4.

7-11-5-5: What would test return if a = {1,2,3,4} and v = 3?

public static int test(int[] a, int v)
{
for (int i = 0; i < a.length; i++)
{
if (a[i] == v)
return i;
else return -1;
}
}

• -1
• This would be true if the sequential search code was okay and v was a value that wasn't in the array, but the code is incorrect. The return -1 should be outside of the for loop.
• 0
• This would be true if v was 1 and the code was correct for a sequential search.
• 1
• This would be true if v was 2 and the code was correct for a sequential search.
• 2
• This would be true if the code was correct for a sequential search, but it returns -1 inside the for loop instead of outside of it.
• The code will not compile
• This method won't compile because it is supposed to return an integer and if the for loop doesn't execute it will not return anything. The return -1 should be outside the for loop to make this sequential search work as intended.

You can see this code at the following Ex-12-8-5.