首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
admin
2022-06-07
27
问题
以下有关拓扑排序的说法中,错误的是( )。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案
D
解析
Ⅰ:如果一个有向图存在环路,则肯定不会存在拓扑排序,因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。
Ⅲ: —个反例如图8—9所示。该图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。
转载请注明原文地址:https://jikaoti.com/ti/WzDjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
假设主机1(在图2-4中网络1以太网上)是可以运行IE浏览器的某客户机,主机4(在图2—4中网络3以太网上)为天勤论坛Web服务器(IP地址为202.197.11.5),主机5(在图2-4中网络2的FDDI主干网上)为天勤论坛DNS服务器,该DNS服务器上
设某计算机有四个中断源,优先顺序按1→2→3→4降序排列,若1、2、3、4中断源的服务程序中对应的屏蔽字分别为1110、0100、0110、1111,试写出这四个中断源的中断处理次序(按降序排列)。若四个中断源同时有中断请求,画出CPU执行程序的轨迹。
设有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,请回答:若要加入第5
已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是____。
设算术表达式由字符串b表示,其中可以包括三种括号:圆括号、方括号以及花括号,嵌套的顺序随意,如:“{[()]()}”。试编写算法,实现判定给定表达式中所含括号是否正确配对的出现。
某公司的局域网设置如下所示,两个局域网通过路由器连接到NAT服务器上,并且通过NAT服务器连接到Internel:上。局域网1的掩码是192.168.14.0/25,局域网2的掩码是192.168.14.128/25,NAT服务器的内部IP地址为192.1
某一个计算机系统采用虚拟页式存储管理方式,当前在处理机上执行的某一个进程的页表如下表6—3所列,所有的数字均为十进制,每一项的起始编号是0,并且所有的地址均按字节计址,每页的大小为1024字节。 (1)将下列逻辑地址转换为物理地址,并说明理
若CPU要执行的指令为:MOVR0,R1(即将寄存器R1中的数据传送到寄存器R0中),则CPU首先要完成的操作是()。
某网络中的路由器运行OSPF路由协议,题表是路由器R1维护的主要链路状态信息(LSI),题图是根据题表及R1的接口名构造出来的网络拓扑。请回答下列问题:若Rl增加一条Metric为10的链路连接Internet,则题42表中R1的LSI需要增加哪些
下列关于程序中断方式基本接口的说法中,不正确的是()。
随机试题
如果企业承担社会责任就会以牺牲自己的经济利益为代价。()
PKI的性能中,电子商务通信的关键是
A.liveabetterlifeB.madeupofmorethan50islandsC.HighereducationinstituteD.notbytheParliament,butbythepeop
WhenIwasyoung,Iwasn’tused______whenImadesomemistakes.
药品合格证明和其他标识是指
直接抹灰或直接喷刷式顶棚仅适用于()。
预付款金额为()万元。在进行工程价款动态结算时,价格调整所要考核的地点一般是()。
IG541混合气体灭火剂是由哪些气体按一定比例混合而成的气体?
下列关于职业流行病学调查论述正确的是()。
有三个关系R,S和T如下图所示:则由关系R和S得到关系T的运算是()。
最新回复
(
0
)