Recursive Searching and Sorting FRQ Practice

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

Question 1 of 5

A kite shop counts letter A on ribbon stamps with this recursive method.

public static int countA(String s)
{
    if (s.length() == 0)
    {
        return 0;
    }
    int n = 0;
    if (s.substring(0, 1).equals("A"))
    {
        n = 1;
    }
    return n + countA(s.substring(1));
}

(a) State the return value of countA("CASA"). (b) List the String argument of each call after the original call, in the order the calls are made. (c) Explain what the base case returns and why that case is required.

Question 2 of 5

A quilt booth stores color tags in an ArrayList from first to last: navy, rust, gold.

public static String fromEnd(ArrayList<String> tags, int index)
{
    if (index == tags.size())
    {
        return "";
    }
    return fromEnd(tags, index + 1) + tags.get(index);
}

(a) State the return value of fromEnd(tags, 0). (b) State the return value of fromEnd(tags, 2). (c) Explain why later tags appear earlier in the returned string.

Question 3 of 5

A ceramics lab stores kiln temperatures in increasing order. hunt is the same recursive binary search used for the lockers. Complete the search for 270.

Index 0 1 2 3 4 5 6
Value 210 225 240 255 270 285 300

(a) Copy and complete a table of each call that computes mid, with columns low, high, mid, and data[mid], until the target is found or the range is empty. (b) State the value hunt(temps, 270, 0, 6) returns. (c) Explain one reason this search typically examines fewer elements than a linear scan of a long sorted list.

Question 4 of 5

The kiln list is still 210, 225, 240, 255, 270, 285, 300. hunt now searches for 248, which is not in the list.

(a) Complete a low/mid/high table until the method returns. (b) State the return value. (c) Explain why the temperatures must already be sorted for this process to be valid. (d) Explain whether an iterative version that updates low and high with the same rules would compute the same sequence of mid indexes.

Question 5 of 5

A track booth merge-sorts leftover bib numbers with mergeSort(bibs, 0, 3) using mid = (from + to) / 2, dividing until a piece has one element, then merging sorted halves.

Index 0 1 2 3
Value 19 4 12 7

(a) Show the two subarrays after the first split. (b) Show the four one-element lists after dividing is finished. (c) Show the two sorted halves after each pair of one-element lists is merged. (d) Show the final merged array.