2017年计算机学科专业基础综合试题 - 第42题回答
(1) 与A点相连的边有AB，AD与AE，我们选择权值最小的边AD；紧接着与D点相连的边有DE，CD，我们选择权值最小的边DE；与E点相连且不产生回路的边只有CE；与C点相连且权值最小的边是BC。五个顶点已经全部包含，综上所属，MST的边为AD,DE,CE,CB。权值为4+4+5+4=17。
(2)根据(1)的算法可知，每次选择的候选边权值都是最小的且唯一，所以图G的MST是唯一的。
(3)当带权连通图的任一环中所含的边的权值均不同时该图最小生成树唯一，因为此时每一轮的选择都唯一。
评分及理由
（1）得分及理由（满分4分）
学生给出的边依次为：(A,D)、(D,E)、(C,E)、(B,C)，与标准答案完全一致，且顺序正确。描述过程中虽然提到了AB、AE等边，但正确选择了最小权值边，没有影响结果。因此得4分。
（2）得分及理由（满分2分）
学生正确判断图G的MST是唯一的，理由描述合理（每次选择的候选边权值最小且唯一）。因此得2分。
（3）得分及理由（满分2分）
学生给出的条件与标准答案一致：“当带权连通图的任一环中所含的边的权值均不同时，该图最小生成树唯一”，理由描述正确。因此得2分。
题目总分：4+2+2=8分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发