数据结构
2012-41
设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。
1）给出完整的合并过程，并求出最坏情况下比较的总次数。
2）根据你的合并过程，描述N（N≥2）个不等长升序表的合并策略，并说明理由。
答案
(1) 合并过程与总比较次数
合并过程（基于最佳归并树思想）：
- 第1次合并：A(10) 与 B(35) → 表AB(45)，比较次数为 10+35-1=44。
- 第2次合并：AB(45) 与 C(40) → 表ABC(85)，比较次数为 45+40-1=84。
- 第3次合并：D(50) 与 E(60) → 表DE(110)，比较次数为 50+60-1=109。
- 第4次合并：ABC(85) 与 DE(110) → 表ABCDE(195)，比较次数为 85+110-1=194。
- 第5次合并：ABCDE(195) 与 F(200) → 最终表(395)，比较次数为 195+200-1=394。
最坏情况下比较的总次数：
825 次（计算：44 + 84 + 109 + 194 + 394 = 825）。
(2) 合并策略与理由
策略：对于 N（N≥2）个不等长升序表，采用类似哈夫曼树（最佳归并树）的构造方法：每次选择当前长度最小的两个表进行合并，直至合并为一个表。
理由：两个表合并的最坏比较次数为两表长度之和减1。优先合并短表可使后续合并中参与的表长度较小，从而最小化总比较次数，达到最佳合并效率。