ch14i.txt

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

Chapter 14  Analysis Techniques: Instructor's CD questions

1. Amortized analysis is used to:
a) analyze growth rates as the input size becomes large.
*b) Analyze the cost of a series of operations.
c) Analyze the cost of a problem.

2. Which of the following is not a standard method for finding the
closed form solution for a summation?
a) Guess and test.
b) Shifting.
*c) Contradiction.

3. Which of the following is not a standard method for finding the
closed form solution for a recurrence relation?
a) Guess and test.
b) Expanding.
*c) Shifting.

4. In amortized analysis, potential refers to:
*a) A measure of some resource that can be expended for a series of
operations.
b) The total value that can be computed for the problem.
c) The cost for the algorithm.

5. If we guess a polynomial for the closed form solution to a
summation and derive the coefficients for the polynomial, why
must we verify the result with an induction proof?
a) Any lower-order polynomial can be made to fit some points of a
higher-order polynomial.
b) Our calculations might be in error.
c) The closed form solution might not be a polynomial at all.
*d) all of the above.

6. The closed form solution for the recurrence T(n) = 2T(n/2) + n is:
a) Theta(log n)
b) Theta(sqrt(n))
c) Theta(n)
*d) Theta(n log n)
e) Theta(n^2)
f) Theta(2^n)

7. The closed form solution for the recurrence T(n) = 2T(n/2) + n^2 is:
a) Theta(log n)
b) Theta(sqrt(n))
c) Theta(n)
d) Theta(n log n)
*e) Theta(n^2)
f) Theta(2^n)

8. The closed form solution for the recurrence T(n) = T(n/2) + sqrt(n) 
is:
a) Theta(log n)
*b) Theta(sqrt(n))
c) Theta(n)
d) Theta(n log n)
e) Theta(sqrt(n) log n)
f) Theta(n^2)

9. The average case for Quicksort is an example of:
a) A divide and conquer recurrence.
*b) A recurrence with full history.
c) An asymptotic recurrence.

10. The sum of the cubes of the first n integers has as its closed form
solution:
a) Theta(n log n)
b) Theta(n^2)
c) Theta(n^3)
d) Theta(n^3 log n)
*e) Theta(n^4)
f) Theta(n^4 log n)