文章
7
粉丝
0
获赞
0
访问
366
评分及理由
(1)得分及理由(满分3分)
学生未画出带权有向图,也未给出顶点和边的具体信息,与标准答案要求不符。根据标准答案,需要正确画出图并标注顶点和边权重,学生完全未作答,因此得0分。
(2)得分及理由(满分3分)
学生回答“添加A到D的边”和“删除D到A权值为1的边”,但标准答案中强连通分量数量为4,添加边的最优方案是添加G到D的边(仅需1条),删除边的最优方案是删除D到A和E到C的边(需2条)。学生的添加方案(A到D)可能减少强连通分量,但并非最优(需验证图结构),且未说明强连通分量数量(扣1分);删除方案中“删除D到A权值为1的边”错误(实际权重为3,但权重误写不扣分),但删除D到A边是正确的操作,不过仅删除一条边不足以使所有强连通分量大小变为1(还需删除其他边如E到C),学生未完整给出方案(扣1分)。此外,学生未回答强连通分量数量(扣1分)。因此得0分。
(3)得分及理由(满分3分)
学生回答“若存在拓扑排序且权值和最大,则存在关键路径”,但关键路径的存在需满足有向无环图(通过拓扑排序判断)和AOE网条件(唯一源点、汇点等),学生未提及AOE网条件(扣1分)。后半句“手写拓扑排序算法,使得栈中存放有效路径;有向图”表述模糊,未说明十字链表的优势(标准答案强调十字链表在逆拓扑序中直接访问入边的便利性)。学生未回答优势部分(扣2分)。因此得0分。
题目总分:0+0+0=0分
登录后发布评论
暂无评论,来抢沙发