首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列关于外部排序说法正确的是( )。
下列关于外部排序说法正确的是( )。
admin
2019-07-18
50
问题
下列关于外部排序说法正确的是( )。
选项
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
学硕统考专业
相关试题推荐
简述《资政新篇》的主要内容。
论述欧洲一体化的进程及影响。
阅读材料并结合背景知识回答问题:材料到17世纪60年代,伟大的科学学会的时代到来了:英国皇家学会、法国科学院先后成立。此前,科学工作在很大程度上仰仗于国王对科学家个人的资助一第谷领取丹麦国王的津贴,开普勒由德意志皇帝资助;或者靠某些科学“爱好者”、赞助者
东晋南朝,经济发展,促进文化繁荣,这一时期,从南方兴起的文化现象?
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:我国银行最早的雏形是唐朝时期出现的()
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
一个使用选择性重传协议的数据链路层协议,如果采用了5位的帧序列号,那么可以选用的最大窗口是()。
随机试题
A.胃底部B.胃窦部C.小肠上部D.回肠E.结肠(2001年第94题)及收铁的主要部位是
合同法的公平原则体现为( )。
背景资料某新建住宅楼工程,建筑面积43200m2,砖混结构,投资额25910万元。建设单位自行编制了招标工程量清单等招标文件,其中部分条款内容为:本工程实行施工总承包模式;承包范围为土建、水电安装、内外装修及室外道路和小区园林景观;施工质量标准为合格;工
计算公司各年营业收入、营业成本和各项费用的年同比增长率,这属于财务报表分析中的()。
导游人员应该在考虑游客旅游动机、身体状况等条件的基础上,灵活机动地搭配、安排旅游活动内容,满足游客需要。在活动安排上,应做到()。
贝克认为:人们从童年期开始通过生活经验建立起来的认知结构图式是()。
公安机关治安行政处置中的命令,是指公安机关为了维护社会治安秩序和公共安全,依法向负有特定义务的人发出的作为、不作为和约束的指令,这种命令又称“警察命令”。()
甲路过偏僻路段,看到其友乙强奸丙的犯罪事实。甲的下列哪一行为构成包庇罪()
DHCP客户端启动时会向网络发出一个Dhcpdiscover包来请求IP地址,其源IP地址为______。
Upto80percentoftimespentonlineatworkiswasted,accordingtoanewstudyfromKansasStateUniversity.Itsuggeststhat
最新回复
(
0
)