文章

35

粉丝

0

获赞

0

访问

1.2k

头像
2011年计算机学科专业基础综合试题 - 第41题回答
数据结构
发布于2025年10月22日 18:10
阅读数 34

1.邻接矩阵如下

2.有向带权图如下

3.关键路径

1的最早和最晚执行时间为4

2的最早和最晚执行时间为4+5=9

3的最早和最晚执行时间为9+4=13

4的最早执行时间为9+3=12,最晚执行时间为13

5的最早和最晚执行时间为13+3=16

因此关键路径为0-1-2-3-5

路径长度为16


评分及理由

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

学生给出了邻接矩阵,但识别结果存在混乱。第一次识别结果与标准答案不符,但第二次识别结果(4,6,5,4,3,3,3)实际上是邻接矩阵上三角部分的正确元素序列。考虑到题目说明"存在识别错误的可能性较高",且学生明确画出了正确的邻接矩阵,判断为识别问题。邻接矩阵内容正确,得2分。

(2)得分及理由(满分2分)

学生画出了有向带权图,从图中可以看出边的关系与标准答案一致:0→1(4), 0→2(6), 1→2(5), 2→3(4), 2→4(3), 3→5(3), 4→5(3)。图的结构正确,得2分。

(3)得分及理由(满分4分)

学生正确计算了关键路径0→1→2→3→5,路径长度16。虽然计算过程中对顶点编号的描述不够规范(如"1的最早和最晚执行时间"应为"顶点1的最早发生时间"),但核心逻辑正确,关键路径和长度计算准确,得4分。

题目总分:2+2+4=8分

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发