🏷️ 知识点：排序比较

外部排序和内部排序的主要区别是()。

A. 内部排序的数据量小，而外部排序的数据量大 B. 内部排序不涉及内、外存数据交换，而外部排序涉及内、外存数据交换 C. 内部排序的速度快，而外部排序的速度慢 D. 内部排序所需的内存小，而外部排序所需的内存大

[tag_link]

正确答案：B

下列关于外部排序的说法中，正确的是()。

A. 置换选择排序得到的初始归并段的长度一定相等 B. 内外存交换数据的时间只占总排序时间的一小部分 C. 败者树是一棵完全二叉树 D. 外部排序不涉及对文件的读/写操作

[tag_link]

正确答案：C

多路平衡归并的作用是()。

A. 减少归并趟数 B. 减少初始归并段的个数 C. 便于实现败者树 D. 以上都对

[tag_link]

正确答案：A

设在磁盘上存放有375000个记录，进行5路平衡归并排序，内存工作区能容纳600个 记录，为把所有记录排好序，需要进行()趟归并排序。

A. 3 B.4 C. 5 D.6

[tag_link]

正确答案：B

在下列关于外部排序过程输入/输出缓冲区作用的叙述中，不正确的是()。

A. 暂存输入/输出记录 B. 内部归并的工作区 C. 产生初始归并段的工作区 D. 传送用户界面的消息

[tag_link]

正确答案：D

若只需3趟排序就可完成64个元素的多路归并排序，则选取的归并路数最少是()。

A. 2 B.3 C. 4 D.5

[tag_link]

正确答案：C

置换-选择排序的作用是()。

A. 用于生成外部排序的初始归并段 B. 完成将一个磁盘文件排序成有序文件的有效的外部排序算法 C. 生成的初始归并段的长度是内存工作区的2倍 D. 对外部排序中输入/归并/输出的并行处理

[tag_link]

正确答案：A

一个无序文件的n 个记录采用置换选择排序产生 m 个有序段，则m 和 n 的关系是()。

A. m 与 n 成正比 B. m=l og₂n C.m 与 n 成反比 D. 以上都不对

[tag_link]

正确答案：D

在由k 路归并构建的败者树中选取一个关键字最小的记录，则所需时间为()。

A. O(1) B.O(k) C.O(log₂k) D. 以上都不对

[tag_link]

正确答案：C

下列关于小顶堆和败者树的说法中，正确的是()。 I. 败者树从下往上维护，每上一层，只需和失败结点比较1次 Ⅱ.败者树的每次维护，必定要从叶结点一直走到根结点，不可能从中间停止 Ⅲ.堆从上往下维护，每下一层，若其左右孩子均不为空，则需比较2次 IV. 堆的每次维护，必定要从根结点一直走到叶结点，不可能从中间停止

A. I 、Ⅲ B.Ⅱ 、Ⅲ C.I 、Ⅱ 、Ⅲ D.I 、Ⅲ 、IV

[tag_link]

正确答案：C

最佳归并树在外部排序中的作用是()。

A. 完成m 路归并排序 B. 设计m 路归并排序的优化方案 C. 产生初始归并段 D. 与锦标赛树的作用类似

[tag_link]

正确答案：B

在由m 个初始归并段构建的k 阶最佳归并树中，不需要补充虚段，则度为k 的结点个数 是 ( ) 。

A. (m-1)/k B.mlk C. (m-1)/(k-1) D. 无法确定

[tag_link]

正确答案：C

若某个文件经内部排序得到80个初始归并段，试问： 1)若使用多路平衡归并执行3趟完成排序，则应取得的归并路数至少应为多少? 2)若操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归 并至少需要几趟可以完成排序?若限定这个趟数，可取的最低路数是多少?

[tag_link]

B

假设文件有4500个记录，在磁盘上每个块可放75个记录。计算机中用于排序的内存区 可容纳450个记录。试问： 1)可以建立多少个初始归并段?每个初始归并段有多少记录?存放于多少个块中? 2)应采用几路归并?请写出归并过程及每趟需要读/写磁盘的块数。

[tag_link]

C

设初始归并段为(10,15,31),(9,20),(22,34,37),(6,15,42),(12,37),(84,95)。试利用败者 树进行m 路归并，手工执行选择最小的5个关键字的过程。

[tag_link]

A

给出12个初始归并段，其长度分别为30,44,8,6,3,20,60,18,9,62,68,85。现要做4路外 归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。

[tag_link]

B