首页 > 试题广场 >

将 6 个表最终合并成一个升序表

[问答题]

设有 6 个有序表 A、 B、 C、 D、 E、 F，分别含有 10、 35、 40、 50、 60 和 200 个数据元素，各表中元素按升序排序。要求通过 5 次两两合并，将 6 个表最终合并成一个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题：
（1）给出完整的合并过程，并求出最坏情况下比较的总次数。
（2）根据你的合并过程，描述 n（ n≥2）个不等长升序表的合并策略，并说明理由。

查看答案及解析

城市里的养猫者

（1）6 个表的合并顺序如下图所示，实际上相当于以各有序表的长度为权值，构建一棵赫夫曼树。

对应于合并过程的赫夫曼树
根据该赫夫曼树，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 个元素的表 ABCDEF。

由于合并两个长度分别为m 和 n 的有序表，最坏情况下需要比较 m+n-1 次，故最坏情况下比较的总次数计算如下。
第1 次合并：最多比较次数=10+35-1=44；
第2 次合并：最多比较次数=45+40-1=84；
第3 次合并：最多比较次数=50+60-1=109；

第4 次合并：最多比较次数=85+110-1=194；
第5 次合并：最多比较次数=195+200-1=394。
比较的总次数最多为：44+84+109+194+394=825。
（2）各表的合并策略：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序，可以借用赫夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。