文章

7

粉丝

0

获赞

0

访问

3.4k

头像
2025 年 9 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年9月20日 18:01
阅读数 364


评分及理由

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

学生答案的基本设计思想是采用先序遍历,判断每个结点是否有左右子树,然后计算左右子树的最小距离(通过Mind函数)。但答案中未明确说明如何计算最小距离(例如,Mind函数的设计意图是递归计算最小差值,但实现有误)。思路与标准答案的暴力解类似,但描述不够清晰(例如,未说明如何遍历子树计算最小距离)。因此扣1分,得2分。

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

学生代码存在多处逻辑错误:
- Mind函数中使用了未定义的变量d和root(应为当前结点值),且递归终止条件错误(a为NULL时返回未初始化的d)。
- countNodes函数中,递归调用countNodes(root->left)和countNodes(root->right)时未累加count值,且缺少返回语句。
- LTreeIsEmpty和RTreeIsEmpty函数多余(可直接用root->left != NULL判断),且Mind函数未正确实现最小距离计算。
代码整体无法正确运行,但基本思路(先序遍历和计算最小距离)与暴力解部分匹配。根据错误严重程度,扣7分,得2分。

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

学生给出的时间复杂度为O(h),但根据其思路(先序遍历每个结点,并对每个有左右子树的结点递归计算Mind函数),实际应为O(n^2)(暴力解)或O(nh)(次优解)。O(h)明显错误,且未说明h的含义(树高)。因此扣2分,得0分。

题目总分:2+2+0=4分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发