Chapter 11 Questions
Multiple Choice Questions
1. In the worst case, a binary search is ______.
a. O(n)
b. O(1)
c. O(log2 n)
d. O(n2)
2. The selection sort continues until ______ of the n items in an array have been swapped.
a. n/2
b. n – 2
c. n – 1
d. n
3. Given the following array:
4 15 8 3 28 21
which of the following represents the array after the second swap of the selection sort?
a. 4 3 8 15 21 28
b. 4 15 8 3 21 28
c. 3 4 8 15 21 28
d. 21 4 3 8 15 28
4. Given the fact that a selection sort of n items requires n2/2 + 5 * n/2 – 3 major operations, the selection sort is
______.
a. O(1)
b. O(n)
c. O(n2)
d. O(log2 n)
5. The ______ compares adjacent items and exchanges them if they are out of order.
a. selection sort
b. binary search
c. bubble sort
d. quicksort
6. A bubble sort requires at most ______ passes to sort an array of n items.
a. n/2
b. n – 2
c. n – 1
d. n
7. In the worst case, the insertion sort’s comparison occurs ______ times.
a. n
b. n – 1
c. (n – 1) / 2
d. n * (n – 1)/2
8. Each merge step of the mergesort requires ______ major operations.
Chapter 11 Questions
a. 3 * n – 1
b. 4 * n – 1
c. (n – 1)/2
d. n – 1
9. The quicksort is ______ in the worst case.
a. O(n2)
b. O(n3)
c. O(n * log2 n)
d. O(log2 n)
10. Select the sorting algorithm(s) that is O(n2)
a) insertion sort
b) selection sort
c) bubble sort
d) all three
11. The worst scenario for insertion sort is
a) 9 8 7 6 5 4 3 2 1
b) 1 9 2 8 3 7 4 6 5
c) 8 2 6 4 5 3 7 1 9
d) 5 6 3 8 9 2 1 7 4
12. The ___ compares adjacent items and exchanges them if they are out of order.
a) selection sort
b) binary search
c) bubble sort
d) quicksort
13. A merge sort operation runs in:
a) O(log n) time.
b) O(n) time.
c) O(n log n) time.
d) O(n2) time.
Chapter 11 Questions
True/False Questions
1. The efficiency of the selection sort depends on the initial arrangement of the data.
2. For large arrays, the insertion sort is prohibitively inefficient.
3. In a recursive mergesort, the actual sorting occurs during the recursive calls. The merge step simply puts two
array segments together again.
4. To sort numeric data, the radix sort treats each number as a character string.
5. Insertion sort can be implemented as in-place sort.
6. Quick sort can be slower than insertion sort.
Chapter 11 Questions
Short Answer Questions
1. What is an internal sort?
2. What is an external sort?
3. What is the sort key of a record?
4. In the worst case, how many comparisons does a bubble sort require?
5. What is the drawback of the mergesort with respect to storage?
6. How does the quicksort partition an array?
7. Compare the efficiencies of the quicksort and the mergesort in the worst case.