文章

52

粉丝

0

获赞

0

访问

1.6k

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


评分及理由

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

学生正确推导了叶结点数量的公式。通过边数关系建立方程:总边数 e = n - 1 = m + x - 1(其中x为叶结点数),同时所有边由m个度为k的结点发出,故e = m×k。联立得m + x = m×k + 1,解得x = (k-1)m + 1。推导过程完整,与标准答案一致。得3分。

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

最多结点情况:学生正确给出满k叉树结点数公式∑_{n=0}^{h-1} k^n = (k^h-1)/(k-1),得3分。

最少结点情况:学生思路正确(在高度h-1的满树基础上增加一个非叶结点),但最终表达式化简错误。正确结果应为1+(h-1)×k,而学生得到的是(k^{h-1}-1)/(k-1)+k。虽然思路正确,但计算错误导致结果不正确。根据评分标准,推导过程不完全正确需酌情扣分,扣2分。得3分。

题目总分:3+3=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发