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

admin2015-12-30 37

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

关于荷马时代的叙述，不正确的是()。

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

三国时期，魏、蜀、吴灭亡的先后顺序是()。

同盟会影响下发生的第一次大规模武装起义的地点在()。

以下选项中中原千朝对西藏管辖设置机构对应有误的一项是()。

全国高校院系调整的具体时间是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

JK触发器，当JK为()时，触发器处于置0状态。

确定资产的现时成本是指

下列关于正常新生儿的描述，正确的是

上市公司配股的信息披露中，假设T日为股权登记日，()日至T+5日，刊登配股提示性公告。

根据《刑法》，在渎职罪中，不要求犯罪主体一定是税务机关工作人员的有()。

演出风格朴实、风趣，贴近江淮民众的生活，故事情节来源于基层，能与观众产生共鸣。这是()最大的优势。

党领导人民治理国家的基本方略是()。

下列各句中，没有语病的一句是：

关于物质运动和静止，正确的说法有(　　)

计算并填写下表：

计算机408

学硕统考专业

关于荷马时代的叙述，不正确的是()。

毛泽东从事了大量理论研究工作，系统阐述了新民主主义的理论，下列选项中，不属于这一范围的是()

三国时期，魏、蜀、吴灭亡的先后顺序是()。

同盟会影响下发生的第一次大规模武装起义的地点在()。

以下选项中中原千朝对西藏管辖设置机构对应有误的一项是()。

全国高校院系调整的具体时间是()。

(1)以太网采用了曼彻斯特编码，一个比特的数据需要两个信号来传输，那么为了达到100Mbps的数据传送速率，需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节，那么发送一个最小帧需要的时间T1=64×8／(100×106)，

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

JK触发器，当JK为()时，触发器处于置0状态。

确定资产的现时成本是指

下列关于正常新生儿的描述，正确的是

上市公司配股的信息披露中，假设T日为股权登记日，()日至T+5日，刊登配股提示性公告。

根据《刑法》，在渎职罪中，不要求犯罪主体一定是税务机关工作人员的有()。

演出风格朴实、风趣，贴近江淮民众的生活，故事情节来源于基层，能与观众产生共鸣。这是()最大的优势。

党领导人民治理国家的基本方略是()。

下列各句中，没有语病的一句是：

关于物质运动和静止，正确的说法有( )

计算并填写下表：

关于物质运动和静止，正确的说法有(　　)