文章

115

粉丝

0

获赞

0

访问

7.8k

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

 


评分及理由

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

得分:4分

理由:学生的基本设计思想与标准答案一致。通过模拟拓扑排序过程,在每一轮中寻找入度为0的顶点,并检查是否只有一个这样的顶点。如果每一轮都恰好只有一个入度为0的顶点,且最终所有顶点都被处理,则存在唯一拓扑序列。思路清晰、正确,因此给满分。

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

得分:7分

理由:学生的算法整体框架正确,实现了拓扑排序的核心逻辑,但在细节上存在两处逻辑错误:
1. 在模拟拓扑排序的外层循环中,当找到入度为0的顶点并标记后,立即使用`temp`作为索引去更新其邻接点的入度。然而,如果在一轮循环中根本没有找到入度为0的顶点(即`temp`仍为-1),那么后续的`for (int j = 0; j < G.numVertices; j++) { if (G.Edge[temp][j] != 0) ... }`会导致访问`G.Edge[-1][j]`,这是未定义行为。标准答案中对此情况进行了检查(`if(zeroInDegreeCount == 0) return 0;`),而学生代码缺少此检查。
2. 学生的代码在函数声明处存在不一致(第一次识别为`int uniquelyOrderedGraph G19`,第二次为`int uniquely(ALGraph G)`),但根据上下文和题目要求,应使用`MGraph`。考虑到识别可能产生的字符错误(如`ALGraph`可能是`MGraph`的误识别),且核心逻辑不受此类型名影响,因此不扣分。但第一点逻辑错误是明确的,扣2分。
其余部分,包括入度计算、每一轮检查入度为0的顶点个数、更新邻接点入度以及最终检查处理顶点数,均正确实现。

题目总分:4+7=11分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发