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

admin2018-07-23 45

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

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

软考中级

A、B两人在同一时间就同样的发明创造提交了专利申请，那么，专利局不可能采用(9)的办法解决这一问题。

在网络设计阶段进行通信流量分析时可以采用简单的80／20规则。下面关于这种规则的说明中，正确的是()。

为避免地址的浪费，在一条点到点的链路上子网掩码应该指定为(4)

软件开发过程中，抽取和整理用户需求并建立问题域精确模型的过程叫______。

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

ATM适配层的功能是()。

CHAP协议是PPP链路中采用的一种身份认证协议，这种协议采用(19)握手方式周期性地验证通信对方的身份，当认证服务器发出一个挑战报文时，则终端就计算该报文的(20)并把结果返回服务器。(19)

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

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

甘特图(Gantt图)不能_______。

初产妇，24岁。妊娠38周，规律宫缩7小时。血压110／70mmHg，骨盆不小，预测胎儿体重为2800g，枕左前位，胎心良。肛查宫口开大4cm，S=0。正确处置应是()

某女40岁，月经漏下不止，经血色暗伴有血块已有2月，时见乏力倦怠，舌边尖有瘀点，脉涩，对其应采用的治则是

不能直接用于工程的材料是()。

下列关于固定资产模块设置的说法，正确的有()。

下列各项中，企业确定生产成本在完工产品与在产品之间的分配方法时，应考虑的具体条件有()。

旅游活动对社会的影响有哪些?

五岁的小东随父母迁居到另一个国家，父母让他每天与新的小伙伴们一起自由地玩耍，完全不进行任何语言教学，最后，小东在几个月内就掌握了一种新的语言，而且还学会了当地的口音。小东对语言的学习属于

Researchersarefindingthatboysandgirlsreallyarefromtwodifferentplanets.Boysandgirlshavedifferent"crisispoints"

—Haveyougotyourfinalresult?—Notyet.Thepapers_______.

Acollegelibraryisaninexhaustibleandeverchangingstorehouseofinformation.Newbooks,periodicals,andother【67】ofinfor

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

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

软考中级

A、B两人在同一时间就同样的发明创造提交了专利申请，那么，专利局不可能采用(9)的办法解决这一问题。

在网络设计阶段进行通信流量分析时可以采用简单的80／20规则。下面关于这种规则的说明中，正确的是()。

为避免地址的浪费，在一条点到点的链路上子网掩码应该指定为(4)

软件开发过程中，抽取和整理用户需求并建立问题域精确模型的过程叫______。

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

ATM适配层的功能是()。

CHAP协议是PPP链路中采用的一种身份认证协议，这种协议采用(19)握手方式周期性地验证通信对方的身份，当认证服务器发出一个挑战报文时，则终端就计算该报文的(20)并把结果返回服务器。(19)

Withcircuitswitching,a(71)________________pathisestablishedbetweentwostationsforcommunication．Switchingandtransmissi

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

甘特图(Gantt图)不能_______。

初产妇，24岁。妊娠38周，规律宫缩7小时。血压110／70mmHg，骨盆不小，预测胎儿体重为2800g，枕左前位，胎心良。肛查宫口开大4cm，S=0。正确处置应是()

某女40岁，月经漏下不止，经血色暗伴有血块已有2月，时见乏力倦怠，舌边尖有瘀点，脉涩，对其应采用的治则是

不能直接用于工程的材料是()。

下列关于固定资产模块设置的说法，正确的有()。

下列各项中，企业确定生产成本在完工产品与在产品之间的分配方法时，应考虑的具体条件有()。

旅游活动对社会的影响有哪些?

五岁的小东随父母迁居到另一个国家，父母让他每天与新的小伙伴们一起自由地玩耍，完全不进行任何语言教学，最后，小东在几个月内就掌握了一种新的语言，而且还学会了当地的口音。小东对语言的学习属于

Researchersarefindingthatboysandgirlsreallyarefromtwodifferentplanets.Boysandgirlshavedifferent"crisispoints"

—Haveyougotyourfinalresult?—Notyet.Thepapers_______.

Acollegelibraryisaninexhaustibleandeverchangingstorehouseofinformation.Newbooks,periodicals,andother【67】ofinfor

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