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

admin2022-06-07 36

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

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

答案D

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

转载请注明原文地址:https://jikaoti.com/ti/WzDjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

计算机指令系统中采用多种寻址方式的目的是()。

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

下面关于电子邮件的说法中，不正确的是()。

判断加减法溢出时，可采用判断进位的方式，如果符号位的进位为C0，最高数值位为C1，产生溢出的条件是()。I．C0生进位；Ⅱ．C1产生进位；Ⅲ．C0、C1都产生进位；Ⅳ．C0、C1都不产生进位；V．C0产

用某种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：(1)25，84，21，47，15，27，68，35，20(2)20，15，21，25，47，27，68，35，84

一种数据编码的海明距是7，那么使用这种编码最多可以纠正()个错误。

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

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

(2006年)设f(x，y)是连续函数，则∫01dx∫01f(x，y)dy=()。

岩石三轴压缩的全应力应变曲线特点和有声发射现象反映出()。

股票回购后股东会得到纳税上的好处，因而股票购回肯定对股东有利。()

下列计量单位中，()不属于SI基本单位。

一般在教学开始前进行，摸清学生的现有水平及个别差异，这种评价称之为()

X光片：骨折

旅游商品，是指旅游者在旅游活动中出于非商业性目的而购买的实物性商品，它不包含维持旅游活动所必需的生活用品。根据上述定义，下列属于旅游商品的是()。

元朝统领吏、户、礼、兵、刑、工六部的中央国家机构是()(2017年非法学综合课单选第40题)

CellPhoneLetsYourSecretOutYourcellphoneholdssecretsaboutyou.Besidesthenamesand【C1】______thatyou’veprogra

Mostcometshavetwokindsoftails,onemadeupofdust,______madeupofelectricallychargedparticlescalledplasma.