数据结构习题汇编09排序试题

1、数据结构课程（本科）第九章试题、单项选择题1,若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。A,直接插入排序B,快速排序C.归并排序D.直接选择排序2 .如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。A.起泡排序B,快速排序C,直接选择排序D,堆排序3 .对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）。A,直接选择排序B,直接插入排序C.快速排序D,起泡排序4 .对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？A.8B.10

2、C.15D.255 .如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？A.起泡排序B,直接插入排序C,直接选择排序D,快速排序6 .如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？A.起泡排序B,直接插入排序C,直接选择排序D,快速排序7,下列排序算法中（）算法是不稳定的。A.起泡排序B,直接插入排序C,基数排序D,快速排序8.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3趟内完成排序,则应取的归并路数至少是（）。A.3B.4C,5D,69,采用任何基于排序码比较的算法，对5个互异的整数进行排序，至少需要（）次比较。A.5B.6C,7D,

3、810,下列算法中（）算法不具有这样的特性：对某些输入序列，可能不需要移动数据对象即可完成排序。A,起泡排序B,希尔排序C.快速排序D,直接选择排序11 .使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O(nlog2n),必须做到()。A.每次序列的划分应该在线性时间内完成B.每次归并的两个子序列长度接近C.每次归并在线性时间内完成D.以上全是12 .在基于排序码比较的排序算法中，()算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序13.在下列排序算法中，(A.锦标赛排序C.基数排序)算法使用的附加空间与输入序列的长度及初始排

