文章

26

粉丝

253

获赞

1

访问

15.2k

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

1 根据这六个有序表中的元素的个数 分别进行比较和合并   先选取元素个数较少的两个表进行合并 先选取表A  B合并成(A B)  在把表(A B)与表C进行合并合并成表( A B C) 在合并表  D E合并成(D E)在把表(A B C) (D E) 合并成(A B C D E)在于表F合并 最终合并成一个升序表(A B  C D E F)

最坏情况下的比较次数  35+45+60+110+200=450

2. 先选取两个表长最小的表进行合并 把合并后的新表加入待合并的有序表的序列 在从中选出两个表长最小的表进行合并 以此类推 直到合并成功

理由 :根据哈夫曼树的思想进行合并 选取两个表长最小的表进行合并

 

 


评分及理由

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

学生给出了合并过程:先合并A和B(10+35),再合并AB和C(45+40),然后合并D和E(50+60),接着合并ABC和DE(85+110),最后合并ABCDE和F(195+200)。这个过程与标准答案中的哈夫曼树合并策略一致,因此合并过程描述正确,得5分。但在计算最坏情况下比较的总次数时,学生给出的计算为35+45+60+110+200=450,这是错误的。正确计算应为每次合并的比较次数之和:A+B合并为10+35-1=44,AB+C合并为45+40-1=84,D+E合并为50+60-1=109,ABC+DE合并为85+110-1=194,ABCDE+F合并为195+200-1=394,总次数为44+84+109+194+394=825。学生未正确应用比较次数公式(m+n-1),且结果错误,因此扣2分。本部分得5分。

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

学生描述了合并策略:先选取两个表长最小的表合并,将新表加入序列,再重复选择最小两个表合并,直到完成。理由中提到了哈夫曼树思想。这与标准答案一致,策略描述正确,理由充分,因此得3分。

题目总分:5+3=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发