首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列关于外部排序说法正确的是( )。
下列关于外部排序说法正确的是( )。
admin
2019-07-18
26
问题
下列关于外部排序说法正确的是( )。
选项
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
学硕统考专业
相关试题推荐
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,其名义是()。
第二次世界大战后,资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力
中国共产党打响武装反抗国民党反动派第一枪的事件是()。
下列明末清初来华传教士,按时间顺序排列,正确的是()。
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:随着商业的发展,唐朝在货币和金融方面有一些重要的进步,以下表述全面的是()
下列选择中,()不是操作系统关心的主要问题。
一组记录的关键字为{25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序表,用归并排序方法对该序列进行一趟归并后的结果是()。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后,得到IP地址都不一样,可能吗?为什么?
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
随机试题
男性,30岁,上腹部痛7小时后转移到右下腹,3天后右下腹可触及一界限不清、不活动、压痛性包块,体温38.2℃。WBC16×109/L。合理的处理方式是
主要参与细胞免疫应答的是
患者,女,29岁。初产妇。宫内妊娠37周,胎膜破超过3天,原发性宫缩乏力,宫口扩张慢,体温连续两次38℃以上,宫缩间歇底压痛明显,疑有宫内感染,拟行剖宫术。适宜的剖宫产手术方式是
下列关于仓储合同特征的表述不正确的是()
分析用控制图的调整过程即是()不断改进的过程。
湖南苗族在秋收完成后,还要举办大祭神农的节庆,苗民称为()。
一般将()方法运用于劳动关系协调中的个人或小组问题的解决。
依据《普通高中美术课程标准(实验)》,高中生“通过美术学习活动,学会用艺术思维的方式认识世界,学习艺术表现和交流的方法”。这一表述所体现的理念是()。
泳协在网上发了一篇帖子说有一个游船停靠在距离游泳区30米的位置,并且向游泳区倾倒食物残渣。但实际情况是政府为了疏通航道,临时将这艘游船调到这里停靠的,且停靠区域实际距离游泳区60米。如果领导让你负责与泳协沟通。你会如何进行?
五育并举的教育方针
最新回复
(
0
)