文章

164

粉丝

0

获赞

1

访问

44.0k

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

(1)采用类似哈夫曼树的构造思想,每次选取数据元素最少的合并组进行合并

过程如下 合并10,35->45,比较44次

合并40,45->95,比较94次

合并50,60->110,比较109次

合并95,110->205,比较204次

合并205,200->405,比较404次

总共比较了855次

(2)采用类似最小归并树的构造思想构造一颗严格的k叉树,其中k为归并路数,每次选取k个元素最少的数据集合进行归并,若无法构成严格k叉树则需补充虚段。

这样可保证让小序列之间先进行比较,从而尽可能降低比较次数。


评分及理由

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

学生采用了哈夫曼树(最佳归并树)的思想进行合并,合并策略正确,过程描述清晰。但在合并过程中存在计算错误:

  • 第一次合并:10+35=45,比较次数44次(正确)
  • 第二次合并:40+45=85,但学生计算为95,比较次数应为84次,学生计算为94次(错误)
  • 第三次合并:50+60=110,比较次数109次(正确)
  • 第四次合并:85+110=195,但学生计算为205,比较次数应为194次,学生计算为204次(错误)
  • 第五次合并:195+200=395,但学生计算为405,比较次数应为394次,学生计算为404次(错误)
  • 总比较次数应为825次,学生计算为855次(错误)

由于合并过程思路正确但存在多处计算错误,扣3分。得分:4分

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

学生正确描述了采用类似哈夫曼树(最小归并树)的构造思想,说明了每次选取元素最少的数据集合进行归并,并解释了这样做的理由(降低比较次数)。描述完整准确,符合标准答案要求。得分:3分

题目总分:4+3=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发