文章

146

粉丝

0

获赞

1

访问

26.1k

头像
2024年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月12日 10:54
阅读数 70


评分及理由

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

学生答案的基本设计思想是:使用访问数组记录顶点是否被消除,通过遍历邻接矩阵寻找入度为0且未被访问的节点,消除该节点并更新其邻接节点的入度。若在某次循环中找到多个入度为0的节点,则拓扑序列不唯一;若无法找到入度为0的节点,则存在环。该思路与标准答案一致,正确实现了拓扑排序唯一性判断的核心逻辑。因此得4分。

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

学生代码存在以下逻辑错误:
1. 变量定义重复(如`n`和`numvertices`)且未初始化,`n`应为`G.numVertices`,但代码中未正确使用图结构参数。
2. 内存分配`malloc`使用未定义的`n`,且未释放内存,可能造成运行时错误。
3. 内层循环中`k`的循环范围错误,`if(G.Edge[k][j] == 1)`应检查节点`j`的入度,但循环变量`k`用于行索引,逻辑混乱。
4. 记录入度为0的节点索引`k`在循环结束后未保存,且`count`和`s`的更新位置错误,导致无法正确标记和消除节点。
5. 缺少对节点消除后更新邻接节点入度的操作(标准答案中需遍历出边减少邻接节点入度)。
这些错误导致算法无法正确执行拓扑排序,核心逻辑存在严重缺陷。但学生思路正确,部分注释表明理解问题本质。根据错误严重程度,扣5分。得4分。

题目总分:4+4=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发