文章

74

粉丝

0

获赞

0

访问

8.6k

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

(1)算法思想:根据二叉搜索树的定义,只需要确认节点的右孩子比自己小,左孩子比自己大。在进行遍历的时候需要设置一个上下界防止出现右子树的节点比根节点大还要大。

(2)代码:

//辅助递归函数
bool isSearchTree(sqBiTree T,int idx,int sup,int inf){
    //当前节点不存在时,下标越界值为-1
    if(idx >= T.Elemnum || T.SqBiTNode[idx] == -1){
        return true;
    }
    int val = T,SqBiTNode[idx];//当前节点的值
    if(val < inf || val > sup){
        return false;
    }
    //递归检查左子树(下表idx*2+1):更新上界为val-1
    //递归检查右子树(下标idx*2+2):更新下界为val+1
    return isSearchTree(T,2*idx+1,inf,val - 1) && isSearchTree(T,2*idx+2,val+1,sup);
}
//主函数
bool isBST(SqBiTree T){
    if(T.ElemNum==0){
        return true;
    }
    return isSearchTree(T,0,INT_MIN,INT_MAX);
}

 


评分及理由

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

学生给出的算法思想基本正确:

  • 正确指出了二叉搜索树的性质(左子树所有节点值小于根节点,右子树所有节点值大于根节点)
  • 提到了需要设置上下界来约束子树节点的取值范围
  • 基本思想与标准答案中的递归方法一致

扣分点:

  • 描述中"右孩子比自己小,左孩子比自己大"表述不够准确,应该是"左子树所有节点值小于等于当前节点,右子树所有节点值大于等于当前节点"
  • 对上下界的作用描述不够清晰

得分:3分(基本思想正确但表述不够精确)

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

学生代码存在以下问题:

  1. 语法错误:第6行"T,SqBiTNode[idx]"应为"...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发