AP CSA Searching and Sorting Algorithms 1

Question 1

What is the time complexity of linear search in the worst case?

Accepted Answer

O(n)

Answer

Linear search checks every element in the worst case (target not present), giving O(n) time complexity.

Question 2

What precondition must be met before applying binary search to an array?

Accepted Answer

The array must be sorted

Answer

Binary search requires the array to be sorted so it can correctly discard half the remaining elements at each step.

Question 3

What is the worst-case time complexity of binary search?

Accepted Answer

O(log n)

Answer

Binary search halves the search space each step, giving O(log n) comparisons in the worst case.

Question 4

Which sorting algorithm repeatedly finds the minimum element and places it at the beginning?

Accepted Answer

Selection sort

Answer

Selection sort works by finding the smallest unsorted element and swapping it to its correct sorted position in each pass.

Question 5

In bubble sort, what happens during each pass through the array?

Accepted Answer

Adjacent elements are compared and swapped if out of order

Answer

Bubble sort compares adjacent pairs and swaps them if they are out of order, causing larger elements to 'bubble up' to the end.

AP CSA - Advanced Placement Computer Science A Practice Test