文章

92

粉丝

68

获赞

0

访问

11.4k

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


评分及理由

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

学生给出的基本设计思想是:“所有节点,左子树小于根节点,并且右子树大于根节点”。这个描述过于简化,没有体现出二叉搜索树的关键约束:整个左子树的所有节点都小于根节点,整个右子树的所有节点都大于根节点,而不仅仅是直接左右孩子。学生的描述容易误解为仅检查直接孩子节点,这不能保证整棵树是二叉搜索树。因此,该思想表述不完整且不准确。扣2分,得2分。

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

学生实现的算法存在以下问题:
1. 逻辑错误:算法仅检查每个节点的直接左孩子是否大于该节点、直接右孩子是否小于该节点。这违反了二叉搜索树的定义(需要递归地约束子树的所有节点)。例如,对于右子树中的左后代节点,它可能小于根节点但大于其父节点,该算法无法检测此类错误。
2. 返回值逻辑相反:算法中,当发现违反条件时设置 bRet = 1,最后返回 bRet。这意味着如果检测到违反情况返回1(true),否则返回0(false)。但题目要求是二叉搜索树返回 true,否则返回 false。因此返回值逻辑与题目要求相反。
3. 数组越界风险:循环中访问 T.sqBiTNode[2*i+1]T.sqBiTNode[2*i+2] 时,没有检查下标是否超出 ElemNum 范围,可能导致越界访问。
基于以上逻辑错误,该算法不能正确判断二叉搜索树。由于核心逻辑错误,扣7分。但考虑到学生理解了顺序存储中父子索引关系(2*i+1, 2*i+2)以及用-1表示空节点,给予基础分2分。得2分。

题目总分:2+2=4分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发