文章

438

粉丝

0

获赞

0

访问

76.3k

头像
2017年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年11月8日 22:47
阅读数 163


评分及理由

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

学生给出的边序列为:(A,D), (D,E), (E,C), (C,B)。这与标准答案(A,D), (D,E), (C,E), (B,C)在边的选择上完全一致,只是最后两条边的表示顺序和顶点顺序有所不同。在最小生成树中,边的顶点顺序不影响边的本质,且(E,C)与(C,E)是同一条无向边,(C,B)与(B,C)也是同一条无向边。因此,学生选择的边是正确的,并且顺序也符合Prim算法的执行过程。得4分。

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

学生回答“不是”,即认为图G的MST不是唯一的。但根据标准答案,图G的MST是唯一的。学生的回答与事实不符,存在逻辑错误。扣2分,得0分。

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

学生回答“不存在权值相等的边”。这个条件比标准答案“当带权连通图的任意一个环中所包含的边的权值均不相同时”更为严格。虽然“不存在权值相等的边”确实能保证MST唯一,但它并不是MST唯一的必要条件(例如,即使存在权值相等的边,但只要这些边不在同一个环中,或者在一个环中但权值相等的边不会导致多个MST,那么MST仍然可能是唯一的)。学生的回答给出了一个充分但不必要的条件,其表述不够准确,未能完全捕捉到MST唯一的本质条件。因此扣1分,得1分。

题目总分:4+0+1=5分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发