文章

7

粉丝

0

获赞

0

访问

3.0k

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


评分及理由

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

学生作答中未画出带权有向图,仅提供了部分边的描述(如A→B、A→C等),但未完整给出所有边及权重,且描述中存在错误(如B指向F应为B指向D和E,D指向F正确但缺少其他边)。根据标准答案,需完整画出图并标注权重,学生未完成此部分,因此得0分。

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

学生回答强连通分量数量为2(标准答案为4),错误;添加边方案为添加C→D(标准答案为添加G→D等),但添加C→D不能使强连通分量数量变为1(仅连接分量{C,E}和{A,B,D},但F和G仍孤立),因此添加方案错误;删除边数量为3(标准答案为2),删除方案为删除C→E(标准答案为删除D→A和E→C),但删除C→E仅能破坏{C,E}的强连通性,未能消除所有大小大于1的强连通分量(如{A,B,D}仍存在)。因此,强连通分量数量判断错误扣1分,添加方案错误扣1分,删除方案部分正确(删除C→E可消除一个强连通分量,但未完全解决问题)扣0.5分,最终得0.5分(保留半分因删除C→E有一定合理性,但整体不完整)。

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

学生描述了拓扑排序过程(找度为0的点并输出,删除边等),但未说明关键路径存在的条件(如检测环、唯一源点和汇点等),仅提到“存在关键路径”的判断方式不完整;优势部分提到“十字链表表示唯一确定一个图”不准确,但“找相邻边、删除顶点方便”部分涉及逆边访问优势(标准答案强调逆邻接访问便利)。思路部分得1分(拓扑排序过程正确但未关联关键路径判断),优势部分得0.5分(部分正确),共得1.5分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发