8.7 外部排序·习题
复习入口
8.7 外部排序 · 8.7.1 外部排序的基本概念 · 8.7.2 外部排序的方法 · 8.7.3 多路平衡归并与败者树 · 8.7.4 置换选择排序 · 8.7.5 最佳归并树
本节共22题:选择题17题,综合应用题5题。每题答案紧接题目折叠显示。
文字转录进度:22/22题。已转录题目的题干、选项和解析可编辑;示意图按需保留。
单项选择题
单项选择题 01
原书题目P392 · 解析P394 · 目视转录
外部排序与内部排序的主要区别是( )。
A. 内部排序数据量小,外部排序数据量大
B. 内部排序不涉及内外存数据交换,外部排序涉及
C. 内部排序快,外部排序慢
D. 内部排序所需内存小,外部排序所需内存大
查看答案与解析
答案:B。
最主要区别是是否涉及内存、外存之间的数据交换。
单项选择题 02
原书题目P392 · 解析P394 · 目视转录
下列关于外部排序的说法中,正确的是( )。
A. 置换选择排序得到的初始归并段长度一定相等
B. 内外存交换时间只占总排序时间的一小部分
C. 败者树是一棵完全二叉树
D. 外部排序不涉及文件读写
查看答案与解析
答案:C。
置换选择生成的段长度不一定相等,A错。外部排序主要耗时在内外存数据交换,B错。败者树是完全二叉树,C对。生成初始段与归并两个阶段都涉及文件读写,D错。
单项选择题 03
原书题目P392 · 解析P394 · 目视转录
多路平衡归并的作用是( )。
A. 减少归并趟数
B. 减少初始归并段个数
C. 便于实现败者树
D. 以上都不对
查看答案与解析
答案:A。
m个初始段采用k路平衡归并,需S=⌈logₖm⌉趟;不用多路归并时趟数更大。
单项选择题 04
原书题目P392 · 解析P394 · 目视转录
磁盘存有375000条记录,5路平衡归并排序,内存工作区容纳600条记录,需( )趟归并。
A. 3
B. 4
C. 5
D. 6
查看答案与解析
答案:B。
初始段r=375000/600=625,S=⌈log₅625⌉=4。各趟段数625→125→25→5→1。
单项选择题 05
原书题目P392 · 解析P394 · 目视转录
下列关于外部排序输入/输出缓冲区作用的叙述,不正确的是( )。
A. 暂存输入输出记录
B. 内部归并工作区
C. 生成初始归并段工作区
D. 传送用户界面消息
查看答案与解析
答案:D。
缓冲区即排序的内存工作区。m路平衡归并需m个输入、1个输出缓冲区,存放参与归并及完成归并的记录;生成初始段时也可作内部排序工作区,没有传送界面消息的任务。
单项选择题 06
原书题目P392 · 解析P394 · 目视转录
m路平衡归并中,为使输入、内部归并、输出并行,需要(①)个输入缓冲区、(②)个输出缓冲区。
①
A. 2
B. m
C. 2m−1
D. 2m
②
A. 2
B. m
C. 2m−1
D. 2m
查看答案与解析
答案:①D;②A。
普通m路归并增加一个输出缓冲区,一个写出时另一个供内部归并填充,使归并与输出并行。再增加m个输入缓冲区,一组用于当前归并时另一组从外存读入,使输入与归并并行。因此需2m个输入、2个输出。
单项选择题 07
原书题目P392 · 解析P394 · 目视转录
64个元素只需3趟多路归并,则归并路数最少为( )。
A. 2
B. 3
C. 4
D. 5
查看答案与解析
答案:C。
趟数⌈logₖn⌉,k=4、n=64恰为3,最少4路。
单项选择题 08
原书题目P392 · 解析P394 · 目视转录
置换选择排序的作用是( )。
A. 生成外部排序的初始归并段
B. 完成磁盘文件整体排序的有效外部排序算法
C. 生成的初始段长度是内存工作区2倍
D. 实现输入、归并、输出并行
查看答案与解析
答案:A。
用于生成初始段,长度不等,平均为传统等长初始段的2倍,可使段数平均减少约一半。它本身不是完成整个外部文件排序的算法。
单项选择题 09
原书题目P392 · 解析P394 · 目视转录
无序文件的n条记录,用置换选择产生m个有序段,m与n的关系是( )。
A. 成正比
B. m=log₂n
C. 成反比
D. 以上都不对
查看答案与解析
答案:D。
工作区w=1时,{1,2,3,4,5}产生1段,{5,4,3,2,1}产生5段。段数与文件初态、工作区w及n均有关,并非前三项关系。
单项选择题 10
原书题目P393 · 解析P394 · 目视转录
k路归并构建的败者树中选取最小关键字记录,所需时间为( )。
A.
B.
C.
D. 以上都不对
查看答案与解析
答案:C。
选取并维护最小关键字的时间取决于败者树高度,为 。
单项选择题 11
原书题目P393 · 解析P395 · 目视转录
关于小顶堆与败者树,正确的是( )。
Ⅰ.败者树自下向上维护,每上一层只需与失败结点比较1次。
Ⅱ.败者树每次维护必从叶走至根,不会中途停止。
Ⅲ.堆自上向下维护,每下一层若左右孩子均非空,需比较2次。
Ⅳ.堆每次维护必从根走至叶,不会中途停止。
A. Ⅰ、Ⅲ
B. Ⅱ、Ⅲ
C. Ⅰ、Ⅱ、Ⅲ
D. Ⅱ、Ⅲ、Ⅳ
查看答案与解析
答案:C。
Ⅰ是败者树性质;胜利者维护时一直调整至根,Ⅱ正确。小顶堆每次先比较两个孩子找较小者,再与当前元素比较决定是否下移,共2次,Ⅲ正确。堆若中途已满足要求可停止,无需走到叶,Ⅳ错误。
单项选择题 12
原书题目P393 · 解析P395 · 目视转录
最佳归并树在外部排序中的作用是( )。
A. 完成m路归并排序
B. 设计m路归并的优化方案
C. 生成初始归并段
D. 与锦标赛树作用类似
查看答案与解析
答案:B。
仿照哈夫曼树,以初始段长度为权,构造WPL最小的m叉哈夫曼树,可减少归并过程读写记录数,加快外部排序。
单项选择题 13
原书题目P393 · 解析P395 · 目视转录
由m个初始归并段构建k阶最佳归并树,不需要补虚段,则度为k的结点个数是( )。
A. (m−1)/k
B. m/k
C. (m−1)/(k−1)
D. 无法确定
查看答案与解析
答案:C。
树只有度0、度k结点。设总数n、叶数n₀=m、度k结点数nₖ,则n=n₀+nₖ、n−1=knₖ,故knₖ=m+nₖ−1,得nₖ=(m−1)/(k−1)。
单项选择题 14
原书题目P393 · 解析P395 · 目视转录
【2013 统考真题】三叉树T的6个叶结点权为2,3,4,5,6,7,带权外部路径长度最小为( )。
A. 27
B. 46
C. 54
D. 56
查看答案与解析
答案:B。
构造三叉哈夫曼树需(n₀−1)%(3−1)=0,因此补1个权0叶结点,叶数7。每次合并最小3个:0、2、3→5;4、5、5→14;6、7、14→27。
WPL=(2+3)×3+(4+5)×2+(6+7)×1=46。也可将分支结点权值求和,WPL=27+14+5=46,因为每个分支权累加其下所有叶权,第二种更方便。
单项选择题 15
原书题目P393 · 解析P395 · 目视转录
【2016 统考真题】对10TB数据文件排序,应使用( )。
A. 希尔排序
B. 堆排序
C. 快速排序
D. 归并排序
查看答案与解析
答案:D。
大文件无法一次装入内存,需多次内外存交换,通常采用归并排序。A、B、C均为内部排序方法。
单项选择题 16
原书题目P393 · 解析P395 · 目视转录
【2019 统考真题】120个初始段作12路最佳归并,需补虚段个数为( )。
A. 1
B. 2
C. 3
D. 4
查看答案与解析
答案:B。
设补虚段nₓ,内部结点n₁₂=(120−1+nₓ)/(12−1)。使其为整数的最小nₓ为2。即补两个0权叶,令总叶数122,满足(n−1)%(m−1)=0。
单项选择题 17
原书题目P393 · 解析P395 · 目视转录
【2024 统考真题】败者树归并初始升序归并段,记录“冠军”的结点保存的是( )。
A. 最大关键字
B. 最小关键字
C. 最大关键字所在归并段号
D. 最小关键字所在归并段号
查看答案与解析
答案:D。
每次需当前最小关键字。若冠军结点保存段号,可直接取得该关键字及所在段,再移动该段元素、继续比较,效率高;若仅保存最小关键字,还需检查各段首元素才能找到所在段,时间更高。因此保存的是最小关键字所在段号。
综合应用题
综合应用题 01
原书题目P393 · 解析P396 · 目视转录
某文件内部排序得到80个初始归并段,问:
- 多路平衡归并3趟完成排序,归并路数至少多少?
- 操作系统要求同时可用输入输出文件总数不超过15,至少几趟完成?限定该趟数时,可取最低路数多少?
查看答案与解析
- 设路数m,r=80,S=⌈logₘ80⌉=3,需m³≥80,解得m≥5,至少5路。
- 需m个输入缓冲区、1个输出缓冲区,一个缓冲区对应一个文件,m+1=15得m=14。⌈log₁₄80⌉=2,最少2趟。若限定2趟,m²≥80,最小m=9,即9路平衡归并。
综合应用题 02
原书题目P393 · 解析P396 · 目视转录
文件有4500条记录,磁盘每块75条,内存排序区容纳450条。问:
- 可建多少初始段?每段多少记录、占多少块?
- 应用几路归并?写出过程及每趟读写块数。
查看答案与解析
- 初始段数4500/450=10,每段450条,占450/75=6块。
- 内存容6块,可建6缓冲区,5个输入、1个输出,采用5路归并。第一趟将10个450条的段分别每5个合并,得到2个2250条的段;第二趟将它们合成4500条。共2趟,每趟读60块、写60块。
综合应用题 03
原书题目P393 · 解析P396 · 目视转录
初始归并段为 (10,15,31)、(9,20)、(22,34,37)、(6,15,42)、(12,37)、(84,95),利用败者树作m路归并,手工给出选出最小5个关键字的过程。
查看答案与解析
作6路归并,段号为0~5。败者树的叶从左到右按段2、3、4、5、0、1排列;其中前4个叶深度3,后2个深度2。内部结点存失败者段号,另设冠军结点。
以下记录每次输出前的完整比较树状态。“根、左、右、左左、左右”分别指根及相应内部结点的位置。
| 当前各段首元素(按0~5号) | 冠军段 | 根 | 左 | 右 | 左左 | 左右 | 输出及补入 |
|---|---|---|---|---|---|---|---|
| 10,9,22,6,12,84 | 3 | 1 | 4 | 0 | 2 | 5 | 输出6,3号补15 |
| 10,9,22,15,12,84 | 1 | 4 | 3 | 0 | 2 | 5 | 输出9,1号补20 |
| 10,20,22,15,12,84 | 0 | 4 | 3 | 1 | 2 | 5 | 输出10,0号补15 |
| 15,20,22,15,12,84 | 4 | 0 | 3 | 1 | 2 | 5 | 输出12,4号补37 |
| 15,20,22,15,37,84 | 3 | 0 | 4 | 1 | 2 | 5 | 输出15,3号补42 |
前5个输出关键字为6、9、10、12、15;最后的15来自3号段,与原书平值时的胜负选择一致。
综合应用题 04
原书题目P393 · 解析P397 · 目视转录
12个初始段长度为30,44,8,6,3,20,60,18,9,62,68,85,做4路外归并。画最佳归并树,计算WPL。
查看答案与解析
n=12、k=4,(n−1)%(k−1)=11%3=2,不满足严格4叉树要求。需补1个0长度虚段,使叶数13,内部结点数(13−1)/3=4。
按权值从小到大,逐次合并最小4个:
- 0、3、6、8合并为17。
- 9、17、18、20合并为64。
- 30、44、60、62合并为196。
- 64、68、85、196合并为根413。
树可表示为:413(64(9,17(0,3,6,8),18,20),68,85,196(30,44,60,62))。
WPL=(3+6+8)×3+(9+18+20+30+44+60+62)×2+(68+85)×1=51+486+153=690;亦等于17+64+196+413=690。
综合应用题 05
原书题目P393 · 解析P397 · 目视转录
【2023 统考真题】对含n(n>0)条记录的文件外部排序,置换选择生成初始归并段,工作区可保存m条记录。
- 文件19条记录,关键字依次为51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100。m=4时可生成几段?各为何?
- 任意n>m>0时,第一个初始段长度的最大值、最小值分别是多少?
查看答案与解析
- 工作区WA每次输出当前段允许的最小值,输出后从输入FI补入,低于当前段末值的记录留待下一段。
#表示段结束。原书完整过程如下。
| 输出文件FO(当前段) | 工作区WA | 剩余输入FI |
|---|---|---|
| — | — | 51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100 |
| — | 51,94,37,92 | 14,63,15,99,48,56,23,60,31,17,43,8,90,166,100 |
| 37 | 51,94,14,92 | 63,15,99,48,56,23,60,31,17,43,8,90,166,100 |
| 37,51 | 94,14,92,63 | 15,99,48,56,23,60,31,17,43,8,90,166,100 |
| 37,51,63 | 15,94,14,92 | 99,48,56,23,60,31,17,43,8,90,166,100 |
| 37,51,63,92 | 15,94,14,99 | 48,56,23,60,31,17,43,8,90,166,100 |
| 37,51,63,92,94 | 15,14,99,48 | 56,23,60,31,17,43,8,90,166,100 |
| 37,51,63,92,94,99 | 15,14,56,48 | 23,60,31,17,43,8,90,166,100 |
| 37,51,63,92,94,99# | 15,14,56,48 | 23,60,31,17,43,8,90,166,100 |
| 14 | 15,23,56,48 | 60,31,17,43,8,90,166,100 |
| 14,15 | 60,23,56,48 | 31,17,43,8,90,166,100 |
| 14,15,23 | 60,31,56,48 | 17,43,8,90,166,100 |
| 14,15,23,31 | 60,17,56,48 | 43,8,90,166,100 |
| 14,15,23,31,48 | 60,17,56,43 | 8,90,166,100 |
| 14,15,23,31,48,56 | 60,17,8,43 | 90,166,100 |
| 14,15,23,31,48,56,60 | 90,17,8,43 | 166,100 |
| 14,15,23,31,48,56,60,90 | 166,17,8,43 | 100 |
| 14,15,23,31,48,56,60,90,166 | 100,17,8,43 | — |
| 14,15,23,31,48,56,60,90,166# | 100,17,8,43 | — |
| 8 | 100,17,43 | — |
| 8,17 | 100,43 | — |
| 8,17,43 | 100 | — |
| 8,17,43,100 | — | — |
| 8,17,43,100# | — | — |
生成3个初始段:37,51,63,92,94,99;14,15,23,31,48,56,60,90,166;8,17,43,100。
- 最大值n,最小值m。文件本身升序时只生成1段,长度n;若初始工作区m个元素都大于输入文件剩余所有记录,第一个段只能输出这m个元素,长度最小为m。