7.13.5. Medium Search/Sort Multiple Choice Questions¶

These problems are similar to those you will see on the AP CSA 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.

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

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.

You have attempted 1 of 6 activities on this page