文章

37

粉丝

0

获赞

7

访问

3.5k

头像
【2012年】408计算机统考真题模拟考试 - 第41题答案笔记
数据结构
发布于2025年5月30日 13:17
阅读数 10

计算机考研408统考历年真题及答案解析

(1) A与B合并,最坏需要35次比较,得到A'(45个元素);A'与C合并,最坏需要45次比较,得到B'(95个元素);D和E合并,最坏需要60次比较,得到C'(110个元素);B'和C'合并,最坏需要110次比较,得到D'(205个元素);D'与F合并,最坏需要205次比较,得到最终的升序表(405个元素)。总次数为35+45+60+110+205=455次比较。
(2) 使用构建哈夫曼树的思想,每次选取两个元素最少的表合并,直到只剩下一个表。理由:对于两个表来说,其最坏比较次数必然为较长者的长度,那么我们的目标就是让较长者的长度达到最短,因此选择构建哈夫曼树让“非叶结点”的值更小。

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发