首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
admin
2022-06-07
72
问题
以下有关拓扑排序的说法中,错误的是( )。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案
D
解析
Ⅰ:如果一个有向图存在环路,则肯定不会存在拓扑排序,因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。
Ⅲ: —个反例如图8—9所示。该图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。
转载请注明原文地址:https://www.kaotiyun.com/show/jt3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。文件A在该文件目录中的位置如下图所示。此树
一个长度为L(L≥1)的升序序列s,处在第[L/2]个位置的数称为s的中位数。例如,若序列sl=(11,13,15,17,19),则s1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若s2=(2,4,6,8,20),则S1和s2
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
某公司网络拓扑图如下图所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口L0连接路由器R2,并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1;R2的L0接口的IP地址是202.118.2.2,L1
下列的应用层协议中,()是采用UDP传输的。
已知两个长度分别为m和n的升序链表,若将它们合并为一个长度为m+n的降序链表,则最坏情况下的时间复杂度是
(1)流水线的节拍时间应取各过程段所需时间的最大值,即100ns,该流水线的加速比为(80ns+100ns+60ns+90ns)/100ns=3.3(2)如四个过程段所需执行时间都为85ns,则流水线的节拍时间为85ns,流水线的
一棵二叉树的前序遍历序列为1234567,则它的中序遍历序列不可能为()。Ⅰ.3124567Ⅱ.1234567Ⅲ.4135627Ⅳ.1436572
若CPU要执行的指令为:MOVR0,R1(即将寄存器R1中的数据传送到寄存器R0中),则CPU首先要完成的操作是()。
判断括号是否匹配是栈的主要应用之一。设字符表达式存储在数组E[n]中,‘#’为字符表达式的结束符。给出一个算法,用于判断表达式中括号(’(’和’)’)是否配对。要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用C或C++或Java语言描述算法
随机试题
支配阑尾的神经是交感神经腹腔丛和
该研究属于要验证吸烟与冠心病的病因关系
肺炎喘嗽风寒闭肺型首选是肺炎喘嗽阴虚肺热型首选是
未提足折旧而提前报废的固定资产不需补提折旧。()
如何理解地理教学过程中教与学的关系?
拓展和畅通群众需求表达渠道,全面准确地了解群众需求是提高公共服务精准性与有效性的首要前提。下列做法不属于拓展和畅通群众需求表达渠道的是:
某单位经费紧张,现只有20万元,要办的事情就有下列几项:(1)解决办公室打电话难的问题:(2)装饰会议室、大厅等,以迎接上级单位委托承办的大型会议;(3)支付职工的高额医疗费;(4)五一节为单位职工发些福利。很明显.20万元无法将这四件事都办圆满。如果你是
一个软件产品开发完成投入使用后,常常由于各种原因需要对它做适当的变更。在软件的使用过程中,软件原来的(48)可能不再适应用户的要求,需要进行变更;软件的工作环境也可能发生变化:最常见的是配合软件工作的(49)有变动;还有一种情况是在软件使用过程中发现错误,
汇编语言是一种()。
Weallhaveproblemsandbarriersthatblockourprogressorpreventusfrommovingintonewareas.Whenthathappens,consider
最新回复
(
0
)