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

admin2018-07-23 57

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

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

软考中级

某系统的进程状态转换如图2—4所示，图中1、2、3、4分别表示引起状态转换的不同原因，原因4表示()。

在面向对象的软件工程中，一个组件包含了()。

通过交换机连接的一组工作站()。

数字签名(Digital　Signature)：即是只有信息发送者使用公开密钥算法的主要技术产生的别人无法伪造的一段数字串。下列各项中，(1)是数字签名不能保证的。

常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。其中()适用于需求明确或很少变更的项目。

以下关于DHCP协议的描述中，错误的是()。

操作是类中对象所使用的一种功能或变换。类中的各个对象可以共享操作，方法是类中操作的　______　。

要实现VTP动态修剪，在VTP域中的所有交换机都必须配置成__________。(2010年下半年试题)

IEEE802．11定义的AdHoe网络是由无线移动结点组成的对等网，这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(63)

已知D(X)=25，D(Y)=36，pxy=0.4，试求D(X+Y)和D（X-Y）。

在静电复印过程中感光版的表面电位随时问的变化曲线称为感光版的______。

下列哪种情况不属于占有()

老年人易发生便秘的主要原因是

霍乱流行期最重要的传染源是

A．癌前病变B．早期胃癌C．良性肿瘤D．恶性肿瘤E．肉瘤直、结肠家族性多发性腺瘤性息肉属于

有时调查对象对询问的问题不愿意真实回答，使结果产生误差称在随机抽样时，属于样本人群中的受检者，由于主观或客观原因未能接受检查，如超过抽样人数的30%可产生不准确的结果，这种误差称

反映银行资本金与风险资产总额关系的指标为()。

在新课程中，教师的教学行为将发生变化，下列说法正确的是()。

Perhapsitwouldn’tbe______togoandseesuchafilm.

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

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

软考中级

某系统的进程状态转换如图2—4所示，图中1、2、3、4分别表示引起状态转换的不同原因，原因4表示()。

在面向对象的软件工程中，一个组件包含了()。

通过交换机连接的一组工作站()。

数字签名(Digital Signature)：即是只有信息发送者使用公开密钥算法的主要技术产生的别人无法伪造的一段数字串。下列各项中，(1)是数字签名不能保证的。

常见的软件开发模型有瀑布模型、演化模型、螺旋模型、喷泉模型等。其中()适用于需求明确或很少变更的项目。

以下关于DHCP协议的描述中，错误的是()。

操作是类中对象所使用的一种功能或变换。类中的各个对象可以共享操作，方法是类中操作的 ______ 。

要实现VTP动态修剪，在VTP域中的所有交换机都必须配置成__________。(2010年下半年试题)

IEEE802．11定义的AdHoe网络是由无线移动结点组成的对等网，这种网络的特点是(62)。在这种网络中使用的DSDV(Destination-SequencedDistanceVector)路由协议是一种(63)。(63)

已知D(X)=25，D(Y)=36，pxy=0.4，试求D(X+Y)和D（X-Y）。

在静电复印过程中感光版的表面电位随时问的变化曲线称为感光版的______。

下列哪种情况不属于占有()

老年人易发生便秘的主要原因是

霍乱流行期最重要的传染源是

A．癌前病变B．早期胃癌C．良性肿瘤D．恶性肿瘤E．肉瘤直、结肠家族性多发性腺瘤性息肉属于

有时调查对象对询问的问题不愿意真实回答，使结果产生误差称在随机抽样时，属于样本人群中的受检者，由于主观或客观原因未能接受检查，如超过抽样人数的30%可产生不准确的结果，这种误差称

反映银行资本金与风险资产总额关系的指标为()。

在新课程中，教师的教学行为将发生变化，下列说法正确的是()。

Perhapsitwouldn’tbe______togoandseesuchafilm.

数字签名(Digital　Signature)：即是只有信息发送者使用公开密钥算法的主要技术产生的别人无法伪造的一段数字串。下列各项中，(1)是数字签名不能保证的。

操作是类中对象所使用的一种功能或变换。类中的各个对象可以共享操作，方法是类中操作的　______　。