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

admin2018-07-23 27

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

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

软考中级

通过“Internet信息服务(IIS)管理器”管理单元可以配置FTP服务，若将控制端口设置为2222，则数据端口自动设置为()。

在数据通信中，将信道上的数字信号变换成模拟信号的过程称之为(59)。

在我国著作权法中，(7)是指同一个概念。

目前在网络上流行的“熊猫烧香”病毒属于()类型的病毒。

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

算术表达式a+(1)一c)d的后缀式是(10)(-、+、表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

设信道带宽为3400Hz，采用PcM编码，采样周期为125μs，每个样本量化为128个等级，则信道的数据速率为()。

面向对象开发方法的基本思想是尽可能按照人类认识客观世界的方法来分析和解决问题，()方法不属于面向对象方法。

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

警跻人

寄生虫病自然疫源地所具备的条件，哪项是错误的

增殖型肠结核患者不经常出现的临床表现是

贸易术语的国际贸易惯例主要有()。

下列关于预收款的特点说法不正确的有()。

公共支出，也称财政支出或政府支出，是政府为履行其职能而购买相应商品和劳务从而支出的一切费用的总和。政府进行货币资金支出的活动，其行为依据是()。

A:CanIseeyourdrivinglicence?B:______

数据库管理系统中用来定义模式、内模式和外模式的语言为

A、Mostnicknamesarequiteinteresting.B、Somestatenicknameshavesurprisingorigins.C、GeorgeWashingtonhasmanynicknames.

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

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

软考中级

通过“Internet信息服务(IIS)管理器”管理单元可以配置FTP服务，若将控制端口设置为2222，则数据端口自动设置为()。

在数据通信中，将信道上的数字信号变换成模拟信号的过程称之为(59)。

在我国著作权法中，(7)是指同一个概念。

目前在网络上流行的“熊猫烧香”病毒属于()类型的病毒。

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

算术表达式a+(1)一c)*d的后缀式是(10)(-、+、*表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

设信道带宽为3400Hz，采用PcM编码，采样周期为125μs，每个样本量化为128个等级，则信道的数据速率为()。

面向对象开发方法的基本思想是尽可能按照人类认识客观世界的方法来分析和解决问题，()方法不属于面向对象方法。

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

警跻人

寄生虫病自然疫源地所具备的条件，哪项是错误的

增殖型肠结核患者不经常出现的临床表现是

贸易术语的国际贸易惯例主要有()。

下列关于预收款的特点说法不正确的有()。

公共支出，也称财政支出或政府支出，是政府为履行其职能而购买相应商品和劳务从而支出的一切费用的总和。政府进行货币资金支出的活动，其行为依据是()。

A:CanIseeyourdrivinglicence?B:______

数据库管理系统中用来定义模式、内模式和外模式的语言为

A、Mostnicknamesarequiteinteresting.B、Somestatenicknameshavesurprisingorigins.C、GeorgeWashingtonhasmanynicknames.

算术表达式a+(1)一c)d的后缀式是(10)(-、+、表示算术的减、加、乘运算，运算符的优先级和结合性遵循惯例)。

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