4、列无关。B.快速排序D.归并排序14.一个对象序列的排序码为46,79,56,38,40,84准而）得到的第一次划分结果为：A.38,46,79,56,40,84C.40,38,46,79,56,84,采用快速排序（以位于最左位置的对象为基B.38,79,56,46,40,84D.38,46,56,79,40,8415.如果将所有中国人按照生日算法最快。(不考虑年份,只考虑月、日)来排序，那么使用下列排序算法中A.归并排序C.快速排序B.希尔排序D.基数排序参考答案：1.A2.D3.C6.D7.D8.C11.D12.C13.C14.C4.B9.C15.D5.A10.C二、填空题1 .第i(i=

5、1,2,，n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个第i-1个元素组成的有序表中适当的位置，此种排序方法叫做排序。2 .第i(i=0,1,，n-2)趟从参加排序白序列中第i个第n-1个元素中挑选出一个最小(大)元素，把它交换到第i个位置，此种排序方法叫做排序。3 .每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做排序。4 .每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做排序。5 .在直接选择排序中，排序码比较次数的时间复杂度为0()。6 .在直接选择排序中，数据对象移动次数的时间复杂度为0()。7 .在堆排序中，对n个对象

6、建立初始堆需要调用次调整算法。8 .在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用次调整算法。9 .在堆排序中，对任一个分支结点进彳T调整运算的时间复杂度为0()。10 .对n个数据对象进行堆排序，总的时间复杂度为0()。11 .给定一组数据对象的排序码为46,79,56,38,40,84,则利用堆排序方法建立的初始堆(最大堆)为。0()。0()。0()。0()。12 .快速排序在平均情况下的时间复杂度为13 .快速排序在最坏情况下的时间复杂度为14 .快速排序在平均情况下的空间复杂度为15 .快速排序在最坏情况下的空间复杂度为16 .给定一组数据对象的排序

7、码为46,79,56,38,40,84,对其进行一趟快速排序，结果为17 .在n个数据对象的二路归并排序中，每趟归并的时间复杂度为0()。18 .在n个数据对象的二路归并排序中，整个归并的时间复杂度为0()。3.交换6.n9.log2n12.nlog2n15.n18.nlog2n参考答案：1.插入2.直接选择4.两路归并5.n27. ?n/2?8.n-110. nlog2n11.84,79,56,38,40,4613. n214.log2n16. 40384679568417.n三、判断题1 .直接选择排序是一种稳定的排序方法。2 .若将一批杂乱无章的数据按堆结构组织起来，则堆中各数据是否必然

8、按自小到大的顺序排列起来。3 .当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。4 .在任何情况下，快速排序需要进行的排序码比较的次数都是O(nlog2n)。5 .在2048个互不相同的排序码中选择最小的5个排序码，用堆排序比用锦标赛排序更快。6 .若用m个初始归并段参加k路平衡归并排序，则归并趟数应为?log2m?。7 .堆排序是一种稳定的排序算法。8 .对于某些输入序列，起泡排序算法可以通过线性次数的排序码比较且无需移动数据对象就可以完成排序。9 .如果输入序列已经排好序，则快速排序算法无需移动任何数据对象就可以完成排序。10 .希尔排序的最后一趟就是起泡排序。11 .任

9、何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度不会低于O(nlog2n)。9次排序码的比较，就可以对任何6个排序12 .不存在这样一个基于排序码比较的算法：它只通过不超过码互异的数据对象实现排序。参考答案：1.否2.否3.是4.否5.否6.否7.否8.是9.否10.是11.是12.是四、运算题1 .判断以下序列是否是最小堆？如果不是，将它调整为最小堆。(1) 100,86,48,73,35,39,42,57,66,21(2) 12,70,33,65,24,56,48,92,86,33。2 .在不要求完全排序时，堆排序是一种高效的算法。这种算法的过程是：(Heapifi

10、cation)把待排序序列看作一棵完全二叉树，通过反复筛选将其调整为堆；(Re-heapification)依次取出堆顶，然后将剩余的记录重新调整为堆。现考虑序列A=23,41,7,5,56:(1)给出对应于序列A的最小堆HA(以线性数组表示)；(2)给出第一次取出堆顶后，重新调整Ha后的结果(以线性数组表示)；(3)给出第二次取出堆顶后，重新调整Ha后的结果(以线性数组表示)。3 .希尔排序、直接选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。4 .给出12个初始归并段，其长度分别为19,22,17,16,11,10,12,32,26,20,28,07。现要做4路外归并排序，试画出

11、表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL5 .设输入文件包含以下数据对象的排序码：14,22,7,16,11,10,12,90,26,30,28,110。现采用置换一选择方法生成初始归并段，并假设内存工作区可同时容纳5个数据对象，请画出生成初始归并段的过程。6 .在利用置换一选择方法生成初始归并段时，可另开辟一个与工作区容量相同的辅助存储区(称为储备库)。当输入对象排序码小于刚输出的门槛LastKey对象的排序码时，不将它存入工作区，而暂存于储备库中，接着输入下一对象的排序码，依次类推，直到储备库满时不再进行输入，而只是从工作区中选择对象输出直至工作区空为止，由此得到一个初

12、始归并段。然后再将储备库中的对象传送至工作区，重新开始置换一选择。若设输入文件包含对象的排序码为19,22,17,16,11,10,12,32,26,20,28,07。采用上述方法生成初始归并段，并设工作区可容纳5个对象，请画出生成初始归并段的过程。7 .假设文件有4500个记录，在磁盘上每个页块可放75个记录。计算机中用于排序的内存区可容纳450个记录。试问：(1)可建立多少个初始归并段？每个初始归并段有多少记录？存放于多少个页块中？(2)应采用几路归并？请写出归并过程及每趟需要读写磁盘的页块数。8 .如果某个文件经内排序得到80个初始归并段，试问(1)若使用多路归并执行3趟完成排序，那么应

13、取的归并路数至少应为多少？(2)如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？参考答案:1. (1)100,86,48,73,35,39,42,57,66,21为最大堆。调整为最小堆后为21,35,39,57,86,48,42,73,66,100(2)12,70,33,65,24,56,48,92,86,33不是最小堆。调整为最小堆后为12,24,33,65,33,56,48,92,86,702. (1)建堆结果HA=52374156(2)第一次取出堆顶，并重新调整后Ha=7235641(3)第

14、二次取出堆顶，并重新调整后Ha=2341563.(1)希尔排序512275275*061力胃里为2275*061512275锚日4A增里为1061275*275512(2)直接选择排序275275*512061ii=1061275*512275i=2061275*512275i=3061275*275512(3)快速排序512275275*275*275512(4)堆排序275275*061170已经是最大堆，交换275与170170275*061275对前3个调整275*170061275061170275*275170061275*275前3个最大堆，交换275*与061对前2个调整前2个

15、最大堆，交换170与061061170275*2754.k-2-1=12/3设初始归并段个数n=12,外归并路数k=4,计算(n-1)%(k-1)=11%3=2丰0,必须补=1个长度为0的空归并段，才能构造k路归并树。此时，归并树的内结点应有(n-1+1)/(k-1)=4个。回区回回区回回回回回回回画WPL=(3+6+8)*3+(9+18+20+30+44+60+62)*2+(68+85)*1=51+486+153=6905.生成初始归并段的过程输入文件InFile内存工作区输出文件OutFile动作19,22,17,16,11,10,12,32,26,20,28,07输入5个排序码10,12

16、,32,26,20,28,0719,22,17,16,回选择11,输出11,门槛11,置换1012,32,26,20,28,0719,22,17,四，1011选择16,输出16,门槛16,置换1232,26,20,28,0719,22,回12,1011,16选择17,输出17,门槛17,置换3226,20,28,07回22,32,12,1011,16,17选择19,输出19,门槛19,置换2620,28,0726,国32,12,1011,16,17,19选择22,输出22,门槛22,置换2028,07国20,32,12,1011,16,17,19,22选择26,输出26,门槛26,置换2807

17、园20,32,12,1011,16,17,19,22,26选择28,输出28,门槛28,置换0707,20,国12,1011,16,17,19,22,26,28选择32,输出32,门槛32,无输入07,20,12,1011,16,17,19,22,26,无大于门槛的对28,32象，输出段结束符OO凹20,12,1011,16,17,19,22,26,28,32,8选择07,输出07,门槛07,无输入,20,12,四07选择10,输出10,门槛10,无输入一,20,一,啊一07,10选择12,输出12,门槛12,无输入一,|20,一,一07,10,12选择20,输出20,门槛20,无输入,07,

18、10,12,20无大于门槛的对象，输出段结束符807,10,12,20,8结束6. 生成初始归并段的过程输入文件InFile内存工作区储备库输出文件OutFile动作19,22,17,16,11,10,12,32,26,20,28,07输入5个排序码10,12,32,26,20,28,0719,22,17,16,忙11选择11,输出11,门槛11,暂存1012,32,26,20,28,0719,22,17,16,一1011选择16,输出16,门槛16,暂存1232,26,20,28,0719,22,1百,10,1211,16选择17,输出17,门槛17,置换3226,20,28,07国22,3

19、2,10,1211,16,17选择19,输出19,门槛19,置换2620,28,0726,苞32,10,1211,16,17,19选择22,输出22,门槛22,暂存2028,07国,32,10,12,2011,16,17,19,22选择26,输出26,门槛26,置换2807国,32,10,12,2011,16,17,19,22,26选择28,输出28,门槛28,暂存07,32J,10,12,20,0711,16,17,19,22,26,28选择32,输出32,门槛32,无输入,10,12,20,0711,16,17,19,22,26,28,32无大于门槛的对象，输出段结束符8将暂存区内容传送到

20、内存工作区10,12,20,同，-11,16,17,19,22,26,28,32,8选择07,输出07,门槛07,无输入10,12,20,07选择10,输出10,门槛10,无输入,1固20,07,10选择12,输出12,门槛12,无输入一,一,20?,07,10,12选择20,输出20,门槛20,无输入,07,10,12,20无大于门槛的对象，输出段结束符807,10,12,20,8结束7. (1)文件有4500个记录，计算机中用于排序的内存区可容纳450个记录，可建立的初始归并段有4500/450=10个。每个初始归并段中有450个记录，存于450/75=6个页块中。(2)内存区可容纳6个页

21、块，可建立6个缓冲区，其中5个缓冲区用于输入，1个缓冲区用于输出，因此，可采用5路归并。归并过程如下：450450450450450450450450450450晒画皿皿皿皿皿皿皿皿450450450450450450450450450450晒画皿皿皿皿皿皿皿皿/22502250共做了2趟归并，每趟需要读60个磁盘页块，写出60个磁盘页块。8. (1)设归并路数为k,初始归并段个数m=80,根据归并趟数计算公式S=?logkm?=?logk80?=3得：k380o由此解得k5,即应取的归并路数至少为5。(2)设多路归并的归并路数为k,需要k个输入缓冲区和1个输出缓冲区。1个缓冲区对应1个文件,

22、有k+1=15，因此k=14,可做14路归并。由S=?logkm?=?log1480?=2。即至少需2趟归并可完成排序。若限定这个趟数，由S=?logk80?=2,有80k2,可取的最低路数为9。即要在2趟内完成排序，进彳T9路排序即可。五、算法分析题1.给出下面main()函数的执行结果：ey=0;j-)if(Vectorj.key)Vectorj+1=Vectorjelsebreak;Vectorj+1=temp;(1)该算法执行什么功能？(2)针对有n个数据对象的待排序的数据表，算法的排序码比较次数和对象移动次数最好是多少？最坏是多少？4 .下面给出一个排序算法，它属于数据表类的成员函数

23、，其中currentSize是数据表实例的当前长度,Vector是存放数据表元素的一维数组。templatevoiddataList:unknown()Ttemp;inti,j,d,n=currentSize;for(d=n/2;d=1;d/=2)ey)Vectorj+d=Vectorj;elsebreak;Vectorj+d=temp;)(1)该算法执行什么功能？(2)针对一组输入实例35,67,18,29,53,44,09,21,画出每一趟排序过程。5 .下面给出一个排序算法，它属于数据表类的成员函数，其中currentSize是数据表实例的当前长度,Vector是存放数据表元素的一维数组。temp