文章

148

粉丝

0

获赞

0

访问

16.8k

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


评分及理由

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

得分:3分

理由:学生的基本设计思想正确,包括计算入度、检查入度为0的顶点个数、删除顶点等关键步骤。但描述中存在两处不准确:①“将度为0的顶点所在邻接矩阵的行的值都修为0”实际上应该是对该顶点指向的所有邻接点的入度减1,而不是修改邻接矩阵本身(虽然修改邻接矩阵也能实现删除效果,但不符合拓扑排序常规做法,且会破坏原图数据);②“重复①②直至遍历完成则说明存在唯一的邻接矩阵”表述不严谨,应为“存在唯一的拓扑序列”。由于核心思路正确,扣1分。

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

得分:6分

理由:算法框架基本正确,但存在以下逻辑错误:
1. 每次while循环中,k(入度为0的顶点计数)没有重置为0,会导致后续循环中k累加错误,这是严重逻辑错误,扣2分。
2. 在删除顶点时,代码直接修改了邻接矩阵G.Edge[temp][i] = 0,这虽然能模拟“删除”效果,但会破坏原始图数据,且不符合拓扑排序中仅更新入度数组的常规做法,扣1分。
3. 代码中“G.Vertices”应为“G.numVertices”,但根据误写不扣分原则,不扣分。
4. 算法缺少对“不存在拓扑序列”(即有环)的完整判断:当没有入度为0的顶点时,应返回0,但学生代码中仅通过k!=1返回0,若k=0(没有入度为0顶点)也会返回0,这一点实际上覆盖了有环情况,但逻辑不够清晰。
整体代码结构正确,能实现基本功能,但因上述逻辑错误扣3分。

题目总分:3+6=9分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发