文章
225
粉丝
0
获赞
1
访问
11.1k

评分及理由
(1)得分及理由(满分7分)
学生给出的合并过程与标准答案一致:第1次合并A(10)与B(35)生成AB(45);第2次合并AB(45)与C(40)生成ABC(85);第3次合并D(50)与E(60)生成DE(110);第4次合并ABC(85)与DE(110)生成ABCDE(195);第5次合并ABCDE(195)与F(200)生成最终表。该过程符合哈夫曼树(最佳归并树)思想,合并顺序正确,因此合并过程描述得5分。
最坏情况下比较次数的计算:学生正确计算了每次合并的比较次数(10+35-1=44,45+40-1=84,50+60-1=109,85+110-1=194,195+200-1=394),但在第二层比较次数求和时误写为193(实际应为84+109=193),但后续总次数计算中实际使用了正确的分项值(44+193+194+394=825),其中193由84和109组成,与标准答案一致。计算过程正确,结果正确,但第二层表述有误,因误写不扣分,故比较次数计算得2分。
本小题总分:5+2=7分。
(2)得分及理由(满分3分)
学生明确描述合并策略为“采用哈夫曼树构造的思想,每次选当前归并段中数据元素最少的段进行归并”,这与标准答案一致,理由充分(比较次数与树WPL正相关)。因此得3分。
题目总分:7+3=10分
登录后发布评论
暂无评论,来抢沙发