文章

5

粉丝

0

获赞

0

访问

2.3k

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

1. 采用深度遍历。分别使用递归遍历到最底层的节点。若没有左子树或右子树则向上返回,并在返回途中记录节点的最下值。如果符合节点,则分别计算左子树与右子树的距离,若相等则res+=1。

 


评分及理由

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

学生答案中描述的设计思想是采用深度遍历(递归),在返回途中记录节点的最小值,并计算左右子树与当前节点的距离差,若相等则计数。这与标准答案中的最优解(后序遍历)思路基本一致,但描述不够清晰和完整(例如未明确说明如何记录子树的最小值和最大值,以及如何利用二叉搜索树性质)。考虑到核心思想正确(后序遍历并维护子树信息),但细节描述不足,扣1分。得分:2分。

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

学生提供的代码存在多处逻辑错误和语法问题:
1. 函数参数和返回值设计不合理:函数`f`的参数`minVal`未使用,且试图通过指针传递最小值但实际使用了整数常量(如9999)而非指针或引用。
2. 变量未定义:`res1`和`res2`未声明和初始化,导致返回值错误。
3. 递归调用未处理返回值:递归调用`f(root->left, *min1)`和`f(root->right, *min2)`的返回值未被捕获,导致计数丢失。
4. 最小值记录错误:试图用`min1`和`min2`记录子树最小值,但未实际计算和更新,而是直接赋值为常量9999。
5. 条件判断不完整:未处理当前节点左右子树是否存在的情况,且未维护子树的最小值和最大值。
这些错误导致代码无法正确统计符合条件的节点数,逻辑错误严重。但代码结构试图采用后序遍历(递归左右子树后再处理当前节点),与最优解方向一致,因此给予部分分数。扣分:由于核心逻辑错误(未正确维护子树信息、未处理返回值等),扣7分。得分:2分。

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

学生声明时间复杂度为O(n),这与最优解的时间复杂度一致,且后序遍历每个节点仅访问一次,因此正确。但鉴于代码实现有严重错误,理论上无法达到O(n)的效率(实际可能因错误而无法运行),但考虑到时间复杂度分析本身正确,不扣分。得分:2分。

题目总分:2+2+2=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发