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

admin2018-07-23 39

问题拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点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之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_____。

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

软考中级

现有四级指令流水线分别完成取指、取数、运算、传达结果四步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns，则流水线的操作周期应设计为______　ns。

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

路由器R1的连接和地址分配如图7．7所示，如果在R1上安装OSPF协议，运行下列命令：routerospf100，则配置SO和EO端口的命令是()。

若某计算机系统的I／O接口与主存采用统一编址，则输入输出操作是通过()指令来完成的。

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

下列行为不属于网络攻击的是()。

WindowsServer200．3中的IIS为Web服务器提供了许多选项，利用这些选项可以更好地配置Web服务的性能、行为和安全等。如下图所示属性页中，“限制网络带宽”选项属于__________选项卡。(2008年下半年试题)

软件能力成熟度模型(CMM)将软件能力成熟度自低到高依次划分为初始级、可重复级、定义级、管理级和优化级，其中__________对软件过程和产品都有定量的理解与控制。

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

当感觉到紧张时，通过参加各种社会活动、体育和娱乐活动调节情绪，开阔心胸，放松心理，这种消除紧张情绪的方法是()

归档文件是指本机关形成的文件。

求

下列属于我国器官移植的伦理原则的是

药品说明书和标签，是药品外在质量的主要体现，是传递药品信息，指导医师用药和消费者购买使用药品，以及药师开展合理用药咨询的主要依据之一。制定并发布药品说明书的具体格式、内容和书写要求的部门是()

下列项目中，引起负债和所有者权益有增有减的经济业务是(　　)。

新加坡著名的华人街景点的名称是()。

“孟母三迁”的故事中，孟母采取的德育方法是()

设矩阵A是一个n×n对称矩阵，即A[i,j]=A[j,i],为了节省存储空间，将其下三角部分按行序为主序存放在一维数D[1…n(n+1)/2]中，对任一下三角元素Aij(i≥j)，在一维数组B的下标位置k的值是______。

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

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

软考中级

现有四级指令流水线分别完成取指、取数、运算、传达结果四步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns，则流水线的操作周期应设计为______ ns。

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

路由器R1的连接和地址分配如图7．7所示，如果在R1上安装OSPF协议，运行下列命令：routerospf100，则配置SO和EO端口的命令是()。

若某计算机系统的I／O接口与主存采用统一编址，则输入输出操作是通过()指令来完成的。

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

下列行为不属于网络攻击的是()。

WindowsServer200．3中的IIS为Web服务器提供了许多选项，利用这些选项可以更好地配置Web服务的性能、行为和安全等。如下图所示属性页中，“限制网络带宽”选项属于__________选项卡。(2008年下半年试题)

软件能力成熟度模型(CMM)将软件能力成熟度自低到高依次划分为初始级、可重复级、定义级、管理级和优化级，其中__________对软件过程和产品都有定量的理解与控制。

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

当感觉到紧张时，通过参加各种社会活动、体育和娱乐活动调节情绪，开阔心胸，放松心理，这种消除紧张情绪的方法是()

归档文件是指本机关形成的文件。

求

下列属于我国器官移植的伦理原则的是

药品说明书和标签，是药品外在质量的主要体现，是传递药品信息，指导医师用药和消费者购买使用药品，以及药师开展合理用药咨询的主要依据之一。制定并发布药品说明书的具体格式、内容和书写要求的部门是()

下列项目中，引起负债和所有者权益有增有减的经济业务是( )。

新加坡著名的华人街景点的名称是()。

“孟母三迁”的故事中，孟母采取的德育方法是()

设矩阵A是一个n×n对称矩阵，即A[i,j]=A[j,i],为了节省存储空间，将其下三角部分按行序为主序存放在一维数D[1…n(n+1)/2]中，对任一下三角元素Aij(i≥j)，在一维数组B的下标位置k的值是______。

现有四级指令流水线分别完成取指、取数、运算、传达结果四步操作。若完成上述操作的时间依次为9ns、10ns、6ns、8ns，则流水线的操作周期应设计为______　ns。

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

下列项目中，引起负债和所有者权益有增有减的经济业务是(　　)。