2. 考研
  3. 下列关于外部排序说法正确的是( )。

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

admin2019-07-18  30
问题 下列关于外部排序说法正确的是(    )。
选项 A、内存与外设交换信息的时间只是外排序总时间的一小部分
B、外部排序就是在外存上进行排序，无需内存参与
C、败者树是一棵完全二叉树
D、置换一选择排序得到的初始归并段长度一定相等
答案C
解析 A：影响外排序时间的主要因素就是内存与外设交换信息的总次数，所以A错误。
    B：外部排序也是在内存上进行排序，只不过需要分为多步而已，所以B错误。
    C：从败者树的构建方式可知，败者树是一棵完全二叉树，所以C正确。
    补充知识点：败者树和堆有什么区别?
    提示：外排序中败者树和堆排序的区别在于：
    (1)败者树是在双亲结点中记下刚进行完的这场比赛的败者，而让胜者去参加更加高一层的比赛，便可得到一棵败者树。而堆排序可看做一种胜者树，即双亲结点表示其左右孩子中的胜者。
    (2)在败者树中，参加比较的n个关键字全部为叶子结点，双亲即为其左、右子女的败者，败者树中结点总数为2n一1，加上冠军结点恰好为2n。而堆是由n个关键字组成的完全二叉树，每个关键字作为树中的一个结点，根是n个关键字中的胜者，树中结点总数为n。
    D：使用置换-选择排序得到的初始归并段长度不一定相等，从最佳归并树构造赫夫曼树的过程也可以得到答案，所以D错误。
  外排序的基本过程：
  基于磁盘进行的排序多使用归并排序方法。其排序过程主要分为以下两个阶段：  
(1)建立用于外排序的内存缓冲区。根据它们的大小将输入文件划分为若干段，用某种内排序方法对各段进行排序。经过排序的段叫做初始归并段。当它们生成后就被写到外存中。   
(2)按归并树模式，把(1)生成的初始归并段加以归并，一趟趟扩大归并段和减少归并段数，直到最后归并成一个大归并段为止。    例如：设有一个包含4500个记录的输入文件，现用一台其内存至多可容纳750个记录的计算机对该文件进行排序。输入文件放在磁盘上，磁盘每个页块可容纳250个记录，这样全部记录可存储在4500／250=18个块中。输出文件也放在磁盘上，用以存放归并结果。由于内存中可用于排序的存储区域能容纳750个记录，所以内存中恰好能存3个块的记录。在外排序一开始，把18块记录每3块一组读入内存。利用某种内排序方法进行内排序，形成初始归并段，再写回外存。总共可得到6个初始归并段，然后一趟一趟进行归并排序，如图1-9所示。
转载请注明原文地址:https://kaotiyun.com/show/gPCi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)