2012年计算机学科专业基础综合试题 - 第41题回答
（1）1.将A和B合并，比较次数为44次
2.将AB与C合并，比较次数为84次
3.将D与E合并，比较次数为109次
4.将ABC与DE合并，比较次数为194次
5将ABCDE与F合并，比较次数为394次，总比较次数为44+84+109+194+394=825次
（2）
采用 贪心算法（类似哈夫曼编码），每次选择当前最小的两个表 进行合并，直到只剩一个表。
理由：
- 最小化比较次数：每次合并较小的表可以避免较大的表被多次比较，从而减少总比较次数。
- 最优子结构：该问题具有贪心选择性质，局部最优解能构成全局最优解。
评分及理由
（1）得分及理由（满分7分）
学生给出了完整的合并过程，并且每一步的比较次数计算正确，总比较次数也正确。合并过程符合哈夫曼树的思想，因此可以给满分7分。
（2）得分及理由（满分3分）
学生正确描述了合并策略，即采用类似哈夫曼树（贪心算法）的思想，每次选择当前最小的两个表进行合并，并给出了合理的理由。因此可以给满分3分。
题目总分：7+3=10分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发