计算机学科专业基础2012 真题档案

(1) 合并过程与总比较次数

合并过程（基于最佳归并树思想）：

1. 第1次合并：A(10) 与 B(35) → 表AB(45)，比较次数为 10+35-1=44。
2. 第2次合并：AB(45) 与 C(40) → 表ABC(85)，比较次数为 45+40-1=84。
3. 第3次合并：D(50) 与 E(60) → 表DE(110)，比较次数为 50+60-1=109。
4. 第4次合并：ABC(85) 与 DE(110) → 表ABCDE(195)，比较次数为 85+110-1=194。
5. 第5次合并：ABCDE(195) 与 F(200) → 最终表(395)，比较次数为 195+200-1=394。

最坏情况下比较的总次数：
825 次（计算：44 + 84 + 109 + 194 + 394 = 825）。

(2) 合并策略与理由

策略：对于 N（N≥2）个不等长升序表，采用类似哈夫曼树（最佳归并树）的构造方法：每次选择当前长度最小的两个表进行合并，直至合并为一个表。

理由：两个表合并的最坏比较次数为两表长度之和减1。优先合并短表可使后续合并中参与的表长度较小，从而最小化总比较次数，达到最佳合并效率。