设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：给出完整的合并过程，并求出最坏

admin2015-12-30 20

问题设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。
请回答下列问题：
给出完整的合并过程，并求出最坏情况下比较的总次数。

选项

答案对于长度分别为m，n的两个有序表的合并，最坏情况下是一直比较到两个表尾元素，比较次数为m+n-1次。故，最坏情况的比较次数依赖于表长，为了缩短总的比较次数，根据哈夫曼树(最佳归并树)思想的启发，可采用如图所示的合并顺序。 [*] 根据上图中的哈夫曼树，6个序列的合并过程为：第1次合并：表A与表B合并，生成含有45个元素的表AB；第2次合并：表AB与表C合并，生成含有85个元素的表ABC；第3次合并：表D与表E合并，生成含有110个元素的表DE；第4次合并：表ABC与表DE合并，生成含有195个元素的表ABCDE；第5次合并：表ABCDE与表F合并，生成含有395个元素的最终表。由上述分析可知，最坏情况下的比较次数为：第1次合并，最多比较次数=10+35-1=44；第2次合并，最多比较次数=45+40-1=84；第3次合并，最多比较次数=50+60-1=109；第4次合并，最多比较次数i=85+110-1=194；第5次合并，最多比较次数=195+200-1=394。故，比较的总次数最多为：44+84+109+194+394=825。

解析

转载请注明原文地址:https://jikaoti.com/ti/yefjFFFM

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

罗斯福新政的中心措施是对()的调整。

30年代，对斯大林的个人崇拜达到相当严重的程度，这一现象的社会基础是()

维也纳会议争论的焦点问题是()。

下列关于戈尔巴乔夫上台以后发生的事件，按时间先后顺序排列正确的是()。①苏联进行政治改革②苏联进行经济改革③八一九事件④苏联解体

以下关于玛雅天文学成就的叙述，正确的是()。①玛雅人创造的“玛雅历”是一种太阳历。②玛雅人的历法，与宗教祭祀有着密切联系。③奇钦.伊查天文观象台是玛雅天文学的伟大成就。④玛雅人的历法中，采用了12进位法。

1984年，《中共中央关于经济体制改革的决定》中强调，商品经济的充分发展是社会经济发展不可逾越的阶段，市场调节的辅助性作用不可缺少，并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

[*]对应的微指令如下：ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001

血清铁减低，总铁结合力增高及转铁蛋白饱和度减低见于

育龄妇女停经60天，阴道流血3天，血量增多，伴腹痛下坠。妇检子宫增大如孕50天大小，宫口开一指，尿妊娠试验阳性，应首先考虑

依据《特种作业人员安全技术培训考核管理规定》，特种作业人员有()的，复审或者延期复审不予通过。

竣工图是真实、准确、完整反映和记录各种地下和地上建筑物、构筑物等详细情况的技术文件，竣工图应由承包人根据()提交。

大量存款人的挤兑行为叮能会导致商业银行面临()危机。

通常作为参考蛋白质使用的食物蛋白质是()。

根据继承法的有关规定，下列有关遗嘱效力的表述，正确的有()。

测试是软件开发的重要内容，应从以下哪个阶段开始制订测试计划?

Exceptionalchildrenaredifferentinsomesignificantwayfromothersofthesameage.Forthesechildrentodeveloptheirfull