ch7i.txt

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

Chapter 7  Internal Sorting: Instructor's CD questions

1. A sorting algorithm is stable if it:
a) Works for all inputs.
*b) Does not change the relative ordering of records with identical key 
values.
c) Always sorts in the same amount of time (within a constant factor)
for a given input size.

2. Which sorting algorithm does not have any practical use?
a) Insertion sort.
*b) Bubble sort.
c) Quicksort.
d) Radix Sort.
e) a and b.

3. When sorting n records, Insertion sort has best-case cost:
a) O(log n).
*b) O(n).
c) O(n log n).
d) O(n^2)
e) O(n!)
f) None of the above.

4. When sorting n records, Insertion sort has worst-case cost:
a) O(log n).
b) O(n).
c) O(n log n).
*d) O(n^2)
e) O(n!)
f) None of the above.

5. When sorting n records, Quicksort has worst-case cost:
a) O(log n).
b) O(n).
c) O(n log n).
*d) O(n^2)
e) O(n!)
f) None of the above.

6. When sorting n records, Quicksort has average-case cost:
a) O(log n).
b) O(n).
*c) O(n log n).
d) O(n^2)
e) O(n!)
f) None of the above.

7. When sorting n records, Mergesort has worst-case cost:
a) O(log n).
b) O(n).
*c) O(n log n).
d) O(n^2)
e) O(n!)
f) None of the above.

8. When sorting n records, Radix sort has worst-case cost:
a) O(log n).
b) O(n).
c) O(n log n).
d) O(n^2)
e) O(n!)
*f) None of the above.

9. When sorting n records with distinct keys, Radix sort has a lower
bound of:
a) Omega(log n).
b) Omega(n).
*c) Omega(n log n).
d) Omega(n^2)
e) Omega(n!)
f) None of the above.

10. Any sort that can only swap adjacent records as an average case
lower bound of:
a) Omega(log n).
b) Omega(n).
c) Omega(n log n).
*d) Omega(n^2)
e) Omega(n!)
f) None of the above.

11. The number of permutations of size n is:
a) O(log n).
b) O(n).
c) O(n log n).
d) O(n^2)
*e) O(n!)
f) None of the above.

12. When sorting n records, Selection sort will perform how many swaps 
in the worst case?
a) O(log n).
*b) O(n).
c) O(n log n).
d) O(n^2)
e) O(n!)
f) None of the above.

13. Shellsort takes advantage of the best-case behavior of which sort?
*a) Insertion sort
b) Bubble sort
c) Selection sort
d) Shellsort
e) Quicksort
f) Radix sort

14. A poor result from which step causes the worst-case behavior for Quicksort?
*a) Selecting the pivot
b) Partitioning the list
c) The recursive call

15. In the worst case, the very best that a sorting algorithm can do
when sorting n records is:
a) O(log n).
b) O(n).
*c) O(n log n).
d) O(n^2)
e) O(n!)
f) None of the above.