文章
20
粉丝
0
获赞
0
访问
586
(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分
登录后发布评论
暂无评论,来抢沙发