AP CSA Unit 4.17 MCQ Explanations

How to use this page: First try each question without looking at the explanation. Then compare your answer with the key and read why the other choices are not correct.

Answer Explanations

What condition must be true for recursive binary search to work correctly?

AThe method must be void.

BThe data must be sorted.

CThe array must contain only one value.

DThe data must be unsorted.

Correct answer: B. Binary search requires sorted data, because its range decisions depend on sorted order.

Explanation

Each step compares the target with the middle value and then keeps only the half that can still contain the target. That decision is only trustworthy when the values are in sorted order; without it the method can return an incorrect result.

A is not correct: The return type is not what makes the search work; the traced method returns an int, either the found index mid or -1.
C is not correct: A single value is not a requirement at all; the traced array {2, 5, 8, 10, 11, 15, 17, 20, 22} holds nine values and the halving still works.
D is not correct: Unsorted data is the case the method cannot handle, since the choice between the left half and the right half would no longer eliminate the values it assumes it eliminates.

For {2, 5, 9, 12, 18}, a search for 18 first checks index 2. Which inclusive range is searched next?

AIndexes 0 through 1

BIndexes 2 through 4

CIndexes 3 through 4

DIndex 4 only

Correct answer: C. The middle value at index 2 is 9, the target 18 is larger, so the next call takes the right half starting at mid + 1.

Explanation

The recursive call for the right half is rBinarySearch(a, mid + 1, high, target). With mid equal to 2 and high still 4, the new inclusive range runs from index 3 to index 4.

A is not correct: Indexes 0 through 1 form the left half, which is taken only when the target is less than a[mid]; here 18 is greater than 9.
B is not correct: Keeping index 2 in the range re-includes the middle value that was just checked, so the range does not make progress toward an empty range.
D is not correct: Starting at index 4 moves the low bound one position too far and skips index 3, a value that still needs to be checked.

A recursive array traversal begins at index i and advances by 1. Which condition shows that every element has been processed?

Ai == 0

Bi < array.length

Ci == array.length

Di == array.length - 1

Correct answer: C. The traversal is finished when the index has advanced past the last element, which is the base case i == array.length.

Explanation

Each call processes the element at i and then calls the method with i + 1. The index therefore lands exactly on the length after the last element has been handled, which is why the sample methods use i == a.length and i == s.length() to return 0.

A is not correct: i == 0 is the usual starting index of a forward traversal, so it describes the first call rather than the finished one.
B is not correct: i < array.length is true while elements still remain, so it marks the calls that still have work to do.
D is not correct: i == array.length - 1 is the last valid index, and the element stored there has not been processed yet at that point.

In recursive binary search, which condition represents an empty inclusive search range?

Alow == 0

Bhigh == data.length - 1

Clow == high

Dlow > high

Correct answer: D. An inclusive range is empty once its low bound has passed its high bound, which is the same condition the traced method writes as high < low.

Explanation

This is the not-found base case. Each recursive call narrows the range with mid - 1 or mid + 1, and when the target is absent the bounds eventually cross, so the method returns -1.

A is not correct: low == 0 only says the low bound sits at the first index, which is where a search of the whole array begins.
B is not correct: high == data.length - 1 describes the upper bound of a full-array range, so it is a starting state rather than an empty one.
C is not correct: low == high is a one-element range, and that element is still the mid that has to be compared with the target.

Which statement best describes the work performed by merge sort?

AIt splits the data, sorts the pieces, and merges them.

BIt repeatedly swaps the smallest value into the next position.

CIt inserts each value into an already sorted prefix.

DIt checks values from left to right until it finds the target.

Correct answer: A. Merge sort follows a divide-and-conquer pattern: split the array into two halves, recursively sort each half, then merge the two sorted halves.

Explanation

The traced helper shows that order directly. It computes mid, calls sort on from to mid and on mid + 1 to to, and only then calls merge to combine the two sorted ranges.

B is not correct: Repeatedly moving the smallest value into the next position describes a pass over the whole data, not the splitting into halves and merging that the recursive helper performs.
C is not correct: Placing each value into an already sorted prefix never divides the array into smaller ranges, so nothing is recursively sorted and then merged.
D is not correct: Checking values from left to right until a target is found describes a search, like the linear search that binary search is compared with, not a sorting algorithm.

