文章

20

粉丝

0

获赞

0

访问

586

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

(1)

第一条边选:AD(代价为4);第二条边选DE(代价为4);第三条边选EC(代价为5);第4条边选BC(代价为4)结束。

(2)

并不唯一,因为起始顶点可以有A,B,C,D,E五种选择。

(3)

对于只有一个强连通分量的带权连通图,其MST是唯一的,每个顶点到其他顶点的路径只有一条。


评分及理由

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

学生给出的边依次为:(A,D)、(D,E)、(E,C)、(B,C),与标准答案完全一致,且顺序正确。因此得4分。

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

学生回答“并不唯一”,理由是“起始顶点可以有A,B,C,D,E五种选择”。但Prim算法中起始顶点的选择不会影响最终MST的结构(仅影响构建顺序),该图MST实际唯一。学生理解有误,故得0分。

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

学生回答“对于只有一个强连通分量的带权连通图,其MST是唯一的”不正确。强连通分量通常用于有向图,而MST针对无向图;且强连通性与MST唯一性无直接关系。学生未给出正确条件(任意环中边权均不相同),故得0分。

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

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发