文章

191

粉丝

0

获赞

0

访问

18.1k

头像
2016年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年10月3日 11:39
阅读数 113


评分及理由

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

学生正确推导了叶结点数量公式。通过总结点数 = 非叶结点数 + 叶结点数,以及边数关系(总结点数-1 = k×非叶结点数),得出叶结点数为 (k-1)m+1。推导过程完整正确,得3分。

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

最多结点情况:学生正确给出了满k叉树的结点数公式 (k^h-1)/(k-1),得3分。

最少结点情况:学生的答案 (k^(h-1)-1)/(k-1)+k 存在逻辑错误。在最少结点情况下,除根结点外,第2到h-1层每层应该只有1个分支结点和k-1个叶结点,最后一层有k个叶结点。学生的计算方式实际上得到的是高度为h-1的满k叉树加上最后一层k个结点,这与正则k叉树最少结点的结构不符。根据标准答案,最少结点数应为 1+(h-1)k。因此扣2分,得3分。

题目总分:3+3=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发