文章

37

粉丝

0

获赞

0

访问

1.8k

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


评分及理由

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

学生作答中,合并过程采用了哈夫曼树思想,第一次合并A和B(10和35),第二次合并AB和C(45和40),第三次合并D和E(50和60),这些步骤正确。但第四次合并时,学生有两种识别结果:一种是将ABC与DE合并(85和110),另一种是将ABC与F合并(85和200)。标准答案中第四次合并是ABC与DE(85和110),第五次是ABCDE与F(195和200)。学生第一次识别中第四次合并写为ABC与DE(但计算比较次数时误写为200+85-1=284,实际应为85+110-1=194),第五次合并写为ABCDE与F(但计算比较次数时误写为285+110-1=394,实际应为195+200-1=394)。学生第二次识别中第四次合并错误地将ABC与F合并(85和200),第五次合并ABCDEF与DE(285和110),这不符合哈夫曼树策略(应优先合并短表),导致合并顺序错误。

计算总比较次数时,学生第一次识别结果为915次,但计算过程混乱(如385+285+85+45+110-5),实际正确计算应为44+84+109+194+394=825次。学生第二次识别结果也为915次,但基于错误合并顺序。

根据评分标准:①合并过程描述部分正确(采用了哈夫曼思想但第四次合并顺序错误),给3分(标准答案中按其他策略合并给3分)。②计算总比较次数错误,且未给出正确值,扣2分(但计算部分有尝试,给1分)。因此,(1)部分得分4分。

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

学生描述了合并策略:选取两个长度最短的表合并,重复直至完成。这符合哈夫曼树思想,与标准答案一致。因此,(2)部分得3分。

题目总分:4+3=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发