排序练习题(答案)

《排序》练习题一、单项选择题1.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。A.j-iB.i-j-1C.i-jD.i-j+12.在对n个元素进行直接插入排序的过程中，共需要进行（）趟。A.nB.n+1C.n-1D.2n3.在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)D.O(n)4.在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则排序的时间复杂度为（）。A.O(1)B.O(nlog2n)C.O(n2)D.O(n)5.在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)D.O(nlog2n)6.设一组初始记录关键字序列(5，2，6，3，8)，利用冒泡排序进行升序排序，且排序中从后往前进行比较，则第一趟冒泡排序的结果为（）。(A)2，5，3，6，8(B)2，5，6，3，8(C)2，3，5，6，8(D)2，3，6，5，87.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。A.1,3,5,7,9B.9,7,5,3,1C.5,1,3,7,9D.5,7,9,3,18.在对n个元素进行堆排序的过程中，时间复杂度为（）。A.O(1)B.O(log2n)C.O(n2)D.O(nlog2n)9.以下序列不可以构成小跟堆的是（）。A.12,9,7,5,3,1B.1,3,5,9,7,12C.1,5,3,7,9,12D.1,5,3,9,12,710.设一组初始记录关键字序列(5，8，6，3，2)，以第一个记录关键字5为基准进行一趟从大到小快速排序的结果为（）。A.2，3，5，8，6B.2，3，5，6，8C.3，2，5，8，6D.3，2，5，8，611.假定对元素序列（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,712.假定一个初始堆为(1,5,3,9,12,7,15,10)，则进行第一趟堆排序后，再重新建堆得到的结果为（）。A.3,5,7,9,12,10,15,1B.3,5,9,7,12,10,15,1-2-C.3,7,5,9,12,10,15,1D.3,5,7,12,9,10,15,113.若对n个元素进行归并排序，则进行归并的趟数为（）。A.nB.n-1C.n/2D.log2n14.若要从1000个元素中得到10个最小值元素，最好采用（）方法。A.直接插入排序B.归并排序C.堆排序D.快速排序15.若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。A.直接插入排序B.归并排序C.堆排序D.快速排序二、填空题1.对n个记录进行冒泡排序时，最少的比较次数为__n-1______，最少的趟数为_1______。2.快速排序在平均情况下的时间复杂度为__O(nlog2n)______，在最坏情况下的时间复杂度为__O(n2)___。3.假定一组记录为(46,79,56,38,40,84)，则利用堆排序方法建立的初始小根堆为_(38,40,56,79,46,84)__。4.假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为___(40,38,46,56,79,80)___。5.假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要_____4_____趟完成。6.在时间复杂度为O(nlog2n)的所有排序方法中，___归并_____排序方法是稳定的。7.设有一无序序列{32，45，41，12，1，9}，进行从小到大的希尔排序，且分组增量d=3，则一趟希尔排序后的序列为_{12,1,9,32,45,41}_。三、判断题1．希尔排序算法的平均时间复杂度为O(n2)。(0)2．堆是完全二叉树，完全二叉树不一定是堆。（1）3．在对排序中，若要进行升序排序，则需要建立大根堆。（1）4．若给出的待排序序列已有序，则使用快速排序的进行排序的时间复杂度是O(n)。（0）5．若待排序序列已基本有序，则使用冒泡排序会比快速排序的时间效率会更好。（1）6．堆排序是稳定的排序算法。（0）四、应用题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)，给出采用简单选择排序法进行排序时-3-每一趟的排序结果。5.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。6.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。-4-四、应用题（参考答案）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]-5-(9)142627343846536574[86]5.构成初始堆（即建堆）的过程：12345678910(0)46745314263886652734(1)46745314263886652734(2)46745314263886652734(3)46743814265386652734(4)46143827265386657434(5)14263827345386657446进行堆排序的过程：(0)14263827345386657446(1)262738463453866574[14](2)2734384674538665[2614](3)34463865745386[272614](4)384653657486[34272614](5)4665538674[3834272614](6)53657486[463834272614](7)658674[53463834272614](8)7486[6553463834272614](9)86[746553463834272614]6.(0)[46][74][53][14][26][38][86][65][27][34](1)[4674][1453][2638][6586][2734](2)[14465374][26386586][2734](3)[1426384653657486][2734](3)[14262734384653657486]