AP CSA Practice Test: Searching and Sorting
Share
AP CSA Practice Test: Searching and Sorting
Unit 4: Data Collections | 10 Questions | AP Computer Science A
Explanation: Linear search checks each element one by one. In the worst case (element not found or at the end), it checks all 100 elements. Linear search is O(n).
Common Mistake: Confusing linear search (O(n)) with binary search (O(log n)).
Explanation: Binary search halves the search space each time. log2(1024) = 10 divisions, but you need one more comparison at the end. Maximum comparisons = 11. (Some implementations say 10; AP typically accepts ceil(log2(n)) + 1.)
Common Mistake: Saying 10. The maximum is actually 11 because you need one final check.
Explanation: Binary search assumes the array is sorted. On unsorted data, it may skip over the target and return an incorrect result (either wrong index or false negative). No exception is thrown.
Common Mistake: Expecting an error. Binary search silently produces wrong results on unsorted data.
{5, 3, 8, 1, 9}, the array is:Explanation: Selection sort finds the minimum (1 at index 3) and swaps it with the first element (5 at index 0). After one pass: [1, 3, 8, 5, 9]. Only one swap per pass.
Common Mistake: Doing more than one swap per pass. Selection sort makes exactly one swap per pass.
Explanation: Insertion sort maintains a sorted portion and inserts each new element into its correct position within that portion. Selection sort finds minimums; bubble sort swaps adjacent elements.
Common Mistake: Confusing insertion sort with selection sort. Selection SELECTS the min; insertion INSERTS in position.
int[] arr = {2, 5, 8, 12, 16, 23};
int target = 10;
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (arr[mid] == target) {
break;
}
else if (arr[mid] < target) {
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
System.out.println(lo + " " + hi);
Explanation: Trace: lo=0,hi=5,mid=2(8<10,lo=3). lo=3,hi=5,mid=4(16>10,hi=3). lo=3,hi=3,mid=3(12>10,hi=2). Now lo=3,hi=2, loop ends. Output: 3 2.
Common Mistake: Not tracing carefully. Each step updates either lo or hi, narrowing the range.
I. Both have O(n²) worst-case time complexity
II. Selection sort always makes exactly n-1 swaps
III. Insertion sort performs well on nearly-sorted data
Explanation: I: both are O(n²). II: selection sort finds the min for each position, making exactly n-1 swaps total. III: insertion sort is nearly O(n) on almost-sorted data because few shifts are needed.
Common Mistake: Not knowing that selection sort always does n-1 swaps regardless of initial order.
Explanation: log2(1,000,000) is approximately 19.9, so about 20 comparisons. This is the power of binary search: it handles a million elements in roughly 20 steps.
Common Mistake: Thinking large arrays require many steps. Binary search's O(log n) is extremely efficient.
{7, 3, 5, 1}?Explanation: Pass 1: insert 3 into [7] → [3, 7]. Pass 2: insert 5 into [3, 7] → [3, 5, 7]. After two passes, the first three elements are sorted: [3, 5, 7, 1].
Common Mistake: Sorting more elements than the pass number. After k passes, only the first k+1 elements are sorted.
Explanation: Both approaches work: searching backward and returning the first match gives the last occurrence; searching forward and overwriting the result each time also gives the last occurrence.
Common Mistake: Thinking only one approach works. Both backward search and forward with overwrite are valid.