文章
164
粉丝
0
获赞
1
访问
44.0k
(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分)
学生采用了哈夫曼树(最佳归并树)的思想进行合并,合并策略正确,过程描述清晰。但在合并过程中存在计算错误:
由于合并过程思路正确但存在多处计算错误,扣3分。得分:4分
(2)得分及理由(满分3分)
学生正确描述了采用类似哈夫曼树(最小归并树)的构造思想,说明了每次选取元素最少的数据集合进行归并,并解释了这样做的理由(降低比较次数)。描述完整准确,符合标准答案要求。得分:3分
题目总分:4+3=7分
登录后发布评论
暂无评论,来抢沙发