文章

26

粉丝

0

获赞

0

访问

1.3k

头像
2025 年 5 月第 1 次 408 月考试卷 - 第42题回答
数据结构
发布于2025年12月7日 21:53
阅读数 37

(1) 不一定。

最长编码长度:N 

最短编码长度 : 1

 

(2)    a*logN

 

(3)   

编码后的长度最少为 a*M bit

压缩比是 a 

 


评分及理由

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

学生回答“不一定”是正确的,因为对于频率相同的字符,哈夫曼树可以构造出所有编码长度相同的满二叉树,但这不是唯一的构造方式,如果合并顺序不同,也可能得到非等长编码的树。然而,学生给出的最长编码长度“N”和最短编码长度“1”是完全错误的。对于N个频率相同的字符,哈夫曼编码长度范围在1到N-1之间,但具体到本题条件(N为2的整数次幂,频率相同),最优构造(也是题目隐含所指)是等长编码,长度为log₂N。学生答案与标准答案不符,且给出了具体但错误的数值。因此扣分严重。得1分(仅因“不一定”判断正确)。

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

学生答案为“a*logN”。标准答案为“N×log₂N”。WPL的计算公式是∑(频率×编码长度)。每个字符频率为a,编码长度为log₂N,共有N个字符,所以WPL = a × N × log₂N。学生的答案中缺少了字符个数N,因此是错误的。得0分。

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

学生答案中,编码后最少长度为“a*M bit”,压缩比为“a”。
首先,编码后长度:原题中字符频率均为a,但这是针对构造哈夫曼树时的N个字符的频率设定。在编码长度为M的序列时,所有字符出现且频率相同,意味着序列中每个字符的出现概率相等,其最优编码长度就是log₂N bit。因此总编码长度为 M × log₂N bit。学生的答案“a*M”混淆了字符的出现频率(权值a)和编码长度,是错误的。
其次,压缩比:压缩前按ASCII码(7bit或8bit,题目假设为7bit)计算,长度为7M bit。压缩后长度为M × log₂N bit。因此压缩比为 (M × log₂N) / (7M) = log₂N / 7。学生的答案“a”同样是错误的。
该小题两个部分答案均错误。得0分。

题目总分:1+0+0=1分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发