Timedora
Free Practice Quiz Question List

06 — Algorithms and Correctness Online Quiz Questions

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

20 questions
01
Choose one
1 point

You must locate a value in a small list whose elements are in no particular order. Which algorithm is the most appropriate choice?

  1. A

    Linear search

  2. B

    Binary search

  3. C

    Merge sort

  4. D

    Insertion sort

02
True or false
1 point

True or false: Binary search requires its input list to be sorted in order to guarantee its usual search behavior.

  1. A

    True

  2. B

    False

03
Written response
1 point

A linear search examines a list of 25 elements. What is the maximum number of element comparisons it can make?

04
Fill in the blank
1 point

In an algorithm specification, a statement describing what is guaranteed to be true after successful execution is a .

05
Choose one
1 point

Which worst-case running time best describes merge sort for a list of n elements?

  1. A

    O(n)

  2. B

    O(n log n)

  3. C

    O(n²)

  4. D

    O(1)

06
True or false
1 point

True or false: Testing an algorithm on many examples alone proves that it is correct for every valid input.

  1. A

    True

  2. B

    False

07
Written response
1 point

What value does the recursive factorial algorithm return for factorial(0)?

08
Fill in the blank
1 point

A loop-invariant proof has three parts: maintenance, plus before the first iteration and when the loop stops.

09
Choose all
1 point

Select all components that belong in a useful algorithm specification.

  1. A

    Inputs

  2. B

    Outputs

  3. C

    Preconditions

  4. D

    Postconditions

  5. E

    The programmer's preferred variable names

  6. F

    The color of the user interface

10
Choose one
1 point

Which statement best explains when insertion sort can be a practical choice?

  1. A

    It always has O(n log n) running time and requires O(n) extra space.

  2. B

    It requires the input list to be sorted before it starts.

  3. C

    It uses O(1) extra space and can work well on nearly sorted lists.

  4. D

    It cannot preserve the relative order of equal records.

11
Choose all
1 point

Select all statements that are components of total correctness.

  1. A

    Partial correctness

  2. B

    Termination

  3. C

    Testing on sample inputs

  4. D

    Use of constant extra space

  5. E

    A recursive implementation

12
Open ended
1 point

Explain the difference between an algorithm specification and an implementation, and explain one practical benefit of keeping them separate.

13
Choose one
1 point

Which statement is an appropriate loop invariant for insertion sort immediately before iteration i?

  1. A

    Before iteration i, the entire list A is already sorted.

  2. B

    Before iteration i, A[0:i] is sorted and contains the elements originally in those positions.

  3. C

    After iteration i, the list contains only unique values.

  4. D

    Before iteration i, the unsorted suffix is guaranteed to be in decreasing order.

14
Choose one
1 point

A program must find a value in a small list whose elements are not sorted. Which algorithm is the most appropriate choice?

  1. A

    Binary search, because it always examines every element

  2. B

    Linear search, because it works without sorted input

  3. C

    Merge sort, because it rearranges the list first

  4. D

    Insertion sort, because it searches a sorted prefix

15
Choose one
1 point

Which condition is the base case in the merge-sort procedure described in the material?

  1. A

    A list with zero or one element

  2. B

    A list with exactly two elements

  3. C

    A list containing no duplicate values

  4. D

    A list whose elements are already in reverse order

16
Choose one
1 point

Which statement correctly describes insertion sort?

  1. A

    It repeatedly halves the list and requires O(n) extra space

  2. B

    It always runs in O(n log n) time because it builds a prefix

  3. C

    It inserts each next element into a sorted prefix and can take O(n²) time

  4. D

    It compares each element with every other element but never moves values

17
True or false
1 point

True or false: Testing an algorithm on many examples alone is sufficient to prove that it is correct for every valid input.

  1. A

    True

  2. B

    False

18
Written response
1 point

Using the factorial definition in the material, what is the value of factorial(5)?

19
Written response
1 point

What is the single term for the part of a loop-invariant proof that shows the invariant is true before the first iteration?

20
Choose one
1 point

Why is sorted input a necessary precondition for binary search?

  1. A

    It must use constant extra space

  2. B

    It must preserve the relative order of duplicate records

  3. C

    It examines every element before returning an answer

  4. D

    It relies on ordering to discard a half of the remaining range