文章

7

粉丝

0

获赞

0

访问

525

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


评分及理由

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

学生未画出带权有向图,也未描述边的具体信息(如边及权重),仅提及"ABCD",不符合题目要求。根据标准答案,需正确画出图并标注边和权重。得0分。

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

学生提到"4个强连通分量",与标准答案一致(分量{A,B,D}、{C,E}、{F}、{G}),得1分;添加边部分,学生提出"添从G(6)→A(0)",但标准答案要求添加边使强连通分量数量变为1(即整个图强连通),添加G→A仅连接G到A,未解决所有分量的连通问题(例如C和E仍独立),且至少需添加多条边(标准答案示例为G→D),逻辑错误,扣1分;删除边部分,学生提出"删D(3)→A(0)",但标准答案要求删除边使顶点数量大于1的强连通分量数量变为0(即所有强连通分量均为单顶点),删除D→A仅破坏分量{A,B,D},但分量{C,E}仍存在(需删除C↔E中至少一条边),逻辑错误,扣1分。本部分得1分(仅强连通分量数量正确)。

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

学生回答"不存在,因为有环"部分正确(关键路径要求无环),但未完整说明拓扑排序判断关键路径的思路(如检查DAG、唯一源点汇点等),得1分;优势部分提到"对于稀疏图,可节省存图的空间",但标准答案强调十字链表在求关键路径时直接访问入边的优势(无需构建逆邻接表),学生回答未涉及此核心点,逻辑错误,扣1分。本部分得1分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发