文章

59

粉丝

0

获赞

1

访问

12.2k

头像
2016年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年7月20日 12:54
阅读数 89

(1)每个非叶节点都有k个孩子,说明节点的度数均为k,总结点数为总度数+1,而m个非叶节点对应有mk条边,设叶节点数量为n1.则有mk=m+n1-1,所以叶节点数量为

mk-m+1
(2)当每一层所有位置均有节点,即为满k叉树时,节点最多为(1-k^h)/1-k,当h-1层所有位置均有节点,第h层仅有k个节点时,结点数最少,为(1-k^h-1)/1-k + k


评分及理由

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

学生正确推导了正则k叉树的叶结点数量公式,思路与标准答案一致,但最终表达式未化简为\((k - 1)×m + 1\),而是直接给出\(mk - m + 1\)。虽然形式不同,但数学等价,因此不扣分。

得分:3分

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

学生正确分析了最多结点情况(满k叉树),并给出了正确的等比数列求和公式\(\frac{1 - k^h}{1 - k}\)(与标准答案等价)。但在最少结点情况的分析中,公式\(\frac{1 - k^{h-1}}{1 - k} + k\)存在逻辑错误:该公式实际计算的是满\(h-1\)层树加上第\(h\)层的\(k\)个结点,但未正确体现“每层仅保留1个分支结点”的最小化条件,导致结果与标准答案\(1 + (h - 1)×k\)不符。

最多结点部分得分:3分(完全正确)

最少结点部分得分:0分(逻辑错误)

(2)总分:3分

题目总分:3+3=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发