文章

2

粉丝

0

获赞

0

访问

969

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


评分及理由

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

学生答案的基本设计思想:通过定义两个辅助函数FindLeft和FindRight分别寻找左子树的最右结点(最大值)和右子树的最左结点(最小值),然后计算当前结点与这两个值的差值,若相等则计数。该思路利用了二叉搜索树的性质,避免了遍历整个子树,与标准答案中的次优解思路一致。因此,设计思想正确,得3分。

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

学生提供的代码存在以下问题:
1. FindLeft函数中,外层while循环条件为root != NULL,但内层while循环后直接返回,导致逻辑错误(实际上只处理了非空情况,但内层循环可能访问空指针)。正确做法应直接处理左子树的最右结点,无需外层循环。
2. FindRight函数正确。
3. countNodes函数中,未处理root为空的情况,直接访问root->left和root->right可能导致段错误。
4. 使用全局变量cnt,但未初始化(可能被多次调用时累积错误),且函数递归调用时未使用返回值(递归调用countNodes时未更新cnt,导致计数错误)。
5. 条件判断中,左差值计算未使用绝对值(但题目要求距离为绝对值,但二叉搜索树中左子树最大值一定小于当前值,故root->val - valLeft为正,可不加绝对值;右差值同理为正值,因此实际不影响结果,但不符合题目距离定义)。
6. 递归调用左右子树时,未检查当前结点是否为空,可能递归到空指针。
综上,代码逻辑存在多处错误,但核心思路正确(利用二叉搜索树性质找最值)。根据标准答案次优解(6分)的评分标准,扣除逻辑错误分后,得4分(思路正确但实现有缺陷)。

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

学生给出的时间复杂度为O(n log₂n),但根据次优解的设计,每个结点需要O(h)时间(h为树高)查找最值,总时间复杂度应为O(nh),最坏情况下h=n(退化为链表),为O(n²);平均情况下h=log n,为O(n log n)。学生答案写为O(n log₂n)基本正确(与平均情况一致),但未说明最坏情况。空间复杂度为递归栈深度O(h),学生写为O(log₂n)(平均情况正确),但未考虑最坏情况。因此,时间复杂度分析部分正确,得1分。

题目总分:3+4+1=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发