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

admin2018-07-23 22

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

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

设信道的码元速率为500波特，采用4相DPSK调制，则信道的数据速率为(5)bit/s。

若某文件系统的目录结构如图2．6所示，假设用户要访问文件f1．java，且当前工作目录为Program，则该文件的全文件名为()。

(42)是错误的软件编码的原则。

下列各项(4)制定的标准是国际标准。

我国在国家标准管理办法中规定，国家标准的有效期(自标准实施之日起，至标准复审重新确认、修订或废止的时间)一般为(2)年。(2)

以下关于边界网关协议BGP4的叙述中，不正确的是______。

下图中12位曼彻斯特编码的信号波形表示的数据是(14)。

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

【说明】①定义类Table的私有数据成员x和y，分别用于表示九九表中的两个乘数(xy)，它们都是int型的数据。②完成类Table的成员函数print()的定义，该函数以“xy=z”的格式打印出九九表中的一个乘法算式，请使用格式化输出函

A．芎菊上清丸B．半夏白术天麻汤C．天麻钩藤饮D．杞菊地黄丸E．羚羊钩藤汤

财政赤字可以刺激经济增长，所以越多越好。(　　)

根据《刑法》的规定，骗取出口退税罪(　　)。

在下列资产的盘盈、盘亏中，可能计入“管理费用”的有()。

西安化觉寺位于陕西西安化觉巷，为中国传统式建筑，是我国现存规模最大，保存最完整的清真寺。()

音位不变，将升高半音，下列选项中正确的是()

教育立法是指国家立法机关依照法律程序制定有关教育法律的活动。()

斯金纳训练鸽子学习走“8”字形路线所采用的主要技术是()

设变换，其中x二阶连续可偏导，求常数a．

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

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

软考中级

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

设信道的码元速率为500波特，采用4相DPSK调制，则信道的数据速率为(5)bit/s。

若某文件系统的目录结构如图2．6所示，假设用户要访问文件f1．java，且当前工作目录为Program，则该文件的全文件名为()。

(42)是错误的软件编码的原则。

下列各项(4)制定的标准是国际标准。

我国在国家标准管理办法中规定，国家标准的有效期(自标准实施之日起，至标准复审重新确认、修订或废止的时间)一般为(2)年。(2)

以下关于边界网关协议BGP4的叙述中，不正确的是______。

下图中12位曼彻斯特编码的信号波形表示的数据是(14)。

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

【说明】①定义类Table的私有数据成员x和y，分别用于表示九九表中的两个乘数(x*y)，它们都是int型的数据。②完成类Table的成员函数print()的定义，该函数以“x*y=z”的格式打印出九九表中的一个乘法算式，请使用格式化输出函

A．芎菊上清丸B．半夏白术天麻汤C．天麻钩藤饮D．杞菊地黄丸E．羚羊钩藤汤

财政赤字可以刺激经济增长，所以越多越好。( )

根据《刑法》的规定，骗取出口退税罪( )。

在下列资产的盘盈、盘亏中，可能计入“管理费用”的有()。

西安化觉寺位于陕西西安化觉巷，为中国传统式建筑，是我国现存规模最大，保存最完整的清真寺。()

音位不变，将升高半音，下列选项中正确的是()

教育立法是指国家立法机关依照法律程序制定有关教育法律的活动。()

斯金纳训练鸽子学习走“8”字形路线所采用的主要技术是()

设变换，其中x二阶连续可偏导，求常数a．

【说明】①定义类Table的私有数据成员x和y，分别用于表示九九表中的两个乘数(xy)，它们都是int型的数据。②完成类Table的成员函数print()的定义，该函数以“xy=z”的格式打印出九九表中的一个乘法算式，请使用格式化输出函

财政赤字可以刺激经济增长，所以越多越好。(　　)

根据《刑法》的规定，骗取出口退税罪(　　)。