查看更多
当前 - 选择题 - 前趋图
简单
单选题
2020年11月第1题
#第二版教材
#必须掌握

前趋图是一个有向无环图,记为:→={(Pi,Pj)} | 在 Pj 开始前,Pi 需要完成 }。假设系统中进程 P={P1,P2,P3,P4,P5,P6,P7},且进程的前趋图如下:

那么,该前趋图可记为(__)。

问题(1)
浓缩知识点

前趋图是一种有向无环图(DAG),核心用于描述进程或任务间的先后执行约束关系,图中有序对(Pi,Pj)表示必须在Pi执行完成后,Pj才能启动,这类图绝对不能存在环结构,否则会引发循环依赖导致死锁。读取前趋图时,需严格遵循箭头指向梳理所有依赖关系,不能颠倒边的方向,也不能凭空添加或遗漏合法的先后约束。它在操作系统进程调度、项目任务编排等场景中广泛应用,能清晰界定并发执行单元间的逻辑先后,保障执行流程的正确性与合理性。

正确答案
B

本题考察的是前趋图(有向无环图,DAG)中边的含义与读取
根据图中的箭头方向,能够读出全部先后约束:P1→P2、P1→P3、P1→P4;P2→P3、P3→P4;P2→P5、P3→P5、P4→P5;P5→P6、P5→P7;P6→P7。
A选项:包含多处方向颠倒与不存在的边,例如(P3,P1)与(P4,P1)应为从P1指向P3、P4;(P5,P2)与(P5,P3)方向也应为P2、P3指向P5;还将(P7,P5)写反且同时给出(P7,P6)与(P6,P7)造成矛盾,因此错误。
B选项:与图中所有箭头一致,既包含P1到P2/P3/P4,亦包含P2到P3、P3到P4,以及到P5的三条入边和从P5到P6、P7及P6到P7的关系,完全正确。
C选项:将(P5,P3)与(P7,P5)写反,正确应为(P3,P5)与(P5,P7),因此错误。
D选项:给出不存在或方向错误的边,如(P3,P6)与(P4,P7)在图中并无;同时(P6,P5)与(P7,P5)方向应为从P5指向P6、P7,故错误。
因此,选项 B 正确。

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有