Which recursive call shows progress for searching the left half?

Asearch(arr, target, low, mid - 1)

Bsearch(arr, target, high, low) always

Csearch(arr, target, low, high)

Dsearch(arr, target, mid, high) always

Correct answer: A. For the left half the new high bound is mid - 1, which excludes the middle index that was just checked and makes the range smaller.

Explanation

Progress means the next call must receive a smaller problem. Dropping mid from the range guarantees that repeated calls eventually reach the empty-range base case when the target is absent.

B is not correct: Passing high and low in swapped positions does not describe the left half at all, and it ignores the mid - 1 bound the left half needs.
C is not correct: Passing low and high unchanged repeats the same range, so an absent target never reaches high < low.
D is not correct: Using mid as the low bound keeps the already-checked middle index and describes the right half, and it can repeat a one-element range.

A recursive traversal calls itself again without changing its index. What is the most likely result?

AThe collection is sorted automatically.

BThe method skips exactly one value.

CThe index becomes the collection's length.

DThe calls may never reach the base case.

Correct answer: D. If the index never changes, the calls never move toward the base case, so they may never reach it.

Explanation

A recursive traversal reaches its base case only because each call advances the index by 1 until i equals the collection's length. Every recursive call must receive updated indexes or a smaller problem; an unchanged index gives neither.

A is not correct: A traversal only processes one element and calls itself for the remaining ones; putting values in order is the work of merge sort, not of a traversal.
B is not correct: Skipping exactly one value would require the index to move too far ahead, which is the opposite of leaving it unchanged.
C is not correct: The index reaches the collection's length only by advancing, so an index that stays the same never arrives there.

After the first merge level for {8, 3, 6, 1}, which sorted segments have been formed?

A{8, 3} and {6, 1}

B{3, 8} and {1, 6}

C{1, 3} and {6, 8}

D{1, 3, 6, 8}

Correct answer: B. The first merge level combines the single elements of each half, producing the two sorted pairs {3, 8} and {1, 6}.

Explanation

The splits break {8, 3, 6, 1} into {8, 3} and {6, 1}, then into single elements. Merging then puts each pair of single elements back together in sorted order, exactly as the traced example turns {86, 3} and {43, 5} into {3, 86} and {5, 43}.

A is not correct: Those are the segments produced by the split level, still in their original order, so no merging has taken place yet.
C is not correct: Those pairs mix values from different halves, but a merge only combines the sorted ranges that came from the same split.
D is not correct: A single fully sorted array is the result of the final merge level, which combines the two sorted pairs afterwards.

Consider the following method. What does hits("pepper", 1) return?

public static int hits(String s, int i) {
    if (i == s.length()) {
        return 0;
    }
    int amount = 0;
    if (s.substring(i, i + 1).equals("p")) {
        amount = 1;
    }
    return amount + hits(s, i + 1);
}

A1

B2

C3

D5

Correct answer: B. Starting at index 1, the traversal visits indexes 1 through 5 and finds "p" twice, so the sum of the contributions is 2.

Explanation

Each call adds 1 when the one-character substring equals "p" and 0 otherwise, then adds the result of the call for the rest of the string. The call at index 6 reaches s.length() and returns 0, which ends the chain.

A is not correct: 1 counts only one of the matches, but two of the visited indexes hold "p" and each contributes 1.
C is not correct: 3 includes the match at index 0, and a call that starts at index 1 never examines index 0.
D is not correct: 5 is how many characters are visited from index 1 onward, not how many of them equal "p".

Q10

Consider the following method. For a = {7, 4, 9, 6}, what does oddCount(a, 1) return?

public static int oddCount(int[] a, int i) {
    if (i == a.length) {
        return 0;
    }
    int amount = 0;
    if (a[i] % 2 != 0) {
        amount = 1;
    }
    return amount + oddCount(a, i + 1);
}

A0

B1

C2

D3

Correct answer: B. From index 1 the calls examine 4, 9, and 6, and only 9 is odd, so the contributions add to 1.

