文章

7

粉丝

0

获赞

0

访问

334

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


评分及理由

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

学生答案的基本设计思想是:对于每个结点,如果同时存在左子树和右子树,则分别寻找左子树的最大值和右子树的最小值,然后计算当前结点与这两个值的差的绝对值(即最小距离),如果相等则计数。最后递归处理左右子树。该思路利用了二叉搜索树的性质(左子树的最大值和右子树的最小值分别对应最小距离),与标准答案中的“次优解”思想一致。因此得3分。

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

学生代码实现了上述思想,但存在以下逻辑错误:
1. 在递归函数中,如果当前结点的左子树或右子树不存在(即不满足条件),直接返回0,但这里应该继续递归左右子树(因为当前结点不满足条件,但左右子树可能还有满足条件的结点)。代码中直接返回0会导致漏掉子树中的结点,这是严重逻辑错误。
2. 函数`abs`的参数错误:`abs`函数应接受一个参数(计算绝对值),但代码中使用了两个参数(如`abs(min_k, cur)`),这会导致编译错误或逻辑错误(实际可能是想计算`abs(min_k - cur)`)。
3. 递归基处理不完整:`findMin`和`findMax`函数中,如果传入空指针(如`root`为NULL)会导致访问空指针错误,但题目中结点值都为正数,且递归条件已确保子树存在,但代码中未处理空指针情况(如`root->left`或`root->right`可能为NULL)。
基于以上错误,扣分如下:
- 逻辑错误1(漏递归子树):扣3分(严重错误)。
- 逻辑错误2(abs使用错误):扣2分(函数使用错误)。
- 逻辑错误3(空指针风险):扣1分(代码健壮性不足)。
剩余得分:9 - 3 - 2 - 1 = 3分。
注:学生代码整体框架正确(使用了递归和二叉搜索树性质),但实现细节有误。

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

学生给出的时间复杂度是O(N),并说明N为树高。但正确时间复杂度应为O(nh)(h为树高),因为每个结点需要递归查找左子树最大值和右子树最小值(每次查找耗时O(h)),总共有n个结点。学生错误地将时间复杂度表述为O(N)(N为树高),但实际应为O(nh)。因此扣1分(时间复杂度分析错误)。得1分。

题目总分:3+3+1=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发