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

admin2018-07-23 66

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

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

x.25分组层的主要功能是(16)。

原型化方法是用户和设计者之间执行的一种交互构成，适用于______　系统。

我国国家标准代号由大写汉语拼音字母构成，标准编号的后两位数字表示国家标准发布的(6)。

单指令流多数据流计算机由______。

对象模型表示静态的、结构化的系统数据性质，描述系统的静态结构。它从现实世界实体的相互关系的角度来描述、表现对象间的相互关系。该模型主要关心系统中对象的结构、属性和操作，使用了______　的工具来刻画。

通过ADSL访问Internet，在用户端通过()和ADSLModem连接PC机。

循环冗余校验标准CRC-16的生成多项式为G(x)=X166+X15+X2+1，它产生的校验码是(13)位。接收端发现错误后采取的措施是(14)。(14)

内存单元按字节编址，地址0000A000H～0000BFFFH共有__________个存储单元。(2012年上半年试题)

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

国际储备的来源有

患儿，男，5岁。反复水肿1年余。入院后查：尿蛋白(＋＋～＋＋＋)，红细胞0～10／HP，血尿素氮11．5mmol／L，血浆总蛋白为42g／L，白蛋白15g／L。本例患儿诊断首先考虑

不属于Ⅳ型变态反应的是()

企业在安全生产许可证有效期内，严格遵守有关安全生产的法律法规，未发生死亡事故的，安全生产许可证有效期届满时，经原安全生产许可证颁发管理机关同意，不再审查，安全生产许可证有效期延期()。

下列情况中应计算缴纳城镇土地使用税的是()。

A．患肢短缩，髋屈曲、内收、内旋畸形B．患肢短缩，髋屈曲、内收、外旋畸形C．患肢短缩，髋屈曲、外展、内旋畸形D．患肢短缩，髋屈曲、外展、外旋畸形E．患肢增长，髋伸直、外展、外旋畸形股骨颈骨折内收型可出现

【S1】【S9】

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

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

软考中级

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

x.25分组层的主要功能是(16)。

原型化方法是用户和设计者之间执行的一种交互构成，适用于______ 系统。

我国国家标准代号由大写汉语拼音字母构成，标准编号的后两位数字表示国家标准发布的(6)。

单指令流多数据流计算机由______。

对象模型表示静态的、结构化的系统数据性质，描述系统的静态结构。它从现实世界实体的相互关系的角度来描述、表现对象间的相互关系。该模型主要关心系统中对象的结构、属性和操作，使用了______ 的工具来刻画。

通过ADSL访问Internet，在用户端通过()和ADSLModem连接PC机。

循环冗余校验标准CRC-16的生成多项式为G(x)=X166+X15+X2+1，它产生的校验码是(13)位。接收端发现错误后采取的措施是(14)。(14)

内存单元按字节编址，地址0000A000H～0000BFFFH共有__________个存储单元。(2012年上半年试题)

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

国际储备的来源有

患儿，男，5岁。反复水肿1年余。入院后查：尿蛋白(＋＋～＋＋＋)，红细胞0～10／HP，血尿素氮11．5mmol／L，血浆总蛋白为42g／L，白蛋白15g／L。本例患儿诊断首先考虑

不属于Ⅳ型变态反应的是()

企业在安全生产许可证有效期内，严格遵守有关安全生产的法律法规，未发生死亡事故的，安全生产许可证有效期届满时，经原安全生产许可证颁发管理机关同意，不再审查，安全生产许可证有效期延期()。

下列情况中应计算缴纳城镇土地使用税的是()。

A．患肢短缩，髋屈曲、内收、内旋畸形B．患肢短缩，髋屈曲、内收、外旋畸形C．患肢短缩，髋屈曲、外展、内旋畸形D．患肢短缩，髋屈曲、外展、外旋畸形E．患肢增长，髋伸直、外展、外旋畸形股骨颈骨折内收型可出现

【S1】【S9】

原型化方法是用户和设计者之间执行的一种交互构成，适用于______　系统。

对象模型表示静态的、结构化的系统数据性质，描述系统的静态结构。它从现实世界实体的相互关系的角度来描述、表现对象间的相互关系。该模型主要关心系统中对象的结构、属性和操作，使用了______　的工具来刻画。