文章
4
粉丝
72
获赞
0
访问
77
⑴解:采用哈夫曼树的思想,每次合并都取最短的两个有序表合并,合并过程:第一次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分
登录后发布评论
暂无评论,来抢沙发