文章

140

粉丝

0

获赞

1

访问

16.8k

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


评分及理由

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

学生回答:该方法不可行,并给出了一个反例。在反例中,学生构造了一个包含三个顶点的图,其中V₁到V₂的边权为1,V₂到V₃的边权为3,V₁到V₃的边权为2。按照题目描述的方法,从V₁出发,首先选择最近的顶点V₂(距离1),然后从V₂选择最近的顶点V₃(距离3),得到路径V₁→V₂→V₃,总长度为4。而实际最短路径是V₁→V₃,长度为2。这个反例正确说明了题目所给方法不一定能求得最短路径。

学生的回答与标准答案的核心逻辑一致,都指出了该方法不一定能求得最短路径,并通过反例进行了说明。虽然学生使用的图与标准答案略有不同,但反例的原理和效果是相同的,因此思路正确。

扣分情况:无扣分。学生回答正确,反例有效,逻辑清晰。

得分:10分

题目总分:10分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发