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

admin2018-07-23 23

问题拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点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://kaotiyun.com/show/DfRZ777K

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

下面有关VLAN的语句中，正确的是()。

Needham—Schroeder协议是基于()的认证协议。

提供虚电路服务的通信子网内部的实际操作为(105)。

假设模拟信号的最高频率为5MHz，如果每个样本量化为256个等级，则传输的数据速率是()。

Linux系统中，默认安装DHCP服务的配置文件为()。

设备A的可用性为0．98，如下图所示将设备A并联以后的可用性为()。

下列_______不是我国建成的主干网。

对于文法G(S)：S→S+aT|aT|+aTT→aT|a对于句型aT+aaa，(28)是该句型的直接短语，(29)是该句型的句柄。

Developingreliable　software　on　time　and　within(66).represents　a　difficult　endeavor　for　many　organizations.　　　Usually　business　s

职业是指由于社会分工而形成的具有特定专业和专门职责、并能为从业者带来一定利益的工作。()

合成肌糖原的原料是

A．3个月B．6个月C．12个月D．24个月E．18个月易拉罐装果汁的保质期的是

患者男性，35岁，肾病综合征10年，血压升高2年，临床特点患者男性，30岁，发作性血压增高，发作时血压达200/120mmHg，伴面色苍白，出汗，持续半个小时，平时血压正常，临床特点为

下列用地，有条件的必须采取拍卖、招标方式出让土地使用权的有：()

在代销方式下，委托方确认销售收入的时间是()。

采用包装机包装食盐，要求500g装一袋，已知标准差σ=3g，要使食盐每包平均重量的95%置信区间长度不超过4.2g，样本量n至少为()。

安全正点是铁路运输企业提供运输服务的基本义务之一。()

设f’(x)=arcsin(x一1)2，f(0)=0，求∫01f(x))dx.

()是指攻击者发送虚假信息来欺骗其他用户。

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

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

软考中级

下面有关VLAN的语句中，正确的是()。

Needham—Schroeder协议是基于()的认证协议。

提供虚电路服务的通信子网内部的实际操作为(105)。

假设模拟信号的最高频率为5MHz，如果每个样本量化为256个等级，则传输的数据速率是()。

Linux系统中，默认安装DHCP服务的配置文件为()。

设备A的可用性为0．98，如下图所示将设备A并联以后的可用性为()。

下列_______不是我国建成的主干网。

对于文法G(S)：S→S+aT|aT|+aTT→*aT|*a对于句型aT+a*a*a，(28)是该句型的直接短语，(29)是该句型的句柄。

Developingreliable software on time and within(66).represents a difficult endeavor for many organizations. Usually business s

职业是指由于社会分工而形成的具有特定专业和专门职责、并能为从业者带来一定利益的工作。()

合成肌糖原的原料是

A．3个月B．6个月C．12个月D．24个月E．18个月易拉罐装果汁的保质期的是

患者男性，35岁，肾病综合征10年，血压升高2年，临床特点患者男性，30岁，发作性血压增高，发作时血压达200/120mmHg，伴面色苍白，出汗，持续半个小时，平时血压正常，临床特点为

下列用地，有条件的必须采取拍卖、招标方式出让土地使用权的有：()

在代销方式下，委托方确认销售收入的时间是()。

采用包装机包装食盐，要求500g装一袋，已知标准差σ=3g，要使食盐每包平均重量的95%置信区间长度不超过4.2g，样本量n至少为()。

安全正点是铁路运输企业提供运输服务的基本义务之一。()

设f’(x)=arcsin(x一1)2，f(0)=0，求∫01f(x))dx.

()是指攻击者发送虚假信息来欺骗其他用户。

对于文法G(S)：S→S+aT|aT|+aTT→aT|a对于句型aT+aaa，(28)是该句型的直接短语，(29)是该句型的句柄。

Developingreliable　software　on　time　and　within(66).represents　a　difficult　endeavor　for　many　organizations.　　　Usually　business　s