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

admin2019-07-18  28

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

选项 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
0

最新回复(0)