文章

7

粉丝

0

获赞

0

访问

3.1k

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


评分及理由

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

得0分。学生的基本设计思想存在根本性错误。学生提出通过中序遍历得到序列后,检查序列中每个元素与其左右相邻元素的差值是否相等来统计满足条件的结点数。但这种方法错误地假设了中序序列中当前结点的前驱和后继分别就是左子树和右子树中与当前结点最小距离的结点。实际上,左子树中与当前结点最小距离的结点可能是左子树的最大值(即中序序列中当前结点的直接前驱),右子树中与当前结点最小距离的结点可能是右子树的最小值(即中序序列中当前结点的直接后继)。但题目要求的是左右子树分别与当前结点的最小距离相等,而学生的方法只检查了相邻三个结点的差值关系,并没有考虑左右子树的最小距离计算,且无法处理非直接前驱/后继的情况(例如,左子树的最小距离可能来自非直接前驱的结点)。因此,设计思想完全错误。

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

得0分。代码实现基于错误的设计思想,存在多个逻辑错误:
1. 中序遍历函数`midOrder`中,错误地将左右子结点的值压入队列(例如`List.push(root->left->val)`),这会导致序列中包含重复结点(子结点会被递归遍历并压入多次)且序列顺序错误。正确的中序遍历应只压入当前根结点的值。
2. 统计循环中,索引`i`从1开始,但循环内访问`List.at(i+1)`会导致越界(当`i`为最后一个元素时)。
3. 核心逻辑错误:条件`List.at(i) - List.at(i-1) == List.at(i+1) - List.at(i)`试图判断相邻三个结点的差值是否相等,这与题目要求的“左右子树最小距离相等”完全无关。例如,对于结点2(值为2),其中序序列前驱是1,后继是3,差值均为1,但题目要求的是左子树最小距离(|1-2|=1)和右子树最小距离(|3-2|=1)相等,这里巧合相等,但对于结点4(值为4),前驱是3,后继是6,差值分别为1和2,但题目左子树最小距离是1(|3-4|),右子树最小距离是2(|6-4|),这里也巧合相等?实际上,结点4并不满足条件(因为1≠2),但学生的代码会错误地统计。因此,代码无法正确解决问题。

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

得0分。学生声称时间复杂度为O(n),但基于错误的设计思想,即使代码正确,中序遍历和序列遍历的时间复杂度为O(n),但题目要求的最小距离计算并未正确实现。...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发