2022年（408）计算机学科专业基础综合试题 - 第41题回答
（1）二叉搜索树是一种二叉排序树，其大小关系是：根的左孩子的值<根节点<根的右孩子的值。对树进行中序遍历，每遍历一个结点就条件判断结点与其左右孩子是否符合二叉排序树的性质。因为树存在数组中，所以数组下标a的左孩子是数组下标（a+1）*2-1，右孩子是数组下标（a+1）*2 。
(2)
int Func(SqBiTree T,int ElemNum)
int rc,lc;
{
if(T[0]==-1)//数为空树时则失败
{
return flase;
}
for(int i=0;i<ElemNum/2;i++)
{
if(T1.SqBiTNode[i]>T1.SqBiTNode[（i+1）*2]&&T1.SqBiTNode[（i+1）*2]!=-1)
{return false;}
elseif(T1.SqBiTNode[i]<T1.SqBiTNode[（i+1）*2-1]&&T1.SqBiTNode[（i+1）*2-1]!=-1)
{
return false;
}
}
return true;
}
评分及理由
（1）得分及理由（满分4分）
得分：1分
理由：学生基本理解了二叉搜索树的定义（左子树结点值小于根结点，右子树结点值大于根结点），并提出了通过检查每个结点与其直接左右孩子的关系来判断。但是设计思想存在严重缺陷：
- 二叉搜索树要求整个左子树的所有结点都小于根结点，而不仅仅是直接左孩子；同样，整个右子树的所有结点都大于根结点。学生的方案只能检查直接父子关系，无法保证子树整体满足条件。
- 中序遍历的思路被提及，但并未在算法设计中正确实现。
- 数组下标的计算方式描述不准确（实际应为左孩子2*i+1，右孩子2*i+2）。
（2）得分及理由（满分9分）
得分：2分
理由：代码实现存在多处严重错误：
- 函数定义语法错误（参数位置混乱，函数名与参数名混淆）。
- 逻辑错误：仅检查结点与其直接左右孩子的大小关系，无法保证整棵树的二叉搜索树性质（如T2中50>40但位于左子树，此算法无法检测）。
- 数组下标计算错误：左右孩子下标应为2*i+1和2*i+2，而不是(i+1)*2...
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发