2009年计算机学科专业基础综合试题 - 第41题回答
上述方法不可行，如以下例子
顶点1到顶点2距离为2顶点1到顶点3距离为1，顶点3到顶点4距离为2，顶点4到顶点5距离为1，顶点2到顶点5距离为1
初始顶点为1目标顶点为5
根据上面算法会分别选择1-3，3-4，4-5距离共为4
而1到5的最佳路径是1-2，2-5距离共为3所以该方法不可行
评分及理由
（1）得分及理由（满分10分）
学生正确指出该方法不可行，并给出了一个具体的反例。反例中顶点关系清晰：顶点1到2距离2，1到3距离1，3到4距离2，4到5距离1，2到5距离1。算法会选择路径1→3→4→5（总距离4），但实际最短路径为1→2→5（总距离3），有效证明了该方法错误。理由充分，逻辑正确，与标准答案本质一致（标准答案使用A-B-C和A-D-C的反例，学生反例不同但同样有效）。因此得满分10分。
题目总分：10分
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后发布评论
暂无评论，来抢沙发