习题10排序及其答案

习题10一、单项选择题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.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个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（）。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(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,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(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.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.直接插入排序B.归并排序C.堆排序D.快速排序27.若要对1000个元素排序，要求既快又节省存储空间，则最好采用（）方法。A.直接插入排序B.归并排序C.堆排序D.快速排序28.在平均情况下速度最快的排序方法为（）。A.简单选择排序B.归并排序C.堆排序D.快速排序二、填空题1.每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做________排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。2．每次直接或通过支点元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做________排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做________排序。3．在简单选择排序中，记录比较次数的时间复杂度为________，记录移动次数的时间复杂度为________。4.对n个记录进行冒泡排序时，最少的比较次数为________，最少的趟数为_______。5.快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。6.若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较________次。7.假定一组记录为(46,79,56,38,40,84)，则利用堆排序方法建立的初始小根堆为____________________。8.假定一组记录为(46,79,56,38,40,84)，在冒泡排序的过程中进行第一趟排序后的结果为____________________。9.假定一组记录为(46,79,56,64,38,40,84,43)，在冒泡排序的过程中进行第一趟排序时，元素79将最终下沉到其后第_______个元素的位置。10.假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，共需要________趟排序。11.假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，含有两个或两个以上元素的排序区间的个数为________个。12.假定一组记录为(46,79,56,25,76,38,40,80)，对其进行快速排序的第一次划分后，右区间内元素的个数为__________。13.假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为____________________。14.假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为________________。15.假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为________________。16.假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要__________趟完成。17.在时间复杂度为O(nlog2n)的所有排序方法中，________排序方法是稳定的。18.在时间复杂度为O(n2)的所有排序方法中，________排序方法是不稳定的。19.在所有排序方法中，________排序方法采用的是二分法的思想。20.在所有排序方法中，________方法使数据的组织采用的是完全二叉树的结构。21.在所有排序方法中，________方法采用的是两两有序表合并的思想。22.________排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。23.________排序方法能够每次使无序表中的第一个记录插入到有序表中。24.________排序方法能够每次从无序表中顺序查找出一个最小值。三、应用题1.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行排序时每一趟的排序结果。2.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。3.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。4.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用简单选择排序法进行排序时每一趟的排序结果。5.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。6.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。四、算法设计题1.编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。2.试以单链表为存储结构实现简单选择排序的算法。习题10参考答案一、单项选择题1.D2.B3.C4.C5.B6.D7.A8.B9.D10.C11.B12.D13.C14.D15.A16.D17.B18.C19.D20.A21.B22.A23.D24.A25.B26.B27.C28.D二、填空题1.插入，选择2.快速，归并3.O(n2)，O(n)4.n-1，15.O(nlog2n)，O(n2)6.47.(38,40,56,79,46,84)8.(46,56,38,40,79,84)9.410.311.412.413．[4038]46[567980]14．315.[2846]16.417.归并18.直接选择19.快速20.堆排序21.归并排序22.冒泡23.直接插入24.直接选择三、应用题1.(0)[46]745314263886652734(1)[4674]5314263886652734(2)[465374]14263886652734(3)[14465374]263886652734(4)[1426465374]3886652734(5)[142638465374]86652734(6)[14263846537486]652734(7)[1426384653657486]2734(8)[142627384653657486]34(9)[14262734384653657486]2.(0)[46745314263886652734](1)[465314263874652734]86(2)[4614263853652734]7486(3)[14263846532734]657486(4)[142638462734]53657486(5)[1426382734]4653657486(6)[14262734]384653657486(7)[14262734]3846536574863.(0)[46745314263886652734](1)[3427381426]46[86655374](2)[262714]343846[746553]86(3)142627343846[5365]7486(4)142627343846536574864.(0)[46745314263886652734](1)14[745346263886652734](2)1426[5346743886652734](3)142627[46743886655334](4)14262734[743886655346](5)1426273438[7486655346](6)142627343846[86655374](7)14262734384653[658674](8)1426273438465365[8674](9