文章

194

粉丝

0

获赞

0

访问

28.0k

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


评分及理由

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

学生给出的基本设计思想是:“使用数组 degree 保存结点入度,若每次仅有一个未被访问且入度为 0 的结点存在,则存在唯一拓扑序列。” 这一描述与标准答案的核心思想一致,即通过计算入度、每次选择唯一入度为0的顶点进行拓扑排序,若过程中出现多个入度为0的顶点则说明拓扑序列不唯一。因此,该部分思路正确,得满分4分。

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

学生的代码实现存在多处逻辑错误和不完整之处:

  1. 代码中使用了变量 only 但未使用,不影响逻辑,不扣分。
  2. 入度数组 degree 的初始化正确,入度统计部分正确。
  3. 后续的循环逻辑混乱:
    - 使用双重循环统计当前入度为0的顶点数(Count),但循环变量使用不当(外层j内层i),且未在每次移除顶点后重新统计,而是试图一次性统计所有顶点的入度为0的情况,这不符合拓扑排序的迭代过程。
    - 代码中出现 if(count == 1) if(count!= 1) break;(第一次识别)或 if(Count!= 1) break;(第二次识别),逻辑矛盾且 break 不在循环内,语法错误。
    - 最后的 for(i = 0; i < G.numVertices; i++) degree[i] = 0; 错误地重置了所有入度,完全破坏了算法逻辑。
  4. 代码未完成拓扑排序的迭代过程,没有实现顶点的“移除”(即将入度设为-1并更新后继顶点入度),也没有正确的循环结构来逐个处理顶点。

因此,该代码实现存在严重的逻辑错误,无法正确判断拓扑序列的唯一性。根据评分标准,应扣除大部分分数。考虑到学生正确实现了入度统计部分,但后续核心逻辑错误,给予2分(满分9分)。

题目总分:4+2=6分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发