文章

70

粉丝

1

获赞

0

访问

11.0k

头像
2025 年 7 月第 1 次 408 月考试卷 - 第42题回答
数据结构
发布于2025年9月20日 17:21
阅读数 88

(1)

最终构造BST如下:

            15 

   8                   20

5       12      18        25

      10    

ASL=21/8

(2)

查找路径15->20->18,关键字比较次数为3

(3)

删除过程使用20的后继25写入20所在节点位置,最后删除25原先所在节点即可。

删除后的BST结构如下:

            15 

   8                   25

5       12      18        

      10    


评分及理由

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

学生正确绘制了BST结构,节点位置与标准答案一致,包括深度关系(如10在深度4)。ASL计算过程正确,给出21/8(即2.625),与标准答案一致。但图形未明确标注深度(如用文字说明深度),但结构正确,扣0.5分。最终得3.5分。

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

学生正确给出查找路径15→20→18,比较次数为3次,与标准答案完全一致。得3分。

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

学生正确说明删除过程(用后继25替换20),删除后BST结构正确(25替换原20位置,18作为25的左孩子)。但未明确说明中序后继节点的选择逻辑(25是20右子树的最小节点)和删除细节...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发