拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_____。

admin2018-07-23 41

问题拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_____。

选项 A、包含回路
B、是强连通图
C、是完全图
D、是有向树

答案A

解析本题考查拓扑排序的概念。
对一个有向无环图(Directed Acyclic Graph，DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若＜u，v＞∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。需要注意的是：①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的；②若图中存在有向环，则不可能使顶点满足拓扑次序；③一个DAG的拓扑序列通常表示某种方案切实可行。由注意的第②点可知，本题正确答案为A。

转载请注明原文地址:https://www.kaotiyun.com/show/DfRZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_____。

软件设计师上午基础知识考试

软考中级

我国国家标准代号由大写汉语拼音字母构成，标准编号的后两位数字表示国家标准发布的(6)。

在下列解决死锁的方法中，不属于死锁预防策略的是()。

软件开发过程中，抽取和整理用户需求并建立问题域精确模型的过程叫______。

端口操作符在协议类型为TCP或UDP时支持端口比较，支持的比较操作包括：等于、大于、小于、不等于或介于等，其中，“介于”的关键字为______。

Cache用于存放主存数据的部分副本，主存单元地址与Cache单元地址之间的转换工作由__________完成。

假设某分时系统采用简单时间片轮转发，当系统中的用户数为n，时间片为q时，系统对每个用户的响应时间T为__________。(2013年上半年试题)

假设生产管理网络系统采用B／S工作方式，经常上网用户数为150个，每用户每分钟产生8个事务处理任务，平均事务量大小为0．05MB，则这个系统需要的信息传输速率为__________。(2010年上半年试题)

通过CATV电缆访问因特网，在用户端必须安装的设备是______。

Comparisons　were　drawn　between　the　development　of　television　in　the　20th　century　and　the　diffusion　of　printing　in　the　15th　and　1

败毒散可用于()(2007年第133题)

当前窗口处于最大化状态，双击该窗口标题栏，则相当于单击()

CO2和O2跨膜转运属于

某60m高层办公楼中，自备柴油发电机房所配备的日用油箱间内的油箱容积须满足()。

下列有关文学常识的说法，错误的是()。

有以下程序：#include＜stdio.h＞voidfun(char**p){++P；printf("%s\n"，p)；}main()chara[]={"Morning"，"Afternoon"，"E

Aboutthenewfinding,whichofthefollowingstatementsisCORRECT?

Some30,000localretail,cateringandtourismfirmsareexpectedtoparticipateinthe2009HangzhouLeisureandShoppingFesti

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_____。

软件设计师上午基础知识考试

软考中级

我国国家标准代号由大写汉语拼音字母构成，标准编号的后两位数字表示国家标准发布的(6)。

在下列解决死锁的方法中，不属于死锁预防策略的是()。

软件开发过程中，抽取和整理用户需求并建立问题域精确模型的过程叫______。

端口操作符在协议类型为TCP或UDP时支持端口比较，支持的比较操作包括：等于、大于、小于、不等于或介于等，其中，“介于”的关键字为______。

Cache用于存放主存数据的部分副本，主存单元地址与Cache单元地址之间的转换工作由__________完成。

假设某分时系统采用简单时间片轮转发，当系统中的用户数为n，时间片为q时，系统对每个用户的响应时间T为__________。(2013年上半年试题)

假设生产管理网络系统采用B／S工作方式，经常上网用户数为150个，每用户每分钟产生8个事务处理任务，平均事务量大小为0．05MB，则这个系统需要的信息传输速率为__________。(2010年上半年试题)

通过CATV电缆访问因特网，在用户端必须安装的设备是______。

Comparisons were drawn between the development of television in the 20th century and the diffusion of printing in the 15th and 1

败毒散可用于()(2007年第133题)

当前窗口处于最大化状态，双击该窗口标题栏，则相当于单击()

CO2和O2跨膜转运属于

某60m高层办公楼中，自备柴油发电机房所配备的日用油箱间内的油箱容积须满足()。

下列有关文学常识的说法，错误的是()。

有以下程序：#include＜stdio.h＞voidfun(char**p){++P；printf("%s\n"，*p)；}main()char*a[]={"Morning"，"Afternoon"，"E

Aboutthenewfinding,whichofthefollowingstatementsisCORRECT?

Some30,000localretail,cateringandtourismfirmsareexpectedtoparticipateinthe2009HangzhouLeisureandShoppingFesti

Comparisons　were　drawn　between　the　development　of　television　in　the　20th　century　and　the　diffusion　of　printing　in　the　15th　and　1

有以下程序：#include＜stdio.h＞voidfun(char**p){++P；printf("%s\n"，p)；}main()chara[]={"Morning"，"Afternoon"，"E