文章

218

粉丝

6

获赞

4

访问

52.9k

头像
2017年计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年10月27日 18:48
阅读数 13


评分及理由

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

学生给出的边依次为:(A,D)、(D,E)、(E,C)、(C,B)。与标准答案(A,D)、(D,E)、(C,E)、(B,C)相比,虽然边的选择完全相同,但第3条边的顺序和表述略有不同。标准答案中第3条边是(C,E),学生写的是(E,C),但无向图中边的表示顺序不影响实质,且边的选择完全正确。因此,按顺序正确性扣1分,得3分。

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

学生回答“唯一”,与标准答案一致,得2分。

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

学生回答:“对于一个图的极大连通子图,去掉任意一边,均无法从其余边中找到权值相同或更短的边,则 MST 是唯一的。” 这个描述虽然不够精确(“极大连通子图”应为“图”本身,“去掉任意一边”等表述不严谨),但核心思想是当不存在权值相同的边可替换时MST唯一,与标准答案“当带权连通图的任意一个环中所包含的边的权值均不相同时,其MST是唯一的”本质一致。因此不扣分,得2分。

题目总分:3+2+2=7分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发