admin 管理员组文章数量: 1184232
2024年3月14日发(作者：最常用的排序算法)
圣才电子书
十万种考研考证电子书、题库视频学习平台
第10章 外排序
一、单项选择题
（1）以下关于外排序的叙述正确的是______。
A．外排序把外存文件调入内存，再利用内排序方法进行排序，所以外排序所花的时间
完全由采用的内排序确定
B．外排序所花的时间=内排序时间+外存信息读／写时间+内部归并所花的时间
C．外排序并不涉及文件的读／写操作
D．外排序完全可以由内排序来替代
【答案】B
【解析】外排序所花的时间由内排序时间、外存读写时间、内部归并时间三部分时间构
成，因此AC两项错误，B项正确；外排序要将文件读取到内存中进行排序，但是由于文件
大小可能会大于内存的最大容量，因此外排序不能完全由内排序替代。
（2）如果将一个由置换-选择排序得到的输出文件F
1
（含所有初始归并段）作为输入
文件再次进行置换-选择排序，得到输出文件F
2
（含所有初始归并段），则F
1
和F
2
的差异是
______。
A．F
2
中归并段的个数减少
B．F
2
中归并段的最大长度增大
C．F
2
和F
1
无差异
1 / 5
【答案】C
圣才电子书
十万种考研考证电子书、题库视频学习平台
D．归并段个数及各归并段长度均不变，但F
2
中可能存在与F
1
不同的归并段
【解析】当进行一次置换-选择排序后，文件的归并段即达到理想状态，无论再进行多
少次排序，均不会发生变化，因此答案为C项。
（3）采用败者树进行k路平衡归并的外排序算法，其总的归并效率与k______。
A．有关
B．无关
【答案】A
【解析】利用败者树进行k路平衡归并不会影响总共需要的关键字比较次数，但是随着
k的增大，归并树的高度会减小，磁盘读/写的次数也就相应减少，从而提高总的归并效率，
因此答案为A项。
（4）对m个初始归并段实施k路平衡归并排序，所需的归并趟数是______。
A．1
B．m/k
C．
m/k
D．
log
k
m
【答案】D
【解析】采用k路归并，相应的归并树就有
log
k
m
+1层，则需要归并的趟数为
log
k
m
，答案为D项。
2 / 5
A．5
B．6
C．7
D．B
【答案】A
圣才电子书
十万种考研考证电子书、题库视频学习平台
（5）设有100个初始归并段，如果采用k路平衡归并3趟完成排序，则k值最小是______。
3
【解析】由题可知，应有
log
k
100
3
，则有
k
100
5
，答案为A项。
二、问答题
（1）简述磁盘外排序的基本步骤。
答：
①采用置换-选择排序算法生成m个初始归并段，并求出每个初始归并段中包含的记录
个数；
②根据内存大小和m值，尽可能选择较大的归并路数k，并构造出最佳归并树；
③按照最佳归并树的方案实施归并，产生一个有序文件F
out
。
（2）给出一组关键字T={12，2，16，30，8，28，4，10，20，6，18}，设内存工
作区可容纳4个记录，写出用置换-选择算法得到的所有初始归并段。
答：
F
1
={2，8，12，16，28，30}；
F
2
={4，6，10，18，20}。
（3）有一个无序文件中存放有若干个记录，其中所有记录构成的关键字序列为{41，
3 / 5
圣才电子书
十万种考研考证电子书、题库视频学习平台
39，28，32，22，19，11，50，13，21，1，33，37，3，52，16，4，8，72，12，32}。
设缓冲区ω有容纳5个记录的容量，按置换-选择算法求初始归并段，写出各初始归并段的
关键字。
答：
F
1
={22，28，32，39，41，50}；
F
2
={1，11，13,19，21，33，37，52，72}；
F
3
={3，4，8，16，12，32}。
（4）设有11个长度（即包含记录个数）不同的初始归并段，它们所包含的记录个数
为{25，40，16，38，77，64，53，88，9，48，98}。试根据它们做4路平衡归并，要
求：
①指出总的归并趟数；②构造最佳归并树；③根据最佳归并树计算每一趟及总的读记录
数。
答：
①进行了三趟归并。
②最佳归并树如下图：
③
第一趟读记录数为：9+16=25；
第二趟读记录数为：25+25+38+40+48+53+64=370;
第三趟读记录数为：88+98+128+242=556；
总的读记录数为：（9+16）×3+（25+38+40+48+53+64+77）×2+（88+98）=951。
4 / 5
0
圣才电子书
十万种考研考证电子书、题库视频学习平台
0
25 25
98 128
556
9
38
16
40 4853 64
242
77
88
三、算法设计题
设计一个算法，给定一个线性表，先对其遍历一遍，划分出若干个最大的有序子序列，
假设为k个有序子序列，将这些子序列作为初始归并段，采用k路归并方法将它们归并为
一个有序线性表（假设线性表采用不带头结点的单链表存放）。
答：略。
5 / 5
版权声明：本文标题：李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(外排序 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710383061a570612.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论