文章

29

粉丝

0

获赞

0

访问

1.1k

头像
2009年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年9月27日 16:39
阅读数 43

不能求出最短路径,如图所示:我们就不能得到节点1到节点4的最短路径。因为如果按照题目的算法,得到的路径是1->2->4,就不是最短路径。


评分及理由

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

学生回答“不能求出最短路径”,并给出了一个图例进行说明。其图例描述为:节点①到②距离为2,②到④距离为3,①到③距离为3,③到④距离为1。学生指出,按照题目所述算法,从①到④的路径将是①→②→④(总距离5),而实际最短路径是①→③→④(总距离4),从而证明了该方法不一定能得到最短路径。

学生的结论(方法不一定能求得最短路径)与标准答案一致,并且所举例子的逻辑结构与标准答案中的例子(A-B-C路径长11,A-D-C路径长5)在本质上相同,都是通过构造一个局部贪心选择导致全局非最优的反例来证明论点。因此,学生的回答正确且有效。

尽管学生作答中的图是通过图片形式呈现,文字描述部分可能存在识别误差(例如节点编号方式与标准答案不同),但根据“禁止扣分”原则,只要核心逻辑正确,因识别导致的非关键细节差异不扣分。

综上,该部分回答内容正确,论证有效。

得分:10分

题目总分:10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发