文章

313

粉丝

0

获赞

0

访问

34.9k

头像
2016年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年12月9日 18:40
阅读数 10


评分及理由

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

学生第一次识别结果为“叶结点有 \( m^{k + 1}-m \) 个”,此表达式明显错误,与标准答案 \( (k-1)m + 1 \) 不符,属于逻辑错误。第二次识别结果为“叶结点有$mk + 1 - m$个”,此表达式可整理为 \( m(k-1) + 1 \),与标准答案 \( (k-1)m + 1 \) 完全一致,思路和结果均正确。根据“禁止扣分”原则第3条,只要有一次识别正确则不扣分。因此本题得满分3分。

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

学生两次识别结果中,关于“最多结点数”的表述均为 \( \frac{k^{n}-1}{k - 1} \)。这里变量符号使用了“n”,而题目给定的高度符号是“h”。根据“禁止扣分”原则第1条和第4条,这很可能是将“h”误识别为“n”,属于字符误写,且核心逻辑(等比数列求和公式)正确,因此不扣分。关于“最少结点数”,两次识别结果均为 \( \frac{k^{n - 1}-1}{k - 1}+k \)。同样,将高度“h”误写为“n”,但表达式结构 \( \frac{k^{h-1}-1}{k-1} + k \) 与标准答案 \( 1 + (h-1)k \) 在形式上不一致。我们需要验证其正确性:
对于高度为h的正则k叉树,结点最少的情况是:除根节点外,第2到第h-1层每层只有一个分支节点(有k个孩子),其余k-1个为叶节点,第h层有k个叶节点。此时,第1层有1个节点,第2到第h-1层每层有k个节点(1个分支+k-1个叶),第h层有k个叶节点。总节点数为 \( 1 + (h-2)k + k = 1 + (h-1)k \)。而学生的表达式 \( \frac{k^{h-1}-1}{k-1} + k \) 计算的是前h-1层满k叉树的节点数加上第h层的k个节点,这实际上描述的是另一种“最少”情况:即前h-1层是满的,第h层只有k个节点。但这种情况并不是结点数最少的,因为前h-1层满树会导致分支节点数远多于“每层只留一个分支”的方案,从而总节点数 \( \frac{k^{h-1}-1}{k-1} + k \) 会大于 \( 1 + (h-1)k \) (当k>1, h>2时)。因此,学生给出的最少结点数公式是错误的,属于逻辑错误。推导过程缺失,且答案错误。
根据标准答案,最多结点数部分占3...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发