文章

179

粉丝

0

获赞

0

访问

9.0k

头像
2016年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年11月27日 21:38
阅读数 43


评分及理由

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

学生正确推导了叶结点数量的公式:设叶结点数为n,根据结点总数m+n等于边数km+1,得到n=(k-1)m+1。推导过程与标准答案一致,逻辑正确。得3分。

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

学生给出了最多结点数的正确公式:\(\frac{k^{h}-1}{k-1}\),这与标准答案一致。但最少结点数的公式\(\frac{k^{h-1}-1}{k-1}+k\)存在逻辑错误:该公式计算的是高度为h-1的满k叉树结点数加上第h层的k个结点,但这样构造的树在第2到h-1层中并非每层只有一个分支结点(实际每层有多个分支结点),不符合最少结点的情况。标准答案中最少结点数为1+(h-1)k,表示除根结点外每层恰好有k个结点(一个分支结点和k-1个叶结点)。因此最多结点部分正确(3分),最少结点部分错误(0分),本小题得3分。

题目总分:3+3=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发