《数据结构》习题汇编09第九章排序试题.docx
《《数据结构》习题汇编09第九章排序试题.docx》由会员分享，可在线阅读，更多相关《《数据结构》习题汇编09第九章排序试题.docx（33页珍藏版）》请在冰点文库上搜索。
《数据结构》习题汇编09第九章排序试题
98989
数据结构课程（本科）第九章试题
一、单项选择题）方法比较次数最1.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（少。
A.直接插入排序B.快速排序
D.归并排序直接选择排序C.
如果只想得到1024个元素组成的序列中的2.前5个最小元素，那么用（）方法最快。
A.起泡排序B.快速排序
D.堆排序C.直接选择排序3.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，）。
直到子序列为空或只剩一个元素为止。
这样的排序方法是（直接插入排A.直接选择排B.序序
D.快速排序起泡排序C.
4.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？
A.8B.10
C.15
D.25
5.如果输入序列是已经排好顺序的，则下列算法中（）算法最快结束？
B.直接插入排序A.起泡排序C.直接选择排D.快速排序序
6.如果输入序列是已经排好顺序的，则下列算法中（）算法最慢结束？
B.直接插入排序A.起泡排序C.直接选择排快速排序序D.
7.）算法是不稳定的。
下列排序算法中（B.直接插入排序A.起泡排序
C.基数排序D.快速排序100个初始归并段，那么如果要求利用多路平衡归3趟内完成排8.并在序，假设某文件经过内部排序得到）。
则应取的归并路数至少是（
A.3B.4C.5D.6
采用任何基于排序码比较的算法，9.5个互异的整数进行排序，至少需要（）次比较。
对
A.5B.6C.7D.8
10.）算法不具有这样的特性：
对某些输入序列，可能不需要移动数据对象即可完成下列算法中（
排序。
．
98989
A.起泡排序B.希尔排序直接选择排D.序快速排序C.
98989
11.使用递归的归并排序算法时，为了保证排序过程的时间复杂度不超过O（nlog2n），必须做到（）。
每次序列的划分应该在线性时间内完成A.每次归并的两个子序列长度接近B.每次归并在线性时间内完成C.以上全是D.
）算法的最坏情况下的时间复杂度高于O（nlog12.2n）。
不在基于排序码比较的排序算法中，（
A.起泡排序希尔排序B.
D.快速排序C.归并排序
13.在下列排序算法中，（）算法使用的附加空间与输入序列的长度及初始排列无关。
B.快速排序A.锦标赛排序
归并排序D.C.基数排序
14.一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：
A.{38,46,79,56,40,
84}B.{38,79,56,46,40,84}
40,38,46,79,56,C.{38,46,56,79,40,8484}D.{}15.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中（）算法最快。
归并排序希尔排序B.A.
基数排序D.C.快速排序
5.A3.C2.D4.B1.A
参考答案：
9.C7.D6.D8.C10.C
12.C
11.D
14.C
13.C
15.D
二、填空题第i（i=1,,?
-n1）趟从参加排序的序列中取出0个～第i-1个元1.2第i个元素，把它插入到由第素组
成的有序表中适当的位置，此种排序方法叫做________排序。
第i（i=0,-2）?
趟n从参加排序的序列2.中第个元素中挑选出一个最小（大）元素，把n-11,
i个～第它交换到第________排序。
i个位置，此种排序方法叫做
3.每次直接或通过基准元素间接比较两个元素，若出现逆序排列，就交换它们的位置，这种排序方法叫做________排序。
每次使两个相邻的有序表合并成一个有序表，这种排序方法叫4.排序。
________做
98989
5.在直接选择排序中，排序码比较次数的时间复杂度为O（________）。
。
O（________）在直接选择排序中，数据对象移动次数的时间复杂度为6.
98989
在堆排序中，对n个对象建立初始堆需要调7.________次调整算法。
用
个对象的初始堆已经建如果n在堆排序中，8.那么到排序结束，还需要从堆顶结点出发调用好，________
次调整算法。
9.。
O（________）在堆排序中，对任一个分支结点进行调整运算的时间复杂度为对n个数据对象进行堆排序，总的时间复杂度10.。
为O（________）
{46,79,56,38,40,84}，则利用堆排序方法建立的初11.始堆（最大堆）为给定一组数据对象的排序码为________。
。
快速排序在平均情况下的时间复杂度为O（________）12.。
13.快速排序在最坏情况下的时间复杂度为O（________）。
14.快速排序在平均情况下的空间复杂度为O（________）O（________）。
快速排序在最坏情况下的空间复杂度为15.，对其进行一趟快速排序，结果为46,79,56,38,40,84{}16.。
________给定一组数据对象的排序码为17.个数据对象的二路归并排序中，每趟归并的时间复杂度为O（________）。
n在18.。
O（________）n在个数据对象的二路归并排序中，整个归并的时间复杂度为交换插入参考答案：
1.2.直接选择3.
6.n4.5.n2两路归并9.log2n8.n-1
7.n/2
11.84,79,56,38,40,10n12.nlog46.nlogn
2215.n13.nn14.log22[4038]46[79561618.nlog2n
84]
.17.n
三、判断题直接选择排序是一种稳定的排序方法。
1.则堆中各数据是否必然按自小到大的顺序排列起来。
2.若将一批杂乱无章的数据按堆结构组织起来当输入序列已经有序时，起泡排序需要的排序码比较次数比快速排序要少。
3.在任何情况下，快速排序需要进行的排序码比较的次数都是4.。
O（nlog2n）
98989
个排序码，用堆排序比用锦标赛排序更快。
5个互不相同的排序码中选择最小的2048在5.
98989
6.若用m个初始归并段参加k路平衡归并排序，则归并趟数应为log2m。
7.堆排序是一种稳定的排序算法。
8.对于某些输入序列，起泡排序算法可以通过线性次数的排序码比较且无需移动数据对象就可以完成排序。
9.如果输入序列已经排好序，则快速排序算法无需移动任何数据对象就可以完成排序。
10.希尔排序的最后一趟就是起泡排序。
n个数据对象进行排序时，最坏情况下时间复杂度不会低11.的于任何基于排序码比较的算法，对
O（nlog2n）。
6个排12.9次排序码的比较，就可以对任何序不存在这样一个基于排序码比较的算法：
它只通过不超过码互异的数据对象实现排序。
5.3.2.4.1.
参考答案：
否否是否否
10.9.7.8.6.是否否是否1211..是是
四、运算题1.判断以下序列是否是最小堆？
如果不是,将它调整为最小堆。
（1）{100,86,48,73,35,39,42,57,66,21}
（2）{12,70,33,65,24,56,48,92,86,33}。
2.在不要求完全排序时，堆排序是一种高效的算法。
这种算法的过程是：
（Heapification）把待排序序列看作一棵完全二叉树，通过反复筛选将其调整为堆；（Re-heapification）依次取出堆顶，然后将剩余的记录重新调整为堆。
现考虑序列A={23，41，7，5，56}：
（1）给出对应于序列A的最小堆HA（以线性数组表示）；
（2）H后的结果（以线性数组表示）；给出第一次取出堆顶后，重新调整A（3）H后的结果（以线性数组表示）。
给出第二次取出堆顶后，重新调整A3.,试举例说明。
希尔排序、直接选择排序、快速排序和堆排序是不稳定的排序方法给出12个初始归并段，其长度分别19,22,17,16,11,10,12,32,26,20,28,07。
现要做44.为路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长WPL。
度5.设输入文件包含以下数据对象的排序码：
14,22,7,16,11,10,12,90,26,30,28,110。
现采用置换—选择
98989
的过程。
生成初始归并段个数据对象，请画出5方法生成初始归并段，并假设内存工作区可同时容纳在利用置换—选择方法生成初始归并段时，可另开辟一个与工作区容量相同的辅助存储区（称为储备6.对象的排序码时，不将它存入工作区，而暂存于LastKey库）。
当输入对象排序码小于刚输出的门槛
98989
储备库中，接着输入下一对象的排序码，依次类推，直到储备库满时不再进行输入，而只是从工作区中选择对象输出直至工作区空为止，由此得到一个初始归并段。
然后再将储备库中的对象传送至工作区，重新开始置换—选择。
若设输入文件包含对象的排序码为19,22,17,16,11,10,12,32,26,20,28,07。
采用上述方法生成初始归并段，并设工作区可容纳5个对象，请画出生成初始归并段的过程。
假设文件有4500个记录，在磁盘上每个页块可放75个记录。
计算机中用于排序的内存区可容450
7.纳个记录。
试问：
（1）可建立多少个初始归并段？
每个初始归并段有多少记录？
存放于多少个页块中？
（2）应采用几路归并？
请写出归并过程及每趟需要读写磁盘的页块数。
如果某个文件经内排序得到80个初始归并段，试问8.趟完成排序，那么应取的归并路数至少应为多少？
若使用多路归并执行3
（1）个，则按多路归并至少需输出文件的总数不超过
（2）如果操作系统要求一个程序同时可用的输入/15要几趟可以完成排序？
如果限定这个趟数，可取的最低路数是多少？
参考答案：
1.
（1）{100,86,48,73,35,39,42,57,66,21}为最大堆。
}调整为最小堆后为{21,35,39,57,86,48,42,73,66,100
不是最小{12,70,33,65,24,56,48,92,86,33}
（2）
12,24,33,65,33,56,48,92,堆。
调整为最小堆后为{
86,70}
（1）建堆结果2.56
23741=H5A第一次取出堆顶，并重新调整后
（2）
41
HA=72356（3）第二次取出堆顶，并重新调整后
56H=2341A275*061}{3.
（1）5122752增量为希尔排序512{275*061275}1
增量为{061
275*512}275
061512}i=1{
（2）275275*直接选择排序i=2}{061275*512275
{061}275i=3275*512
275*512}275{061
275*
{512（3）275}快速排序275275*512}{
275与170275*275{061（4）}170已经是最大堆，交换堆排序170
{275}061
275*个调整3对前
98989
前3个最大堆，交275*与275*{170061
275}061换．
98989
{061170275*275}个调整对前2170与个最大堆，交前2
275{170*061275}061换
275}{061275170*4.设初始归并段个n=12，外归并路k=4，计算（n-1）%（k-1）=11%3≠0，必须补k-2-1=
数数=21
的空归并段，才能构造k路归并树。
此时，归并树的内结点应（n-1+1）/（k-1）=12/3=4
个长度为0有个。
0
3689
1820304460626885
3
68
0
1917820304460626885
3
68
0
917182030446062
19668
8564
413
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,输入5个排序码
12,32,26,20,
28,07
19,22,17,16,10,12,32,26,选择20,28,11输出11,11,门槛07
置换1011,
19,22,17,16,12,32,26,20,选择11
28,0710输出16,16,门槛1216,置换19,22,17,12,
选择11,161032,26,20,28,0717,输出17,门槛32置换17,
19,22,32,12,选择11,16,171026,20,28,0719,19,输出门槛26置换19,
26,22,32,12,选择11,16,17,19
1020,28,0722,22,输出门槛20
置换22,
98989
26,20,32,12,选择11,16,17,19,2228,071026,输出26,门槛置换26,28
11,16,17,19,22,28,20,32,12,选择260710输出28,28,门槛置换0728,
11,16,17,19,22,07,20,32,12,选择26,28
10输出32,32,门槛32,
无输入
07,11,16,17,19,22,无大于门槛的对,12,―20,26,28,
象10
32
输出段结束符∞11,16,17,19,22,07,,12,―选择20,
26,28,07,输出10
07,门槛07,
∞32,无输入．
98989
选择,20,―,12,
输出―071010,10,门槛10,无输入,
―,20,―07,10选择输出―12,12,12,门槛,
―12,无输入07,10,12,―20,―,―选择输出20,20,门槛07,10,12,20―,―,――,―,20,无输入07,10,12,无大于门槛的对象,∞20,输出段结束符∞结束6.生成初始归并段的过程内存工作区储备库输出文件OutFile动作输入文件输入5个排序码22,19,InFile
11,10,17,16,
26,32,12,
20,28,07,――10,12,20,―07,19,22,10,12,32,26,1117,20,28,,12,20,―111016,1107
―,―,20,―,―19,22,12,32,26,20,11,1610,12,――17,28,07
――,―,16,―11,16,1710,12,――19,22,32,26,20,28,07
11,16,17,17,19
10,12――,11,16,17,10,12,26,20,28,0719,222019,22,,32,―11,16,17,10,12,20,28,07―19,22,2026
26,22,,32,―11,16,17,10,12,28,07―19,22,20,,26,―26,28
07
07
―32,11,16,17,10,12,―20,19,22,,28,―26,28,3207,32,―11,16,17,―19,22,,――,26,28,32,32,∞将暂存区内容传送,――07到内存工作区,―,―,―07,10―,―
10,12,07,10,12
20,
98989
无大于门槛的对象,
11,选择输出11,1207,输出段结束符∞11,门槛2010,,结束暂存10
1207,20,选择16,,10,∞输出16,门槛16,暂存12选择17,输出17,门槛17,置换32选择19,输出19,门槛19,置换26选择22,输出22,门槛22,暂存20选择26,输出26,门槛26,置换28选择28,输出28,门槛28,暂存07选择32,输出32,门槛32,无输入无大于门槛的对象,输出段结束符∞选择输出07,07,门槛07,无输入选择输出10,10,门槛10,无输入选择输出12,12,门槛12,无输入选择输出20,20,门槛20,无输入
98989
7.
（1）文件有4500个记录，计算机中用于排序的内存区可容纳450个记录，可建立的初始归并段有4500
个页块中。
75=6∕450个记录，存于450个。
每个初始归并段中有450=10∕．
98989
6个缓冲区，其5个缓冲区用于输入，1个缓冲区用于输出，因
（2）内存区可容纳6个页块，可建立中此，可采用5路归并。
归并过程如下：
45045045045045045045045450
4500
22502250
45002趟归并，每趟需要60个磁盘页块，写60个磁盘页块。
共做了读出logkm=logk80=3得：
k，初始归并段个数m=80，根据归并趟数计算S设归并路数8.
（1）公式为k3≥80。
由=k≥5，即应取的归并路数至少为5。
此解得
（2）设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。
1个缓冲区对应1个文件，有k+1=15，因此k=14，14路归并。
由S=logkm==2。
即至少需2趟归并可完可做log1480成
排序。
若限定这个趟数，由S=log9。
即要在2趟内完成排序，k80=2，有80≤k，可取的最低路数为2进
行9路排序即可。
五、算法分析题1.给出下面main（）函数的执行结果：
//------------------------------------------------------------
//Sorry,nocommentsavailable:
//Trytoread&understandfollowinglinesbyyourself
//------------------------------------------------------------
#include
voidExchange（ints[],inti,intj）{inttemp=s[i];s[i]=s[j];s[j]=temp;}
intPartition（intseq[],intlow,inthigh）{intpivotpos=low;pivot=seq[low];
int
98989
for（inti=low+1;i<=high;i++）if（seq[i]=i）Exchange（seq,pivotpos,i）;};Exchange（seq,low,pivotpos）
98989
;for（i=0;i?
?
?
牰湩晴?
尠屜?
層（i=pivotpos+1;i<=high;for
;seq[i]）;printf（\
）
returnpivotpos;
}
main（）{void57,37,17,42,61,27,84,06,19,59,{inttestSeq[12]=;93,23};Partition（testSeq,0,11）Partition（testSeq,0,6）;;Partition（testSeq,8,11）}，作为结果
升级会员 