文章

986

粉丝

5

获赞

20

访问

251.6k

头像
2024年(408)计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年11月30日 17:42
阅读数 196


评分及理由

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

学生答案的基本设计思想正确:通过计算入度表,选择入度为0的顶点,更新邻接点入度,并检查每次是否只有一个入度为0的顶点。思路与标准答案一致,表述清晰。得4分。

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

学生代码存在以下逻辑错误:

  • 入度计算部分错误:在初始化入度表后,计算入度时使用了错误的逻辑。代码中degree[j] += G.Edge[i][j]会导致重复累加,且没有正确计算每个顶点的入度(应该是列累加,但这里行遍历方式不正确)。标准答案是通过列遍历每个顶点的入边来计算入度。
  • 初始入度为0的顶点查找逻辑错误:在计算入度过程中同时尝试查找入度为0的顶点,但此时入度表尚未完全计算正确,且ino的初始化和更新逻辑混乱(初始ino=1不合理,应为查找第一个入度为0的顶点)。
  • 拓扑排序主循环条件错误:while (ino >= 0)条件不完善,当ino=-2(表示有多个入度为0的顶点)时循环会终止,但此时可能尚未处理完所有顶点,且没有正确处理多个入度为0的情况。
  • 循环结束后没有处理可能存在的多个入度为0顶点的情况:在标准答案中,每次迭代都会检查入度为0的顶点数量,而学生代码中仅在更新邻接点时设置ino=-2,但没有在每次迭代开始时检查多个入度为0的情况。

由于存在多处逻辑错误,导致算法无法正确判断唯一拓扑序列。根据错误严重程度,扣5分。得4分。

题目总分:4+4=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发