AP®Computer ScienceCollege BoardComputer Science PrinciplesExam QuestionsUnit 3: Algorithms and ProgrammingSearch Algorithms

Search Algorithms (College Board AP® Computer Science Principles): Exam Questions

14 mins14 questions
1
1 point

A linear search is performed on the list [9, 4, 17, 2, 11, 6, 8] (7 elements) to find the value 20, which is not in the list. How many comparisons are made?

  • 1

  • 4

  • 7

  • The search cannot complete

Choose your answer

2
1 point

Which statement about linear search is correct?

  • It works on both sorted and unsorted lists

  • It requires the list to be sorted first

  • It eliminates half of the remaining elements at each step

  • It is always faster than binary search

Choose your answer

3
1 point

A sorted list contains 1,024 elements. Which is closest to the maximum number of elements that will be examined when performing a binary search?

  • 10

  • 100

  • 512

  • 1,024

Choose your answer

4
1 point

Which two statements about binary search are true? Select two answers.

  • The list must be sorted for binary search to work correctly

  • Each comparison eliminates about half of the remaining elements

  • Binary search works correctly on unsorted lists

  • Binary search examines every element exactly once

Choose your answer

5
1 point

A binary search (middle index computed with integer division, as in the SME note) is used on the sorted list below to find the value 40.

[3, 7, 11, 18, 25, 33, 40, 52]

Which list elements are compared with the target before it is found?

  • 18, 33, 40

  • 25, 40

  • 18, 40

  • 3, 7, 11, 18, 25, 33, 40

Choose your answer

6
1 point

A linear search is performed on the list [14, 6, 23, 9, 31, 8] (6 elements) to find the value 8, which is the last element in the list. How many comparisons are made in the worst case?

  • 1

  • 3

  • 5

  • 6

Choose your answer

7
1 point

Consider the following code segment, which performs a linear search.

numbers ← [12, 5, 8, 3]

found ← false

FOR EACH n IN numbers

{

   IF(n = 7)

   {

      found ← true

   }

}
IF(found = true)

{

   DISPLAY("Yes")

}
ELSE

{

   DISPLAY("No")

}

What is displayed when this code segment is executed?

  • "Yes"

  • "No"

  • "7"

  • "false"

Choose your answer

8
1 point

A linear search is used to find a value in an unsorted list of 20 elements. In the best case, how many elements are examined before the value is found?

  • 1

  • 10

  • 19

  • 20

Choose your answer

9
1 point

A programmer must search an unsorted list of customer names for a particular name. Which statement best explains why a linear search is a suitable choice?

  • It examines half of the remaining names at each step, making it very fast

  • It requires the names to be sorted alphabetically first

  • It can check each name in turn without the list being sorted

  • It always makes fewer comparisons than a binary search

Choose your answer

10
1 point

A programmer wants to use a binary search on the list [42, 17, 8, 33, 5]. Why will the binary search not work correctly on this list as given?

  • The list contains too few elements for a binary search

  • The list is not in sorted order

  • The list contains a value larger than 40

  • Binary search cannot be used to find whole numbers

Choose your answer

11
1 point

A binary search is performed on the sorted list below, with the middle index computed using integer (floored) division.

[4, 9, 13, 21, 28, 36, 45, 50]

Which element does the binary search examine first?

  • 4

  • 13

  • 21

  • 28

Choose your answer

12
1 point

A binary search (middle index computed with integer division) is used on the sorted list below to find the value 44.

[6, 12, 19, 25, 30, 38, 44]

Which list elements are compared with the target before it is found?

  • 25, 38, 44

  • 25, 30, 44

  • 19, 38, 44

  • 6, 12, 19, 25, 30, 38, 44

Choose your answer

13
1 point

A sorted list contains 64 elements. Which is closest to the maximum number of elements a binary search will examine when finding a value?

  • 32

  • 16

  • 8

  • 6

Choose your answer

14
1 point

A sorted list contains 1,000,000 elements. Which best describes the approximate maximum number of comparisons needed by a binary search compared with a linear search on the same list?

  • About 500,000 for binary search and about 1,000,000 for linear search

  • About 1,000,000 for both binary search and linear search

  • About 20 for both binary search and linear search

  • About 20 for binary search and about 1,000,000 for linear search

Choose your answer