文章

4

粉丝

72

获赞

0

访问

77

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

⑴解:采用哈夫曼树的思想,每次合并都取最短的两个有序表合并,合并过程:第一次A和B合并成a1,第二次a1与C合并成a2,第三次D和E合并成a3,第四次a2和a3合并成a4,第五次a4和F合并成最终的有序表a5.

最坏的情况是每次合并,最小的表都要和最大的表中每个元素比较,所以总次数为35+45+60+110+200=450。

⑵结合(1)中思想,每次合并取当前有序表中最小的两个,这样做总合并数为N,且最坏情况下比较的总次数最小。

 


评分及理由

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

学生正确采用了哈夫曼树的思想进行合并,合并过程描述正确(第一次合并A和B,第二次合并结果与C,第三次合并D和E,第四次合并前两次结果,第五次合并结果与F),符合标准答案的合并策略,因此过程描述部分可得5分。但在计算最坏情况下比较的总次数时,学生计算错误(错误地直接相加表长:35+45+60+110+200=450),而正确计算应为每次合并的比较次数之和(即44+84+109+194+394=825)。由于计算过程错误,但合并策略正确,根据标准答案评分说明,计算部分扣1分(若计算过程正确但结果错误可给1分,但此处计算方式完全错误,故不给分)。因此(1)部分得分为5分(过程描述分) + 0分(计算分) = 5分。

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

学生正确描述了合并策略(每次合并取当前有序表中最小的两个),并说明理由(最坏情况下比较的总次数最小),与标准答案一致。因此(2)部分得3分。

题目总分:5+3=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发