资源描述：
《数据结构详细题型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《数据结构》第九章排序习题一、单项选择题1.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为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(log2n)3.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A.nB.n+1C.n-1D.2n4.对n个元素进行直接插入排序时间复杂度为（）。A.
2、O(1)B.O(n)C.O(n2)D.O(log2n)5.在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之间的交换。A.nB.n-1C.n+1D.n/26.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)D.O(n)7.在对n个元素进行冒泡排序的过程中，至少需要（）趟完成。A.1B.nC.n-1D.n/28.在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个
3、或两个元素的区间个数大致为（）。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
4、.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.对下列四个序列进行快速排序，各以第一个元素为
5、基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。-7-A.1,3,5,7,9B.9,7,5,3,1C.5,3,1,7,9D.5,7,9,1,317.假定对元素序列（7,3,5,9,1,12,8,15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（）。A.2B.3C.4D.518.在对n个元素进行简单选择排序的过程中，需要进行（）趟选择和交换。A.nB.n+1C.n-1D.n/219.在对n个元素进行堆排序的过程中，时间复杂度为（）。A.O(1)B.O(log2n)C.O(
6、n2)D.O(nlog2n)20.在对n个元素进行堆排序的过程中，空间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)D.O(nlog2n)21.假定对元素序列（7,3,5,9,1,12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（）。A.1,3,5,7,9,12B.1,3,5,9,7,12C.1,5,3,7,9,12D.1,5,3,9,12,722.假定一个初始堆为(1,5,3,9,12,7,15,10)，则进行第一趟堆排序后得到的结果为（）。A.3,5,7,9,12,10,15,1B
7、.3,5,9,7,12,10,15,1C.3,7,5,9,12,10,15,1D.3,5,7,12,9,10,15,123.若对n个元素进行归并排序，则进行归并的趟数为（）。A.nB.n-1C.n/2D.élog2nù24.若一个元素序列基本有序，则选用（）方法较快。A.直接插入排序B.简单选择排序C.堆排序D.快速排序25.若要从1000个元素中得到10个最小值元素，最好采用（）方法。A.直接插入排序B.简单选择排序C.堆排序D.快速排序26.若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。A.
8、直接插入排序B.归并排序C.堆排序D.快速排序27.若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。A.直接插入排序B.归并排序C.堆排序D.快速排序28.在平均情况下速度最快的排序方法为（）。A.简单选择排序B.归并排序C.堆排序D.快速排序二、填空题1.每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做________排序；每次从无
