文章
323
粉丝
6
获赞
5
访问
175.0k

评分及理由
(1)得分及理由(满分4分)
得分:4分
理由:学生的算法思想与标准答案基本一致,都是通过计算入度、使用栈(或队列)存储入度为0的顶点,并在每一轮判断是否存在多个入度为0的顶点来判断拓扑序列是否唯一。思路清晰完整,没有逻辑错误,因此得满分。
(2)得分及理由(满分9分)
得分:7分
理由:学生的代码整体框架正确,实现了拓扑排序的基本流程,但在细节处理上存在两处逻辑错误:
1. 在while循环中,判断条件为if(top),这表示当栈中元素个数大于0(即非空)时就返回0,这显然是错误的。正确的逻辑应该是判断栈中是否同时存在多个入度为0的顶点,即if(top > 0)或if(top >= 1)(因为top是栈顶索引,top>0表示栈中至少有两个元素)。此处错误导致算法无法正确判断唯一性,属于关键逻辑错误,扣2分。
2. 代码中定义了变量cnt用于记录拓扑结点数量,但在后续处理中并未对cnt进行递增操作,导致最后无法通过cnt == G.numVertices判断拓扑序列是否包含所有顶点。不过,在第二次识别的代码中,最后直接返回1,这隐含了拓扑排序成功完成即包含所有顶点的假设,但实际代码中缺少对图中是否存在环的检查(即拓扑排序是否真正完成)。由于第一处错误已扣分,此处不再重复扣分。
此外,代码中使用了变长数组int in[G.numVertices],这在C99标准中合法,但部分编译器可能不支持,考虑到题目未明确要求语言标准,且不影响核心逻辑,不扣分。
综上,扣除2分,得7分。
题目总分:4+7=11分
题目总分:4+7=11分
登录后发布评论
暂无评论,来抢沙发