首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
admin
2014-04-17
35
问题
以下有关拓扑排序的说法中,错误的是( )。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案
D
解析
Ⅰ:如果一个有向图存在环路,则该有向图肯定不会存在拓扑排序,这是因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。
Ⅲ:一个反例如图8—9所示。该有向图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。
转载请注明原文地址:https://kaotiyun.com/show/oixi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试分析第二次世界大战的历史地位。
玛雅人的金字塔主要功能是()。
清朝入关初期执行了一些错误的政策,在社会上产生了不良的影响,其中不包括()。
抗日战争期间,日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理,而名义是()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
玛雅人的金字塔主要功能是()。
“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
随机试题
由对超自然实体的信仰和崇拜来支配人们命运的一种意识形态是()
下列病变中,斜位吞钡检查,不形成食管压迹的是
关于蛋白质合成的错误叙述是
润滑剂硬脂酸镁中的镁离子干扰硬脂酸根离子干扰
生产经营项目、场所有多个承包单位、承租单位的,生产经营单位应当与承包单位、承租单位签订专门的(),或者在承包合同、租赁合同中约定各自的()。
箱形预制梁制造技术证明书应()。
在计算劳动生产率时必须遵循的原则是()。
我国刑法的基本原则是()。
PASSAGEONEHowdoyousummarizethepartyscenedescribedinPara.6?
Forthispart,youareallowedthirtyminutestowriteacomposition.Youshouldwriteatleast100words,andbaseyourcomposi
最新回复
(
0
)