以下有关拓扑排序的说法中，错误的是( )。 Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序 Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列 Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1

admin2022-06-07 47

问题以下有关拓扑排序的说法中，错误的是( )。
Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序
Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列
Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1

选项 A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ

答案D

解析 Ⅰ：如果一个有向图存在环路，则肯定不会存在拓扑排序，因为该环路找不到入度为0的结点，拓扑排序自然也就进行不下去了，故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列，最后的出栈序列是逆拓扑排序，只需逆转过来即可，只是效率比较低；使用队列时，出队序列就是拓扑排序序列，故使用栈和队列都是可以的，只是效率不等而已，故Ⅱ正确。
Ⅲ: —个反例如图8—9所示。该图的拓扑有序序列是唯一的，但各个顶点的入度和出度可以超出1，故Ⅲ错误。

转载请注明原文地址:https://kaotiyun.com/show/jt3i777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

操作系统为用户提供了多种接口，它们是()。I．计算机高级指令；Ⅱ．终端命令；Ⅲ．图标菜单；Ⅳ．汇编语言；V．C语言；Ⅵ．系统调用；

下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是____。

按照IEEEE754标准规定的32位浮点数(41A4C000)16对应的十进制数是()。

以下4种以太网中，只能工作在全双工模式下的是()。Ⅰ．10BASE—T以太网Ⅱ．100BASE-T以太网Ⅲ．吉比特以太网Ⅳ．10吉比特以太网

下列调度算法中，不可能导致饥饿现象的是_______。

已知字符串S为"abaabaabacacaabaabcc"，模式串t为"abaabc"。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是_______。

关于网络层和传输层提供的服务，下面几个选项中正确的说法是()。

下列哪些情形，属于挪用公款归个人使用，从而可能构成挪用公款罪?()(2003／2／31)

InJuneof1973,ninewhalesbeachedontheFloridacoast.Beachingmeansswimmingoutoftheoceanontothebeach,andusually

有关双合诊描述，正确的是

总体规划草案由各级人民政府报()审议批准。

下列不属于非法集资特点的是()。

信贷档案是确定借贷双方法律关系和权利义务的重要凭证，是贷款管理情况的重要记录。()

相比其他检验方法，非参数检验尤其适用于以下何种数据的检验?

Aprojectlikelytoevolvein.thenearorintermediatefutureisspacetourism,apurely【B1】______activitythatwouldnothave

Acircleofclosefriendsandstrongfamilytiescanincreaseaperson’shealthmorethanexercise,losingweightorquittingci