Recursive Searching and Sorting FRQ Practice

Responses receive AI feedback against a rubric after submission. Scores are practice estimates.

Question 1 of 5

A pottery studio shortens glaze codes with this recursive method.

public static String zip(String s)
{
    if (s.length() <= 2)
    {
        return s;
    }
    return s.substring(0, 1) + zip(s.substring(2));
}

(a) State the return value of zip("GLAZE"). (b) State the return value of zip("OX"). (c) Explain how the base case treats strings of length 0, 1, or 2.

Question 2 of 5

A library desk stores hold-slip page counts 12, then 4, then 9 in an ArrayList named slips.

public static int pages(ArrayList<Integer> slips, int index)
{
    if (index >= slips.size())
    {
        return 0;
    }
    return slips.get(index) + pages(slips, index + 1);
}

(a) Trace pages(slips, 0) by listing each index used and the value returned from that call. (b) State the return value of pages(slips, 2). (c) Explain that this method only reads the list with get and size and does not need to add or remove elements while it runs.

Question 3 of 5

An orchard map stores row numbers in increasing order. hunt is the recursive binary search that starts at the middle of the current low..high range and discards half of the remaining values after each comparison. Search for 57.

Index 0 1 2 3 4 5 6 7
Value 14 22 31 39 48 57 66 75

(a) Complete a table of each call that computes mid, with low, high, mid, and the compared value, until 57 is found or the range is empty. (b) State the returned index. (c) Explain why this process could miss 57 if the same numbers were stored out of order.

Question 4 of 5

The orchard rows are still 14, 22, 31, 39, 48, 57, 66, 75. hunt now searches for 40, which is not stored.

(a) Complete a low/mid/high table until the method returns. (b) State the return value. (c) Name two indexes the binary search never compares, and contrast that with a linear scan that starts at index 0.

Question 5 of 5

A lantern cart merge-sorts watt leftovers with mergeSort(watts, 0, 4), mid = (from + to) / 2, dividing until each piece has one element, then merging sorted halves.

Index 0 1 2 3 4
Value 28 9 16 4 21

(a) Show the two subarrays after the first split. (b) Show how the three-element left half is split on its first recursive call. (c) Show the sorted left half of three values and the sorted right half of two values just before they are merged together. (d) Show the final merged array.