首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列关于外部排序说法正确的是( )。
下列关于外部排序说法正确的是( )。
admin
2019-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
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述《资政新篇》的主要内容。
清政府被迫签订丧权辱国的《辛丑条约》后,彻底沦为“洋人的朝廷”。最能印证这一说法的是,清政府()
下列对近代社会思潮产生的先后顺序排列正确的是()。①人文主义②自由主义③理性主义④重商主义
严复翻译的《天演论》一书的出版时间是()。
下列关于后三头同盟的叙述,正确的是()。
最早以立法形式巩固大化改新成果的法令是()。
下列关于民族大迁徙的说法不正确的是()。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
试就MutualExclusion、Progress、BoundedWaiting论述以下解决双进程临界区问题的算法是错误的:ProcessPO:do{flag[0]=true;While(flag[1]);
请利用队列的基本操作写出判定一棵二叉树是否为完全二叉树的算法。要求以二叉链表作为二叉树的存储结构。函数原型为:intIsFull_Bitree(BitreeT)。
随机试题
血红蛋白的主要功能是()。
DIC最常见的病因是
因其他疾病切除的子宫连续切片检查中发现,10%~30%在子宫肌层中有子宫内膜组织,目前常采用的诊断深度标准是
下列各项,属实热证的是
在贷款担保中,借款人将其动产交由债权人占有的方式属于()。
一般而言,资本成本最低的筹资方式是()。
2015年,甲、乙、丙、丁各出资2万元、3万元、5万元、4万元,购买一台大型柴油机。三人约定按照出资比例分享权利和承担义务。2016年,甲由于经营超市亏损倒闭,准备将自己手中的份额以1.5万元的价格出售给戊,甲通知了乙和丙,唯独忘记通知丁。甲在通知中仅载明
要引导人们发扬()精神,提高民族自尊心、自信心和自豪感,以热爱祖国、报效人民为最大光荣,以损害祖国利益、民族尊严为最大耻辱,积极投身于建设中国特色社会主义伟大事业。
设AL=0EOH,CX=3,执行RCL,AL,CL指令后,CF的内容为( )。
下列数据结构中,属于非线性结构的是( )。
最新回复
(
0
)