首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
admin
2014-04-17
86
问题
以下有关拓扑排序的说法中,错误的是( )。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案
D
解析
Ⅰ:如果一个有向图存在环路,则该有向图肯定不会存在拓扑排序,这是因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。
Ⅲ:一个反例如图8—9所示。该有向图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。
转载请注明原文地址:https://kaotiyun.com/show/oixi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述近代香港问题的形成。
试析英法绥靖政策和美国中立政策的原因。(南京大学2013年国际关系史真题)
戊戌政变发生的时间是()。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
第三次科技革命促进了社会经济结构和社会生活结构的变化,其在社会经济结构方面的变化主要是()
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
随机试题
下列情形中,运用了德育方法的品德评价法的是()
1990年8月,某远洋客轮上发生一起军团病爆发流行。船离开港口时载有350名乘客、50名船员。8月1日前的一周内,在一次风暴中有七分之一的乘客遇难。8月份第一周中,船上有30人发生军团病,其中一半很快死亡。随后的一周内又有20人发病,但无死亡。假设症状持
18岁,晨卧床不起,人事不省,多汗,流涎,呼吸困难。体检:神志不清,双瞳孔缩小如针尖,双肺布满湿啰音,心率60次/分,肌束震颤,抽搐,最可能的诊断是
电梯井口必须设置高度不低于1.1m的金属防护门。
四方公司于2004年2月销售自己使用过应征消费税的游艇1艘(该游艇的原值为8万元),取得10万元(含税)收入,根据我国增值税法的规定,该公司应纳()万元的增值税。
【2015.广西】儿童在听了科尔伯格的道德两难故事“海因茨偷药”后,认为海因茨不应该去偷药,因为如果人人都违法去偷东西的话,社会会变得很混乱,这些儿童的道德水平处于()。
我国选举制度中,体现选举权的普遍性原则的是()
NancyhadA(agreatdealof)troubleB(toconcentrateon)herworkC(becauseof)thenoiseD(in)thenextroom.
Itistruethatthegroupinteractionshavebothpositiveandnegativesides.Whenwe【B1】______,conflictcannotbegottenrido
A、Heisthoughtful.B、Heishumorous.C、Heiscareless.D、Heishelpful.C综合推断题。女士说她再也不跟Bill一块儿走了,他竟然忘记把车停哪里了,由此可知,比尔是个比较粗心的人。
最新回复
(
0
)