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

admin2015-12-30 35

问题设有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://www.kaotiyun.com/show/GzRi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下列关于胡司战争的叙述错误的一项是()。

元代对边疆地区的统治方式不同于其他三地的一地是()。

国民党的第一次代表大会上通过的《中国国民党第一次全国代表大会宣言》，其内容不包括()

下列选项中，控制了西域政权的是()

巴黎公社采取的带有无产阶级专政性质的措施有()。①公社人员由民主选举产生②没收逃亡资本家的工厂，交给工人合作社管理③取消旧的国家机器，建立：亡人阶级自己的国家机构④工职人员年薪不得超过熟练工人的工资

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

新王朝时期出现了什么类型的墓?()

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

下列叙述中，正确的是()。

一般来说，继电器是由、和三大部分组成。

设随机变量X的概率密度为试求：D(2－3X)．

中药炮制学的定义

血管紧张素Ⅱ受体抑制剂是

依照我国《公司法》，有限责任公司的下列行为中，不需要由代表2/3以上表决权的股东通过并作出决议的是(　　)。

甲对乙享有60万元债权，丙、丁分别与甲签订保证合同，但未约定保证责任的范围和方式。戊以价值30万元的房屋为乙向甲设定抵押并办理了登记。下列关于丙、丁、戊关系的表述中正确的有（　　　）。

税收保全措施适用于()。

某工厂去年12月份的产量是去年1月份产量的a倍，则该厂去年月产量的平均增长率为(其中a∈Q+)()．

计算机408

学硕统考专业

下列关于胡司战争的叙述错误的一项是()。

元代对边疆地区的统治方式不同于其他三地的一地是()。

国民党的第一次代表大会上通过的《中国国民党第一次全国代表大会宣言》，其内容不包括()

下列选项中，控制了西域政权的是()

巴黎公社采取的带有无产阶级专政性质的措施有()。①公社人员由民主选举产生②没收逃亡资本家的工厂，交给工人合作社管理③取消旧的国家机器，建立：亡人阶级自己的国家机构④工职人员年薪不得超过熟练工人的工资

我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说，如炎帝和黄帝两个部落曾战于()，结果黄帝取得了胜利。

新王朝时期出现了什么类型的墓?()

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

下列叙述中，正确的是()。

一般来说，继电器是由________、________和________三大部分组成。

设随机变量X的概率密度为试求：D(2－3X)．

中药炮制学的定义

血管紧张素Ⅱ受体抑制剂是

依照我国《公司法》，有限责任公司的下列行为中，不需要由代表2/3以上表决权的股东通过并作出决议的是( )。

甲对乙享有60万元债权，丙、丁分别与甲签订保证合同，但未约定保证责任的范围和方式。戊以价值30万元的房屋为乙向甲设定抵押并办理了登记。下列关于丙、丁、戊关系的表述中正确的有（ ）。

税收保全措施适用于()。

某工厂去年12月份的产量是去年1月份产量的a倍，则该厂去年月产量的平均增长率为(其中a∈Q+)()．

一般来说，继电器是由、和三大部分组成。

依照我国《公司法》，有限责任公司的下列行为中，不需要由代表2/3以上表决权的股东通过并作出决议的是(　　)。

甲对乙享有60万元债权，丙、丁分别与甲签订保证合同，但未约定保证责任的范围和方式。戊以价值30万元的房屋为乙向甲设定抵押并办理了登记。下列关于丙、丁、戊关系的表述中正确的有（　　　）。