ch3i.txt

（英文原版）数据结构与算法分析（C++版）单选试题与答案

Chapter 3  Algorithm Analysis: Instructor's CD questions

1. A growth rate applies to:
a) the time taken by an algorithm in the average case.
b) the time taken by an algorithm as the input size grows.
c) the space taken by an algorithm in the average case.
d) the space taken by an algorithm as the input size grows.
e) any resource you wish to measure for an algorithm in the average
   case.
*f) any resource you wish to measure for an algorithm as the input
    size grows.

2. Pick the growth rate that corresponds to the most efficient
algorithm as n gets large:
a) 5n
*b) 20 log n
c) 2n^2
d) 2^n

3. Pick the growth rate that corresponds to the most efficient
algorithm when n = 4.
a) 5n
b) 20 log n
c) 2n^2
*d) 2^n

4. Pick the quadratic growth rate.
a) 5n
b) 20 log n
*c) 2n^2
d) 2^n

5. Asymptotic analysis refers to:
a) The cost of an algorithm in its best, worst, or average case.
*b) The growth in cost of an algorithm as the input size grows towards
   infinity.
c) The size of a data structure.
d) The cost of an algorithm for small input sizes

6. For an air traffic control system, the most important metric is:
a) The best-case upper bound.
b) The average-case upper bound.
*c) The worst-case upper bound.
d) The best-case lower bound.
e) The average-case lower bound.
f) The worst-case lower bound.

7. When we wish to describe the upper bound for a problem we use:
*a) The upper bound of the best algorithm we know.
b) The lower bound of the best algorithm we know.
c) We can't talk about the upper bound of a problem because there can
   always be an arbitrarily slow algorithm.

8. When we describe the lower bound for a problem we use:
a) The upper bound for the best algorithm we know.
b) the lower bound for the best algorithm we know.
c) The smallest upper bound that we can prove for the best algorithm
that could possibly exist.
*d) The greatest lower bound that we can prove for the best algorithm
that could possibly exist.

9. When the upper and lower bounds for an algorithm are the same, we
use:
a) big-Oh notation.
b) big-Omega notation.
*c) Theta notation.
d) asymptotic analysis.
e) Average case analysis.
f) Worst case analysis.

10. When performing asymptotic analysis, we can ignore constants and
low order terms because:
*a) We are measuring the growth rate as the input size gets large.
b) We are only interested in small input sizes.
c) We are studying the worst case behavior.
d) We only need an approximation.

11. The best case for an algorithm refers to:
a) The smallest possible input size.
*b) The specific input instance of a given size that gives the lowest
   cost.
c) The largest possible input size that meets the required growth rate.
d) The specific input instance of a given size that gives the greatest
   cost.

12. For any algorithm:
*a) The upper and lower bounds always meet, but we might not know what 
they are.
b) The upper and lower bounds might or might not meet.
c) We can always determine the upper bound, but might not be able to
determine the lower bound.
d) We can always determine the lower bound, but might not be able to
determine the upper bound.

13. If an algorithm is Theta(f(n)) in the average case, then it is:
a) Omega(f(n)) in the best case.
*b) Omega(f(n)) in the worst case.
c) O(f(n)) in the worst case.

14. For the purpose of performing algorithm analysis, an important
property of a basic operation is that:
a) It be fast.
b) It be slow enough to measure.
c) Its cost does depend on the value of its operands.
*d) Its cost does not depend on the value of its operands.

15. For sequential search,
a) The best, average, and worst cases are asymptotically the same.
*b) The best case is asymptotically better than the average and worst
cases.
c) The best and average cases are asymptotically better than the worst 
case.
d) The best case is asymptotically better than the average case, and
the average case is asymptotically better than the worst case.