数据结构详细题型.doc

《数据结构》
第九章排序****题
一、单项选择题
1. 若对n个元素进行直接插入排序,在进行第i趟排序时,假定元素r[i+1]的插入位置为r[j],则需要移动元素的次数为( )。
A. j-i B. i-j-1 C. i-j D. i-j+1
2. 若对n个元素进行直接插入排序,则进行任一趟排序的过程中,为寻找插入位置而需要的时间复杂度为( )。
A. O(1) B. O(n) C. O(n2) D. O(log2n)
3. 在对n个元素进行直接插入排序的过程中,共需要进行( )趟。
A. n B. n+1 C. n-1 D. 2n
4. 对n个元素进行直接插入排序时间复杂度为( )。
A. O(1) B. O(n) C. O(n2) D. O(log2n)
5. 在对n个元素进行冒泡排序的过程中,第一趟排序至多需要进行( )对相邻元素之间的交换。
A. n B. n-1 C. n+1 D. n/2
6. 在对n个元素进行冒泡排序的过程中,最好情况下的时间复杂度为( )。
A. O(1) B. O(log2n) C. O(n2) D. O(n)
7. 在对n个元素进行冒泡排序的过程中,至少需要( )趟完成。
A. 1 B. n C. n-1 D. n/2
8. 在对n个元素进行快速排序的过程中,若每次划分得到的左、右两个子区间中元素的个数相等或只差一个,则整个排序过程得到的含两个或两个元素的区间个数大致为( )。
A. n B. n/2 C. log2n D. 2n
9. 在对n个元素进行快速排序的过程中,第一次划分最多需要移动( )次元素,包括开始把支点元素移动到临时变量的一次在内。
A. n/2 B. n-1 C. n D. n+1
10. 在对n个元素进行快速排序的过程中,最好情况下需要进行( )躺。
A. n B. n/2 C. log2n D. 2n
11. 在对n个元素进行快速排序的过程中,最坏情况下需要进行( )躺。
A. n B. n-1 C. n/2 D. log2n
12. 在对n个元素进行快速排序的过程中,平均情况下的时间复杂度为( )。
A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)
13. 在对n个元素进行快速排序的过程中,最坏情况下的时间复杂度为( )。
A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)
14. 在对n个元素进行快速排序的过程中,平均情况下的空间复杂度为( )。
A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)
15. 在对n个元素进行直接插入排序的过程中,算法的空间复杂度为( )。
A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)
16. 对下列四个序列进行快速排序,各以第一个元素为基准进行第一次划分,则在该次划分过程中需要移动元素次数最多的序列为( )。
A. 1, 3, 5, 7, 9 B. 9, 7, 5, 3, 1
C. 5, 3, 1, 7, 9 D. 5, 7, 9, 1, 3
17. 假定对元素序列(7, 3, 5, 9, 1,