文章

78

粉丝

0

获赞

0

访问

8.0k

头像
2012年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月23日 16:30
阅读数 56

(1)最小比较次数就是构建哈夫曼树的过程,每次选取当前最小的2个有序表进行合并,最坏情况下比较次数是带权路径长度830
(2)N个不等长的序列根据数据长度构建哈夫曼树,这样的带权路径长度最下,即比较次数最小


评分及理由

(1)得分及理由(满分7分)

学生正确指出了合并策略是“构建哈夫曼树的过程,每次选取当前最小的2个有序表进行合并”,这与标准答案的思路一致,得5分。但学生给出的最坏情况下比较的总次数为830,而标准答案计算出的正确结果是825。由于计算错误,扣2分。因此,本小题得分为5分。

(2)得分及理由(满分3分)

学生正确描述了合并策略:“N个不等长的序列根据数据长度构建哈夫曼树,这样的带权路径长度最小,即比较次数最小”,这与标准答案一致。因此,本小题得分为3分。

题目总分:5+3=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发