Timedora
Free Practice Quiz Question List

08 Searching Algorithms Online Quiz Questions

Use this free practice quiz with 20 questions to review 08 Searching Algorithms, test your knowledge, and prepare for your next test or exam.

20 questions
01
Choose one
1 point

In the iterative binary-search implementation that uses the half-open interval [low, high), which initial value of high correctly represents the entire array A?

  1. A

    length(A) - 1

  2. B

    length(A)

  3. C

    length(A) + 1

  4. D

    0

02
Choose one
1 point

What does lower-bound search return for a sorted array?

  1. A

    The last index whose value is strictly less than the target

  2. B

    Any index containing a value equal to the target

  3. C

    The first index i such that A[i] is greater than or equal to the target

  4. D

    The index at which the target would be inserted after all equal values

03
Choose one
1 point

Why does binary search on a sorted linked list usually lose the usual time advantage it has on an array?

  1. A

    It may require linear-time traversal to locate middle positions

  2. B

    It always performs constant-time lookup of every middle position

  3. C

    It cannot compare elements because linked lists have no ordering

  4. D

    It necessarily uses logarithmic auxiliary space

04
Choose all
1 point

Which conditions are required for binary search to be correct and efficient during a search? Select all that apply.

  1. A

    The data is sorted according to the comparison ordering

  2. B

    The target and elements have compatible comparison operations

  3. C

    The collection must never be modified at any time in the future

  4. D

    The implementation can access middle positions efficiently

  5. E

    The collection remains ordered during the search

05
Choose all
1 point

Which situations favor sequential search over binary search? Select all that apply.

  1. A

    The collection is unsorted

  2. B

    The same large sorted collection will receive many searches

  3. C

    Values are accessed through a stream or linked structure

  4. D

    The collection changes so often that maintaining sorted order is expensive

06
True or false
1 point

True or false: On a random-access array, the recursive version of binary search uses logarithmic auxiliary stack space because its recursion depth is logarithmic.

  1. A

    True

  2. B

    False

07
True or false
1 point

True or false: The iterative sequential-search implementation uses constant extra space regardless of the input size.

  1. A

    True

  2. B

    False

08
Written response
1 point

Using zero-based indexing, what index does sequential search return when searching for 23 in [8, 14, 23, 41]?

09
Written response
1 point

What is the other standard name for sequential search?

10
Fill in the blank
1 point

Complete the loop invariant for sequential search: Before each iteration, every position before the current index has been and does not contain the target.

11
Fill in the blank
1 point

Complete the definition: For a sorted array, lower-bound search returns the .

12
Open ended
1 point

Explain why binary search is especially valuable for many searches on a stable sorted array, but may not be the best choice for one search or a frequently changing collection.

13
Choose one
1 point

Which midpoint expression is preferred in fixed-width integer languages because it avoids overflow when low and high are large?

  1. A

    (low + high) // 2

  2. B

    low + high // 2

  3. C

    low + (high - low) // 2

  4. D

    (high - low) // 2

14
Choose one
1 point

A program must search a small collection whose elements are frequently inserted and are not kept in sorted order. Which search algorithm is the most appropriate choice?

  1. A

    Binary search

  2. B

    Sequential search

  3. C

    Lower-bound search

  4. D

    Recursive binary search

15
Choose one
1 point

Why must a collection be sorted before the standard binary-search algorithm is applied?

  1. A

    The target must be stored at index 0 or at the last index.

  2. B

    The collection must contain no duplicate values.

  3. C

    The data must be sorted according to the comparison ordering.

  4. D

    The collection must be implemented as a linked list.

16
Written response
1 point

What is the name of the binary-search variant that returns the first index i such that A[i] is greater than or equal to the target?

17
Choose one
1 point

In the half-open binary-search implementation, what update is correct when A[mid] is less than the target?

  1. A

    low = mid + 1

  2. B

    low = mid

  3. C

    high = mid + 1

  4. D

    high = mid - 1

18
Written response
1 point

Which search algorithm is generally the more suitable choice for an unsorted linked list when the elements must be examined through sequential links?

19
Choose one
1 point

An already sorted array of n elements is searched with iterative binary search, and the target is absent. What is the worst-case running time?

  1. A

    Θ(1) in the worst case because the middle element is always the answer

  2. B

    Θ(n) in the worst case because every element may be compared

  3. C

    Θ(n log n) because the array must be sorted during every search

  4. D

    Θ(log n) in the worst case when the array is already sorted

20
True or false
1 point

True or false: When ordinary binary search is applied to the sorted array [2, 4, 4, 4, 9] with target 4, it is guaranteed to return the index of the first 4.

  1. A

    True

  2. B

    False