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

admin2018-07-23 28

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

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

软考中级

与routeprint具有相同功能的命令是()。

在下面4种病毒中，()可以远程控制网络中的计算机。

应该在()阶段制定系统测试计划。

假设模拟信号的最高频率为5MHz，采样频率必须大于()，才能使得到的样本信号不失真。

网络122．21．136．0／24和122．21．143．0／24经过路由汇聚，得到的网络地址是()。

对于IP地址159.202.176.1，是一个(110)。

如果希望别的计算机不能通过ping命令测试服务器的连通情况，可以(1)。如果希望通过默认的Telnet端口连接服务器，则下面对防火墙配置正确的是(2)。(2008年上半年试题)(2)

按照网络分级设计模型，通常把网络设计为3层，即核心层、汇聚层和接入层，以下关于分级网络的描述中，不正确的是(55)。

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

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

宁红太子茶艺第七道将水质、茶质喻为()。

Manyateacher______toaskhowtoattendthetrainingprogram.

女，35岁，身高160cm，体重75kg。查体：血压150/90mmHg，两下腹壁及大腿内侧有纵行红色纹。下列何项检查不能用以鉴别肾上腺皮质增生和腺瘤

少阴经头痛的特征是

A．绞釉B．釉丛C．釉梭D．釉柱横纹E．釉质生长线釉柱内2／3弯曲形成()。

根据有关规定，尚未公开的()信息属于内幕信息。

一般情况下，还款可能性分析包括()。

固定资产盘盈，应计入当期损益，影响当期的损益。()

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

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

软考中级

与routeprint具有相同功能的命令是()。

在下面4种病毒中，()可以远程控制网络中的计算机。

应该在()阶段制定系统测试计划。

假设模拟信号的最高频率为5MHz，采样频率必须大于()，才能使得到的样本信号不失真。

网络122．21．136．0／24和122．21．143．0／24经过路由汇聚，得到的网络地址是()。

对于IP地址159.202.176.1，是一个(110)。

如果希望别的计算机不能通过ping命令测试服务器的连通情况，可以(1)。如果希望通过默认的Telnet端口连接服务器，则下面对防火墙配置正确的是(2)。(2008年上半年试题)(2)

按照网络分级设计模型，通常把网络设计为3层，即核心层、汇聚层和接入层，以下关于分级网络的描述中，不正确的是(55)。

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

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

宁红太子茶艺第七道将水质、茶质喻为()。

Manyateacher______toaskhowtoattendthetrainingprogram.

女，35岁，身高160cm，体重75kg。查体：血压150/90mmHg，两下腹壁及大腿内侧有纵行红色纹。下列何项检查不能用以鉴别肾上腺皮质增生和腺瘤

少阴经头痛的特征是

A．绞釉B．釉丛C．釉梭D．釉柱横纹E．釉质生长线釉柱内2／3弯曲形成()。

根据有关规定，尚未公开的()信息属于内幕信息。

一般情况下，还款可能性分析包括()。

固定资产盘盈，应计入当期损益，影响当期的损益。()

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