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.

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.

Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

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 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