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

admin2022-06-07 58

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

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

答案D

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是()。

在页式存储管理中，每个页表的表项实际上是用于实现()。

某公司网络拓扑图如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202．118．2．1；R2的L0接口的IP地址是202．118．2．2，L1

设有4台主机A、B、C和D都处在同一物理网络中，它们的IP地址分别为192．155．28．112、192．155．28．120、192．155．28．135和192．155．28．202，子网掩码都是255．255．255．224，请回答：若要使该网络

在虚拟地址和物理地址均为32位、页大小为4KB的某种体系结构中，假定存在下表所示的地址映像关系，问：对应于下列虚拟地址的物理地址分别是什么?(1)22433007H(2)13385ABCH(3)ABC89011H

在存储系统管理中，采用覆盖与交换技术的目的是()。

为实现快速排序算法，待排序序列宜采用的存储方式是____。

下列叙述中，不符合m阶B树定义要求的是_______。

通道管理没有涉及的数据结构有()。Ⅰ．设备控制表Ⅱ．控制器控制表Ⅲ．通道控制表Ⅳ．系统设备表Ⅴ．内存分配表

男，24岁，突然意识不清，跌倒，全身强直数秒钟后抽搐，咬破舌。2分钟后抽搐停止。醒后活动正常。该患者首选治疗药物是

慢性病的自然病程从无危险阶段之后的五个阶段中有哪个不是

不属于Spee’s曲线特点的是

根据《环境影响评价技术导则—地下水环境》，地下水污染源调查因子应根据()选定。

_______是形成各种技能所不可缺少的关键环节。

1999年哪一种股票单股收益最高?1999年买1500股沈阳机床收益为多少元?

（浙江大学2010年试题）ThecharacterofEuropeaneducationdemandsthatthestudentdevelop【1】andsocialindividuality.TheAmerican

Thereenactorsarebusloadsoftourists—usuallyTurkish,sometimesEuropean.Thebusesblunderoverthewinding,indifferently

A、Runningwhencaughtinastorm.B、Shelteringfromtherainunderatree.C、Takinganumbrellawithyou.D、Walkingintherain