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
Was this exam question helpful?
Search Algorithms (College Board AP® Computer Science Principles): Exam Questions
14 mins14 questions
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
Was this exam question helpful?
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
Was this exam question helpful?
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
Was this exam question helpful?
5
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
Was this exam question helpful?
6
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"
Was this exam question helpful?
7
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
Was this exam question helpful?
8
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
Was this exam question helpful?
9
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
Was this exam question helpful?
10
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
Was this exam question helpful?
11
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
Was this exam question helpful?
12
1 point
A binary search is used to find a value in a sorted list of 800 elements. Approximately how many elements are still being searched after two comparisons have been made?
100200400798
Was this exam question helpful?
13
1 point
A sorted list of 500 elements is replaced by a sorted list of 1,000 elements. How does this change the maximum number of comparisons a binary search needs?
It stays exactly the same, because a binary search always makes a fixed number of comparisons
It doubles, because the list is twice as long
It falls by about half, because each comparison now covers more elements
It increases by about one, because one extra comparison reduces the larger list to the original size
Was this exam question helpful?
14
1 point
A binary search is used to look for a value in a sorted list of 50 elements. The value is not in the list. What happens?
The search keeps halving the range indefinitely, because the value is never found
The search reports the element whose value is closest to the target instead
The search ends once every element has been eliminated and reports that the value is not present
The search restarts and checks each element in turn until the value is found
Was this exam question helpful?