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

admin2015-12-30 24

问题设有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个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

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

一个使用选择性重传协议的数据链路层协议，如果采用了5位的帧序列号，那么可以选用的最大窗口是()。

在下列查找的方法中，平均查找长度与结点个数n无关的查找方法是()。

假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是____。

下述关于青霉素抗菌谱的叙述，错误的是

牙齿磨耗程度取决于

现行《海关法》是经哪届全国人民代表大会修改的?()

下列兄弟行辈中长幼排行的次序中表示老四的是?()

有关财政，错误的说法是（）。

设n(n≥3)阶矩阵的秩为n－1，则a必为()

Inthespanof18months,IsaacNewtoninventedcalculus,constructedatheoryofoptics,explainedhowgravityworksanddiscov

有一个虚拟页式存储管理系统，分配给某个进程3个页框(假设开始时页框为空)。某进程执行时的页面访问序列是：0，6，0，1，5，1，5，4，1，2，5，2，4，5，2，3，5，3。若采用最佳页面置换算法(OPT)，缺页次数为()。

Dieserausl?ndisch__TouristfragtmichnachdemWeg.

Theremustbefewquestionsonwhichresponsibleopinionissoutterlydividedasonthatofhowmuchsleepweoughttohave.Th