习题10排序及其答案

习题 10一、单项选择题1. 若对 n 个元素进行直接插入排序，在进行第 i 趟排序时，假定元素 r[i+l]的插入位置为 r[j]，则需要移动元素的次数为()。A.j-iB.i-j-1C.i-jD.i-j+12. 若对 n 个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为()。A.O(1)B.O(n)C.O(n2)D.O(logn)23. 在对 n 个元素进行直接插入排序的过程中，共需要进行()趟。A.nB.n+1C.n-1D.2n4. 对 n 个元素进行直接插入排序时间复杂度为()。A.O(1)B.O(n)C.O(n2)D.O(logn)25. 在对 n 个元素进行冒泡排序的过程中，第一趟排序至多需要进行()对相邻元素之间的交换。A.nB.n-1C.n+1D.n/26. 在对 n 个元素进行冒泡排序的过程中，最好情况下的时间复杂度为()。A.O(1)B.O(logn)C.O(n2)D.O(n)7. 在对 n 个元素进行冒泡排序的过程中，至少需要()趟完成。A.1B.nC.n-1D.n/28. 在对 n 个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为()。A.nB.n/2C.log2nD.2n9. 在对 n 个元素进行快速排序的过程中，第一次划分最多需要移动()次元素，包括开始把支点元素移动到临时变量的一次在内。A.n/2B.n-1C.nD.n+110. 在对 n 个元素进行快速排序的过程中，最好情况下需要进行()躺。A.nB.n/2C.log2nD.2n11. 在对 n 个元素进行快速排序的过程中，最坏情况下需要进行()躺。A.nB.n-1C.n/2D.log2n12. 在对 n 个元素进行快速排序的过程中，平均情况下的时间复杂度为()。A.O(1)B.O(logn)C.O(n2)D.O(nlogn)13. 在对 n 个元素进行快速排序的过程中，最坏情况下的时间复杂度为()。A.O(1)B.O(logn)C.O(n2)D.O(nlogn)14. 在对 n 个元素进行快速排序的过程中，平均情况下的空间复杂度为()。A.O(1)B.O(logn)C.O(n2)D.O(nlogn)15. 在对 n 个元素进行直接插入排序的过程中，算法的空间复杂度为()。A.O(1)B.O(logn)C.O(n2)D.O(nlogn)16. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为()。A.1,3,5,7,9B.9,7,5,3,1A-2B-3C-4D-518.在对 n 个元素进行简单选择排序的过程中，需要进行（）趟选择和交换A-nB-n+1C-n-1D-n/219.在对 n 个元素进行堆排序的过程中，时间复杂度为（）。A-O(1)B-O(logn)C-O(n2)D-O(nlogn)220.在对 n 个元素进行堆排序的过程空间复杂度为（2...