41.设有6个有序表 A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。 1）给出完整的合并过程，并求出最坏情况下比较的总次数。 2）根据你的合并过程，描述N（N≥2）个不等长升序表的合并策略，并说明理由。
【参考答案及解析】
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的 Merge（）函数;对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 （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次合并，最多比较次数=85+110-1=194；第5次合并，最多比较次数=195+200-1=394。故，比较的总次数最为：44+84+109+194+394=825。 （2）各表的合并策略是∶在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。 【（1）（2）评分说明】①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给 5分。按其他策略进行合并，过程描述正确，给 3分。②正确算出与合并过程一致的总比较次数，给 2分。若计算过程正确，但结果错误，可给1分。③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给3分。如果采用其他策略，只要能够完成合并，给2分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
本题同时对多个知识点进行了综合考查。对有序表进行两两合并考查了归并排序中的 Merge（）函数;对合并过程的设计考查了哈夫曼树和最佳归并树。外部排序属于大纲新增考点。 （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次合并，最多比较次数=85+110-1=194；第5次合并，最多比较次数=195+200-1=394。故，比较的总次数最为：44+84+109+194+394=825。 （2）各表的合并策略是∶在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。 【（1）（2）评分说明】①对于用类似哈夫曼树（或最佳归并树）思想进行合并，过程描述正确，给 5分。按其他策略进行合并，过程描述正确，给 3分。②正确算出与合并过程一致的总比较次数，给 2分。若计算过程正确，但结果错误，可给1分。③考生只要说明采用的是类似哈夫曼树（或最佳归并树）的构造方法作为合并策略，即可给3分。如果采用其他策略，只要能够完成合并，给2分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！