首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说明该有向图一定_____。
拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必然在顶点vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说明该有向图一定_____。
admin
2018-07-23
43
问题
拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若在有向图中从顶点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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在软件项目管理中可以使用各种图形工具来辅助决策,下面对Gantt图的描述中,不正确的是()。
以下关于钓鱼网站的说法中,错误的是()。
某银行为用户提供网上服务,允许用户通过浏览器管理自己的银行账户信息。为保障通信的安全,该Web服务器可选的协议是()。
与routeprint具有相同功能的命令是()。
下列行为不属于网络攻击的是()。
循环冗余校验标准CRC-16的生成多项式为G(x)=X166+X15+X2+1,它产生的校验码是(13)位。接收端发现错误后采取的措施是(14)。(14)
以下关于边界网关协议BGP4的叙述中,不正确的是______。
在基于Web的电子商务应用中,访问存储于数据库中的业务对象的常用方式之一是_____________。
文法G=({E),{+,*,(,),a},P,E),其中P由下列产生式组成E->E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式,该文法在乔姆斯基分层中属于(16)型文法,其对应的自动机是(17),如产生句子a*a+a,它的派生树是(
Developingreliable software on time and within(66).represents a difficult endeavor for many organizations. Usually business s
随机试题
欧洲质量奖与马尔科姆.波多里奇国家质量奖的不同点体现在______、________、________、__________。
十二指肠球部溃疡的疼痛规律为
卫生检疫机关的工作人员在实施卫生处理时,必须注意防止对任何人的健康造成危害。( )
以下属于房产税征税范围的是()。
下列选项中,不属于金融市场构成要素的是()。
存款类金融机构所设置的会计科目应符合单位自身特点,满足单位实际需要,这一点符合()原则。
伊斯兰教在()永徽二年(651年)传人中国。
教育理念
5,11,28,68,174,()
Wefindthatbrightchildrenarerarelyheldbackbymixed-abilityteaching.Onthecontrary,boththeirknowledgeandexperienc
最新回复
(
0
)