文章

8

粉丝

0

获赞

1

访问

597

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

(2)强连通分量数为4,至少添加3条边:G->F,F->D,F->E。

至少删除两条边:A->D,E->C。

(3)

  1. 判断关键路径存在的思路:通过拓扑排序检测图中是否存在环。若能完成拓扑排序(无环),则关键路径可能存在(还需源点汇点唯一);否则(有环),关键路径不存在。

  2. 十字链表法的最直接优势:支持对顶点的入边和出边的高效访问,在计算最早/最迟发生时间时,无需额外搜索即可分别遍历出边和入边,提升关键路径算法的整体效率。


评分及理由

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

学生未画出带权有向图,仅通过文字描述了边的信息,但描述中存在错误(如"A到B反向权重为3"应为"D到A权重为3"),且未完整呈现图的结构。根据标准答案,需画出完整的图并正确标注所有边和权重。学生作答不符合要求,得0分。

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

学生正确指出强连通分量数量为4(与标准答案一致),得1分。但添加边的方案错误(标准答案为添加1条边,学生提出添加3条边),且删除边的方案部分正确(删除E→C正确,但删除A→D错误,应为删除D→A)。因此添加边部分得0分,删除边部分得0.5分(因删除E→C正确)。本小题总得分1.5分。

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

学生正确说明了通过拓扑排序检测环的思路(1分),并指出十字链表法支持高效访问入边和出边的优势(1分),但未提及AOE网需验证源点、汇点唯一性等条件(扣0.5分)。因此本小题得分2分。

题目总分:0+1.5+2=3.5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发