首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下有关拓扑排序的说法中，错误的是( )。 Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序 Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列 Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1
以下有关拓扑排序的说法中，错误的是( )。 Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序 Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列 Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1
admin
2019-12-10
21
问题
以下有关拓扑排序的说法中，错误的是( )。
Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序
Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列
Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案
D
解析
Ⅰ：如果一个有向图存在环路，则肯定不会存在拓扑排序，因为该环路找不到入度为0的结点，拓扑排序自然也就进行不下去了，故Ⅰ正确。
Ⅱ：使用栈来表示拓扑排序的序列，最后的出栈序列是逆拓扑排序，只需逆转过来即可，只是效率比较低；使用队列时，出队序列就是拓扑排序序列，故使用栈和队列都是可以的，只是效率不等而已，故Ⅱ正确。
Ⅲ：一个反例如图8-9所示。该图的拓扑有序序列是唯一的，但各个顶点的入度和出度可以超出1，故Ⅲ错误。
转载请注明原文地址:https://kaotiyun.com/show/SI3i777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
设磁盘的扇区大小为4KB，磁盘转速为15000r／min，磁盘平均寻道时间为4ms，最大数据传输速率为40MB／s，磁盘控制器开销时问为1ms，计算读写一个扇区所需平均时间(不考虑I／O请求队列中的等待时间)。
在一个8级中断的系统中，硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8，通过中断屏蔽技术，将中断处理优先顺序设置为1→3→5→7→2→4→6→8，如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达，CPU在按优先顺序处理到第
在一个长度为n(n>1)的带头结点的单链表h上，设有尾指针r(指向尾结点)，则执行()操作与链表的长度有关。
高度为4的4阶B树最多可容纳()个关键字(根是第1层)。
某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca
相对于微程序控制器，硬布线控制器的特点是()。
某阅览室晚间开放，第一个进入的读者开灯，最后一个离开的读者关灯。利用P、V原语操作实现读者进程。
以下关于查找方法的说法正确的是()。I顺序查找法只能在顺序存储结构上进行Ⅱ折半查找法可以在有序的双向链表上进行Ⅲ分块查找的效率与线性表被分为多少块有关
以下关于二叉排序树的说法正确的是()。I在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。Ⅱ每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树都是二叉排序树。Ⅲ在二叉排序树中，新插入的关
关于B一树，下列说法不正确的是()。
随机试题
A、Itisreconcilable.B、Itiscontradictory.C、Ithastobetreatedcarefully.D、Itisadifficulttohandle.A对话中，女士问Mr．Phelps是
实质性分析程序
IappliedforthejobthatIsawadvertised________thepaper.
帕金森病内科治疗首选药物为
石菖蒲具有的功效是
下列关于收集证据的表述不正确的有()
下列压缩机中，属于容积型往复式的有()压缩机。
生产安全事故发生后，受伤者或最先发现事故的人员应立即用最快的传递手段，向施工单位负责人报告。施工单位负责人接到报告后，必须向事故发生地县级以上人民政府建设主管部门和有关部门报告。其事故报告的内容有()。
应急预案的指导思想应坚持()的方针。
IhavebeenteachingforlongerthanIcaretosay,andalwaysofferacourseforenteringfreshmen.AndI’vediscoveredsomet
最新回复
(
0
)
