文章

156

粉丝

195

获赞

0

访问

27.2k

头像
2025 年 7 月第 1 次 408 月考试卷 - 第42题回答
数据结构
发布于2025年11月22日 17:04
阅读数 92

1)

总比较次数 = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 3 = 21
ASL = 21 / 8 = 2.625

2)

查找路径:15→20→18
比较次数:3

3)

        15
       /  \
      8    18
     / \     \
    5  12    25
       /
      10

删除过程:用直接前驱 18 替换 20,然后删除原 18 节点(叶子节点)。


评分及理由

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

学生通过图形展示了BST结构,但图形中节点排列存在部分错误(如18和25的位置关系不符合BST规则),不过从文字描述和ASL计算来看,学生正确理解了BST的构造逻辑和ASL计算方法。ASL计算结果(2.625)与标准答案一致,且计算过程完整。图形错误可能为识别问题或绘制偏差,但核心逻辑正确。扣1分。

得分:3分

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

学生正确给出了查找路径(15→20→18)和比较次数(3次),与标准答案完全一致。无逻辑错误。

得分:3分

(3)得分及理由(满分3分)

学生给出的删除后BST结构正确(用18替换20后调整子树),但删除过程描述存在逻辑错误:标准方法应使用中序后继(25)而非直接前驱(18)进行替换。学生错误地使用直接前驱替换,导致子树连接关系混乱(如18的右子树应连接25,但图中未体现)。扣2分。

得分:1分

题目总分:3+3+1=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发