文章

481

粉丝

5

获赞

19

访问

55.9k

头像
2025 年 7 月第 1 次 408 月考试卷 - 第41题回答
数据结构
发布于2025年10月22日 17:09
阅读数 67


评分及理由

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

得分:4分

理由:学生的设计思想正确,与标准答案一致。明确使用了深度优先搜索(前序遍历)遍历二叉树,维护临时路径数组,在遍历过程中检查路径和,并在回溯时移除当前节点。思路完整且符合题目要求。

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

得分:6分

理由:代码实现基本正确,但存在以下问题:
1. 函数参数中使用了未定义的`BTree`类型(应为`BiTree`),但根据上下文可判断为识别错误,不扣分。
2. 节点权值字段写为`T->Val`(应为`T->val`),但属于识别错误,不扣分。
3. 逻辑错误:在递归调用左右子树时,直接使用了修改后的`pathLen`值,这会导致回溯时路径长度减少后影响后续递归的路径记录。虽然代码最后有`pathLen--`回溯操作,但递归调用时传递的是值拷贝,实际不影响父调用,因此这里不构成错误。
4. 逻辑错误:缺少对节点权值可能为负情况的考虑。标准答案强调即使当前路径和大于k仍需继续遍历(因为后续负权值可能使和等于k),而学生代码在计算sum后没有明确说明这一点,但在代码实现上确实继续遍历了左右子树,因此实际逻辑正确,但思想描述不够完整。
5. 代码结构清晰,包含了路径记录、和计算、路径打印和递归遍历等关键步骤。

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

得分:1分

理由:学生正确给出了空间复杂度O(h),但时间复杂度只写了O(n),没有考虑路径和计算的时间开销。标准答案中时间复杂度为O(n×h),学生此处分析不够完整。

题目总分:4+6+1=11分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发