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. O(1)O(1)

B. O(k)O(k)

C. O(log⁡2k)O(\log_2k)

D. 以上都不对

查看答案与解析

答案:C。

选取并维护最小关键字的时间取决于败者树高度,为 O(log⁡2k)O(\log_2k)。

单项选择题 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个初始归并段,问:

  1. 多路平衡归并3趟完成排序,归并路数至少多少?
  2. 操作系统要求同时可用输入输出文件总数不超过15,至少几趟完成?限定该趟数时,可取最低路数多少?
查看答案与解析
  1. 设路数m,r=80,S=⌈logₘ80⌉=3,需m³≥80,解得m≥5,至少5路。
  2. 需m个输入缓冲区、1个输出缓冲区,一个缓冲区对应一个文件,m+1=15得m=14。⌈log₁₄80⌉=2,最少2趟。若限定2趟,m²≥80,最小m=9,即9路平衡归并。

综合应用题 02

原书题目P393 · 解析P396 · 目视转录

文件有4500条记录,磁盘每块75条,内存排序区容纳450条。问:

  1. 可建多少初始段?每段多少记录、占多少块?
  2. 应用几路归并?写出过程及每趟读写块数。
查看答案与解析
  1. 初始段数4500/450=10,每段450条,占450/75=6块。
  2. 内存容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,84314025输出6,3号补15
10,9,22,15,12,84143025输出9,1号补20
10,20,22,15,12,84043125输出10,0号补15
15,20,22,15,12,84403125输出12,4号补37
15,20,22,15,37,84304125输出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个:

  1. 0、3、6、8合并为17。
  2. 9、17、18、20合并为64。
  3. 30、44、60、62合并为196。
  4. 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条记录。

  1. 文件19条记录,关键字依次为51,94,37,92,14,63,15,99,48,56,23,60,31,17,43,8,90,166,100。m=4时可生成几段?各为何?
  2. 任意n>m>0时,第一个初始段长度的最大值、最小值分别是多少?
查看答案与解析
  1. 工作区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,9214,63,15,99,48,56,23,60,31,17,43,8,90,166,100
3751,94,14,9263,15,99,48,56,23,60,31,17,43,8,90,166,100
37,5194,14,92,6315,99,48,56,23,60,31,17,43,8,90,166,100
37,51,6315,94,14,9299,48,56,23,60,31,17,43,8,90,166,100
37,51,63,9215,94,14,9948,56,23,60,31,17,43,8,90,166,100
37,51,63,92,9415,14,99,4856,23,60,31,17,43,8,90,166,100
37,51,63,92,94,9915,14,56,4823,60,31,17,43,8,90,166,100
37,51,63,92,94,99#15,14,56,4823,60,31,17,43,8,90,166,100
1415,23,56,4860,31,17,43,8,90,166,100
14,1560,23,56,4831,17,43,8,90,166,100
14,15,2360,31,56,4817,43,8,90,166,100
14,15,23,3160,17,56,4843,8,90,166,100
14,15,23,31,4860,17,56,438,90,166,100
14,15,23,31,48,5660,17,8,4390,166,100
14,15,23,31,48,56,6090,17,8,43166,100
14,15,23,31,48,56,60,90166,17,8,43100
14,15,23,31,48,56,60,90,166100,17,8,43—
14,15,23,31,48,56,60,90,166#100,17,8,43—
8100,17,43—
8,17100,43—
8,17,43100—
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。

  1. 最大值n,最小值m。文件本身升序时只生成1段,长度n;若初始工作区m个元素都大于输入文件剩余所有记录,第一个段只能输出这m个元素,长度最小为m。