文章

15

粉丝

0

获赞

1

访问

2.7k

头像
2025 年 9 月第 1 次 408 月考试卷 - 第42题回答
数据结构
发布于2025年9月20日 17:00
阅读数 60

2. 5个,2条,GE、CA之间添加,1条,将BD删除

3.采用辅助队列记录所有入度为0的点,将队列元素出度,再遍历将入度为0的点入队,直到队空即可。采用十字链表可以更加方便的找到对应的出度元素和权值,进而求出关键路径


评分及理由

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

学生未提供带权有向图的图示,也未描述边的具体信息(如起点、终点和权重),因此无法得分。标准答案要求画出图并标注边和权重,学生完全未作答此部分。

得分:0分

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

学生回答强连通分量数量为5个(标准答案为4个),错误;添加边方案为添加GE和CA(标准答案为添加一条边如G→D),错误;删除边方案为删除BD(标准答案为删除两条边如D→A和E→C),错误。所有部分均不符合标准答案,但学生尝试回答了数量和方法,给予部分思路分。

得分:1分(理由:强连通分量数量错误,添加和删除边方案错误,但回答了问题结构)

(3)得分及理由(满分3分)

学生描述了拓扑排序的过程(使用队列处理入度为0的点),但未说明判断关键路径存在的关键条件(如检测环、验证AOE网特性);在优势部分,学生提到十字链表便于找到出度元素和权值(部分正确,但未强调入边访问的优势),标准答案明确说明优势是直接访问入边用于逆拓扑排序。

得分:1分(理由:拓扑排序过程描述正确但关键路径判断条件缺失,优势部分部分正确但未准确对比邻接表)

题目总分:0+1+1=2分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发