文章

69

粉丝

0

获赞

0

访问

2.6k

头像
2022年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年12月14日 19:46
阅读数 31


评分及理由

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

得分:2分

理由:学生答案的基本设计思想部分提到了二叉搜索树的定义(左子树所有结点小于根,右子树所有结点大于根),并提出了中序遍历的思路,用Val记录已遍历到的最大值,然后比较当前结点值与Val的关系。这一思路整体上是正确的,符合二叉搜索树中序遍历递增的性质。但是,描述中存在不严谨之处:①“其中每一个结点作为根结点时”这一表述在递归判断中通常是通过上下界约束实现的,而学生直接用了中序遍历记录前驱值的方法,前后表述略有脱节;②没有明确指出初始Val应设置为一个足够小的值(如LONG_MIN),也没有说明空结点或越界的处理。因此扣2分。

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

得分:5分

理由:学生给出的代码框架基本正确,采用了递归中序遍历,并尝试用val记录前驱值进行比较。但存在以下逻辑错误:
1. 函数judge的参数val是按值传递的,在递归左子树时修改的val不会传递到右子树,这会导致右子树比较时使用的val仍然是进入当前结点之前的值,从而可能错误地判断为不是二叉搜索树。这是严重的逻辑错误,扣3分。
2. 代码中结构体名称存在识别误差(如CSeBiTree、SeBiTree、SqBiNode等),但根据上下文可判断是SqBiTree和SqBiTNode的误写,根据规则不扣分。
3. 缺少对空树或越界的完整处理,但递归终止条件中包含了i < bt.ElemNum && bt.SqBiTNode[i] != -1,基本正确,不扣分。
4. 没有给出完整的函数接口(如主调函数isValidBST)和初始val的设置,但题目要求描述算法,可以接受只给出核心函数,因此不额外扣分。
综合以上,因主要逻辑错误(参数传递问题)扣3分,其他小问题不扣分,得5分。

题目总分:2+5=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发