Explanation

Each call sets amount to 1 when a[i] % 2 != 0 and to 0 otherwise, then adds the result of oddCount(a, i + 1). The call at index 4 reaches a.length and returns 0.

A is not correct: 0 would mean no visited element is odd, but 9 at index 2 makes a[i] % 2 != 0 true.
C is not correct: 2 also counts 7 at index 0, which the traversal skips because it starts at index 1.
D is not correct: 3 is the number of elements visited from index 1, not the number of them that are odd.

Q11

Consider the following method. What does the method return for the list [5, 8, 3, 2] when i starts at 1?

public static int evenSum(ArrayList<Integer> a, int i) {
    if (i == a.size()) {
        return 0;
    }
    int amount = 0;
    if (a.get(i) % 2 == 0) {
        amount = a.get(i);
    }
    return amount + evenSum(a, i + 1);
}

A10

B8

C5

D2

Correct answer: A. From index 1 the even values are 8 and 2, and this method adds the values themselves, so the calls contribute 8 and 2 for a total of 10.

Explanation

Here amount is set to a.get(i) rather than to 1, so the traversal sums the even values instead of counting them. The odd value at index 2 leaves amount at 0, and the call at index 4 reaches a.size() and returns 0.

B is not correct: 8 stops after the first even value, but the chain of calls continues to index 3, where 2 is also even.
C is not correct: 5 is the value at index 0, which a start index of 1 skips, and it is odd so it would contribute 0 anyway.
D is not correct: 2 counts only the last even value and drops the 8 that the call at index 1 contributes.

Q12

Consider the following method. If the initial range is 0 through 5, which ranges do the two recursive calls receive at the first split?

private static void arrange(int[] a, int low, int high, int[] temp) {
    if (low < high) {
        int mid = (low + high) / 2;
        arrange(a, low, mid, temp);
        arrange(a, mid + 1, high, temp);
        merge(a, low, mid, high, temp);
    }
}

A0 to 2 and 3 to 5

B0 to 3 and 4 to 5

C0 to 5 and 0 to 5

D0 to 1 and 2 to 5

Correct answer: A. With low at 0 and high at 5, mid is 2, so the calls receive low to mid and mid + 1 to high.

Explanation

Integer division makes (0 + 5) / 2 equal to 2. The first recursive call gets the range 0 to 2 and the second gets 3 to 5, which is how the split step hands each call a smaller range.

B is not correct: This split would need mid to be 3, but (0 + 5) / 2 evaluates to 2.
C is not correct: Repeating the full range in both calls gives neither call a smaller range, so nothing would reach a single-element range.
D is not correct: This split would need mid to be 1, which is not what (low + high) / 2 produces for these bounds.

Q13

Two sorted halves are merged one element at a time by comparing the front values and taking the smaller one. In what order are the values written to the merged result?

Left half:   {4, 19, 31}
Right half:  {6, 12, 27}

A4, 6, 12, 19, 27, 31

B4, 19, 31, 6, 12, 27

C6, 12, 27, 4, 19, 31

D4, 6, 19, 12, 31, 27

Correct answer: A. Comparing the front values and taking the smaller one each time produces the combined sorted order.

Explanation

The merge works one element at a time: compare 4 and 6 and take 4, then 19 and 6 and take 6, and so on until one half runs out, at which point the remaining values are copied across.

B is not correct: This writes the whole left half and then the whole right half, so no front values are ever compared and the result is not sorted.
C is not correct: This writes the whole right half first, which again skips the comparison step and leaves 4 after 27.
D is not correct: This alternates between the halves regardless of which front value is smaller, so 19 is written before 12.

What to review next

Review the three traces this topic asks for. For a recursive traversal, write the indexes visited, the base case that returns 0, and what each call contributes when it returns. For recursive binary search, write (low, high, mid, a[mid]) for every call, and check that each new range excludes mid by using mid - 1 or mid + 1 so the bounds move toward high < low. For merge sort, write every split level down to single elements and every merge level back up, and practice the element-by-element comparison that builds each merged output. In all three, the key skill is tracking the parameters of each call and seeing how the problem gets smaller.