文章

7

粉丝

0

获赞

0

访问

432

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


评分及理由

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

学生答案的基本设计思想:先判断有无左右子树,然后对左子树找最大值(通过最右结点),对右子树找最小值(通过最左结点),然后计算当前结点值与左子树最大值差的绝对值(即左子树最小距离)和当前结点值与右子树最小值差的绝对值(即右子树最小距离),并比较是否相等。该思路利用了二叉搜索树的性质,避免了遍历整个子树,与标准答案中的“次优解”思路一致。因此,得3分。

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

学生代码实现了基本设计思想,但存在以下问题:
1. 函数命名不一致(如getLeftMax和getLeftMax混用,但识别可能误写,不扣分)。
2. getChazhi函数逻辑错误:该函数本应分别计算左差和右差,但学生代码中试图用一个函数同时计算两个差,且参数传递和计算方式错误(例如,函数参数为leftmax和rightmin,但实际应分别传入leftmax和当前结点值、当前结点值和rightmin)。具体代码中,getChazhi(leftmax, root->data)和getChazhi(root->data, rightmin)的调用意图正确,但函数内部实现错误(使用了(leftmax - rightmin)等,这明显是逻辑错误)。
3. 递归统计count的方式错误:学生代码在CountNodes函数中定义了局部变量count,并递归调用左右子树,但递归结果未累加(递归调用CountNodes(root->left)和CountNodes(root->right)的返回值被忽略),导致最终返回的count只包含当前结点的判断结果,而不会累加子树中的满足条件结点数。
4. 全局变量count和局部变量count混用,但学生代码中似乎有全局count(int count=0;)和局部count(int count=0;),这会导致实际统计错误。
由于存在明显的逻辑错误(特别是getChazhi函数实现错误和递归统计错误),扣分较多。但核心思路正确(利用最右和最左结点),且部分代码正确(如getLeftMax和getRightMin函数)。根据标准答案“次优解”代码(6分)为参考,但学生代码有严重逻辑错误,因此扣3分(得6分)。

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

学生给出的时间复杂度为O(n + h),但实际应为O(nh)(因为对每...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发