文章

117

粉丝

38

获赞

0

访问

22.8k

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


评分及理由

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

学生正确设定了结点总数n、叶结点数n₀和度为k的结点数nₖ,并建立了方程组:n = n₀ + nₖ 和 n = k·nₖ + 1。通过联立解得n₀ = (k-1)nₖ + 1,这与标准答案完全一致。推导过程清晰完整,因此得满分3分。

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

对于最多结点情况:学生正确识别出满正则k叉树的情况,给出了等比数列求和公式 k⁰ + k¹ + ... + kʰ⁻¹ = (1-kʰ)/(1-k),这与标准答案等价(标准答案为(kʰ-1)/(k-1)),只是分子符号不同但数学上等价,因此这部分正确。

对于最少结点情况:第一次识别结果说"第h层只有k个叶结点",第二次识别结果说"第h层只有1个叶结点",存在矛盾。从推导看,学生给出的公式是(1-kʰ⁻¹)/(1-k)+k,这与标准答案M₂ = 1+(h-1)×k不一致。学生的公式实际上计算的是前h-1层满k叉树结点数加上k,这不符合最少结点的构造逻辑,存在逻辑错误。

根据评分标准,最多结点部分正确(3分),最少结点部分错误(0分),因此本小题得3分。

题目总分:3+3=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发