Searching, Sorting, and Recursion

Unit 4: Data Collections. Topics 4.14–4.17. This set has 57 questions. Each time the page loads you get five of them, chosen at random. Pick an answer, press Check answer, and read the explanation for every choice. Reload the page or use New questions for a fresh five.

Topics assessed

• 4.14 Searching Algorithms
• 4.15 Sorting Algorithms
• 4.16 Recursion
• 4.17 Recursive Searching and Sorting

Practice questions

Essential knowledge for this set

These are the essential knowledge (EKS) statements from the AP Computer Science A Course and Exam Description that the 57 questions in this set assess, grouped by topic and learning objective. The table under each question links here.

Topic 4.14: Searching Algorithms

4.14.A — Develop code used for linear search algorithms to search for specific information in a collection and determine the results of executing a search.

• 4.14.A.1 Linear search algorithms are standard algorithms that check each element in order until the desired value is found or all elements in the array or ArrayList have been checked. Linear search algorithms can begin the search process from either end of the array or ArrayList.
• 4.14.A.2 When applying linear search algorithms to 2D arrays, each row must be accessed then linear search applied to each row of the 2D array.

Topic 4.15: Sorting Algorithms

4.15.A — Determine the result of executing each step of sorting algorithms to sort the elements of a collection.

• 4.15.A.1 Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.
• 4.15.A.2 Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it into its correct (and final) position in the sorted portion of the list.
• 4.15.A.3 Insertion sort inserts an element from the unsorted portion of a list into its correct (but not necessarily final) position in the sorted portion of the list by shifting elements of the sorted portion to make room for the new element.

Topic 4.16: Recursion

4.16.A — Determine the result of calling recursive methods.

• 4.16.A.1 A recursive method is a method that calls itself. Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call. Recursion is another form of repetition.
• 4.16.A.2 Each recursive call has its own set of local variables, including the parameters. Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
• 4.16.A.3 Any recursive solution can be replicated through the use of an iterative approach and vice versa.

Topic 4.17: Recursive Searching and Sorting

4.17.A — Determine the result of executing recursive algorithms that use strings or collections.

• 4.17.A.1 Recursion can be used to traverse String objects, arrays, and ArrayList objects.

4.17.B — Determine the result of each iteration of a binary search algorithm used to search for information in a collection.

• 4.17.B.1 Data must be in sorted order to use the binary search algorithm. Binary search starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each recursive call until the desired value is found or all elements have been eliminated.
• 4.17.B.2 Binary search is typically more efficient than linear search.
• 4.17.B.3 The binary search algorithm can be written either iteratively or recursively.

4.17.C — Determine the result of each iteration of the merge sort algorithm when used to sort a collection.

• 4.17.C.1 Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.
• 4.17.C.2 Merge sort repeatedly divides an array into smaller subarrays until each subarray is one element and then recursively merges the sorted subarrays back together in sorted order to form the final sorted array.