首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下列关于外部排序说法正确的是( )。
下列关于外部排序说法正确的是( )。
admin
2019-07-18
47
问题
下列关于外部排序说法正确的是( )。
选项
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
学硕统考专业
相关试题推荐
()是宋代为支付军政费用而筹措的一宗款项。同时又是各地为筹措这项经费而加征的苛捐杂税的总名称
完整地表述电磁场理论的物理学家是()。
第二次工业与第一次工业革命相比较,其新特点是()。①科学和技术真正结合起来②第二次工业革命几乎同时发生在几个先进的资本主义国家③与第一次工业革命交叉进行④使社会第一次分裂为工人阶级和资产阶级
利玛窦与徐光启合作翻译的(),介绍了曾经流行于欧洲的欧几里得平面几何的系统理论,大大地丰富了中国古代几何学的内容。
下列哪两个国家是第二次工业革命的发源地和“中心”?
“瓜步之战”发生在下列哪两个政权之间?()
晚清时期下列武装力量出现的先后顺序是
A、1243B、4312C、2134D、3214D图的BFS遍历。D选项,首先访问结点3,与3邻接的结点4、2都未曾访问过,故3后面因该为2、4(或4、2),故D错。
某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节,按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。
某计算机字长为16位,主存地址空间大小为128KB,按字编址。采用单字长指令格式,指令各字段定义如图B-4所示。转移指令采用相对寻址方式,相对偏移量用补码表示,寻址方式定义见表B-1。请回答下列问题:该指令系统最多可有多少条指令?该计算机最多有
随机试题
2003年5月,马某出国旅游归来,在接受甲省乙市海关检查后,乙市海关以马某携带淫秽光盘为由将其留置3天,并扣留了马某随身携带的行李。据此,回答以下各题。若马某因不服海关扣押财产决定申请复议,行政复议机关逾期不作决定的,申请人可以在复议期满之日起几日内向
与消化性溃疡发生无关的因素是
对于急性期伴有渗出的皮炎湿疹类损害,首选治疗是
Ⅱ型呼吸衰竭的氧疗原则是
9月龄种鸡群,产蛋率和种蛋孵化率偏低,部分鸡消瘦,腹部膨大;剖检见肝脏、肾脏、法氏囊、性腺、脾脏等处有肿块,组织病理学检查见肿块主要由大小一致的淋巴细胞组成。该病可能是
顺经汤的组成药物有:
下列各项中,进项税额不需要做转出处理的是()。
将考生文件夹下GOLDEER文件夹中的文件DOSZIP.OLD的隐藏和存档属性撤销。
Beingassertiveisbeingabletocommunicatewithotherpeopleclearly.Ifyoufeltthatyouhadexpressedwhatwasimportantto
A、Theylikedtraveling.B、Thereasonsareunknown.C、Theyweredrivenoutoftheirhomes.D、Theywantedtofindabetterplacet
最新回复
(
0
)