文章

104

粉丝

0

获赞

0

访问

8.0k

头像
2012年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年10月15日 11:22
阅读数 86


评分及理由

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

学生给出的合并过程为:第一次合并A与B、C与D、E与F;第二次合并AB与CD;第三次合并ABCD与EF。这一合并过程不符合哈夫曼树(最佳归并树)思想,没有优先合并最短的表,导致最坏情况下比较总次数不是最小。根据标准答案,正确的合并顺序应能最小化总比较次数,而学生给出的顺序会导致更高的比较次数。此外,学生计算的最坏情况下总比较次数为635次,与标准答案825次不符,且计算过程未给出详细步骤,无法验证其正确性。因此,合并过程描述不完整且策略错误,计算错误。根据评分说明,按其他策略进行合并且过程描述正确给3分,但学生计算错误扣1分,得2分。

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

学生描述的策略为:n个等长升序表的合并需要⌈log₂n⌉次合并。这一描述错误,因为题目中明确表是不等长的,且合并策略应基于哈夫曼树思想优先合并最短表以最小化比较次数。学生未提到表长差异或哈夫曼树思想,且将“不等长”误写为“等长”(可能为识别错误),但核心逻辑错误。根据评分说明,采用其他策略但能完成合并给2分,但学生策略仅适用于等长表,不适用于本题,且未说明理由,扣1分,得1分。

题目总分:2+1=3分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发