文章

7

粉丝

0

获赞

0

访问

3.7k

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


评分及理由

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

学生答案中提到了中序遍历,并指出对于有左右子树的结点,需要找到前驱(左子树最右结点)和后继(右子树最左结点),然后比较距离。这利用了二叉搜索树的性质,与标准答案中的“次优解”思路一致。但学生提到“后继为中序遍历第一个叶结点”是错误的,应该是右子树的最左结点(即右子树的最小结点),且中序遍历顺序并非直接用于找前驱和后继,而是通过指针遍历。由于核心思路正确但存在部分描述错误,扣1分。得2分。

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

学生提供的代码框架不完整,且存在多处逻辑错误:
1. 变量pre和post的定义不清晰,且初始值设置不合理(应为结点指针而非INT_MIN/INT_MAX)。
2. 中序遍历过程中,pre和post的更新方式错误(pre应为左子树最右结点的值,post应为右子树最左结点的值),但代码中未实现查找逻辑。
3. 条件判断中使用了未更新的pre和post,无法正确计算距离。
4. 递归调用位置混乱,countNode递归调用与条件判断交织,逻辑不清晰。
5. 代码缺少关键步骤(如查找左子树最右结点和右子树最左结点),无法实现功能。
由于代码框架错误较多,无法正确统计满足条件的结点数,但学生试图利用中序遍历和前驱后继的思想,与“次优解”部分吻合,给予部分分数。扣7分,得2分。

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

学生未说明算法时间复杂度,因此不得分。得0分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发