文章

261

粉丝

19

获赞

402

访问

86.4k

头像
2012年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年11月28日 16:53
阅读数 80


评分及理由

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

学生给出的合并过程为:第一次合并A和B、C和D、E和F;第二次合并AB和CD;第三次合并ABCD和EF。这个合并顺序不符合哈夫曼树(最佳归并树)思想,因为合并顺序没有优先选择最短的表进行合并。例如,第一次合并中C(40)和D(50)合并,而不是选择更短的A(10)和B(35)合并。因此,合并策略不正确,但能够完成合并过程。根据标准答案评分说明,按其他策略进行合并且过程描述正确给3分。

计算最坏情况下比较总次数时,学生给出的计算公式和结果(198次)完全错误。正确计算应基于每次合并的两个表长之和减1,然后累加。学生未给出具体计算过程,且结果与标准答案(825次)相差甚远。根据标准答案评分说明,计算错误扣分,但因其合并过程描述正确,计算部分可给0分。

因此,本部分得分:3分(合并过程描述正确但策略错误)+ 0分(计算错误)= 3分。

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

学生描述的策略是“递归进行两两之间合并有序表,在合并两表中采用二路归并进行合并新表的排序直至有序”。这仅描述了一般的两两合并方法,没有说明如何选择合并顺序以优化比较次数,未体现哈夫曼树思想。根据标准答案评分说明,采用其他策略但能够完成合并给2分。

因此,本部分得分:2分。

题目总分:3+2=5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发