文章

295

粉丝

0

获赞

1

访问

81.9k

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


评分及理由

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

学生给出了基本设计思想:使用深度优先遍历,对每个结点检查其值是否在给定的最小值和最大值范围内,并在递归左子树时更新最大值,递归右子树时更新最小值。该思想与标准答案方法一(递归验证上下界)一致,思路正确且表述清晰。因此得4分。

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

学生给出了C语言代码实现,整体框架与标准答案方法一类似,但存在以下问题:

  1. 代码中使用了全局变量 int flag = 1; 的声明,但在函数 solve 中又定义了局部变量 bool flag = true;,两者冲突且全局变量未使用,属于冗余但未影响核心逻辑,不扣分。
  2. 函数 dfs 的参数 int &flag 在C语言中不支持引用(应为C++语法),但在C语言中应使用指针传递。考虑到可能是识别或书写习惯问题,且核心递归逻辑正确,此处视为笔误不扣分。
  3. 递归边界条件中,仅检查了子结点索引是否小于 ElemNum,但未检查索引是否越界(即可能超过数组最大长度),不过题目中数组长度足够,且标准答案也未做此检查,因此不扣分。
  4. 初始值设置:Min = -1 可能不合适,因为结点值均为正整数,但-1作为空结点标记,若树中结点值可能为0时会产生误判。但题目明确结点值均为正整数,且标准答案使用 LONG_MIN,此处使用-1在正整数范围内可以接受,不扣分。
  5. 代码逻辑基本正确,能正确实现二叉搜索树的判定,时间复杂度O(n),空间复杂度O(n)。

因此,扣除1分(因参数传递语法在C语言中不严谨,但考虑到可能是识别问题,从宽处理),得8分。

题目总分:4+8=12分

题目总分:4+8=12分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发