文章

33

粉丝

253

获赞

1

访问

15.6k

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

不能求得最短路径   假设一个图 有ABCD四个顶点   四条边分别是 2 10 4  6 且这个图构成了一个环根据上述方法 假设求  A到 D最短路径 距离A最近的是B 距离是2  B到D的距离是10    那么求得的最短距离是12 实际最短距离是10


评分及理由

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

学生回答"不能求得最短路径"是正确的,与标准答案一致。学生举出了一个反例:图中有ABCD四个顶点,边权分别为AB=2,BD=10,AD=10(虽然学生描述不够清晰,但可以理解为AD=10),按照题目方法从A到D会选择A→B→D=12,而实际最短路径是A→D=10。这个反例虽然不够标准(学生描述中缺少了关键的中间顶点C,且边权描述不够明确),但基本思路正确,能够说明问题。

扣分点:学生举例不够严谨,没有给出完整的图结构描述,边权描述存在歧义("四条边分别是 2 10 4 6"不够清晰),但核心思想正确。

得分:8分(满分10分)

题目总分:8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发