首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ.深度优先遍历 Ⅱ.求最短路径 Ⅲ.拓扑排序 Ⅳ.求关键路径
以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ.深度优先遍历 Ⅱ.求最短路径 Ⅲ.拓扑排序 Ⅳ.求关键路径
admin
2019-05-10
43
问题
以下哪些方法可以判断出一个有向图是否有环( )。
Ⅰ.深度优先遍历 Ⅱ.求最短路径 Ⅲ.拓扑排序 Ⅳ.求关键路径
选项
A、仅Ⅰ、Ⅲ
B、仅Ⅰ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅱ、Ⅲ
D、Ⅰ、Ⅱ、Ⅲ和Ⅳ
答案
A
解析
有两种方法可以判断有向图中是否有回路。用深度优先遍历的方法,如果从有向图上某个顶点v出发的遍历,在dfs(v)结束之前出现一条从顶点j~v的边,由于j在生成树上是v的子孙,则图中必定存在包含v和j的环,因此Ⅰ可以;用拓扑排序的方法,在拓扑排序过程中,每次要删去一个没有前驱的顶点,如果最后图中所有顶点都被删除,则表示没有环,否则有环,因此Ⅲ正确。而最短路径和关键路径(建立在无环的AOE网的基础之上)都是不可以判断的。
补充:还有一个出题点是间接出题,即若一个有向图中的顶点不能排成一个拓扑序列,则断定该有向图一定有什么?想必90%以上的考生都会选择有环,但是没有环这个选项,只有顶点数目大于l的强连通分量这个选项,此时考生必须知道顶点数目大于1的强连通分量就表明有环。
转载请注明原文地址:https://jikaoti.com/ti/kHGjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读以下史料,并回答问题:乾称父,坤称母;予兹藐焉,乃混然中处。故天地之塞,吾其体;天地之帅,吾其性。民,吾同胞;物,吾与也。大君者,吾父母宗子;其大臣,宗子之家相也。尊高年,所以长其长;慈孤弱,所以幼其幼;圣,其合德;贤,其秀也。凡天下疲癃、残疾、惸
“二战”后世界经济发展变化迅速,这种变化主要表现在()。①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美、苏“冷战”为特征的两极格局④科学技术推动生产力发展更为迅速
二次大战后,主要资本主义国家经历了增长时期,首先开始这个进程的国家是()。
简述三十年战争的过程及其结果。
1936年,张学良和杨虎城发动的西安事变()。①是一次具有爱国意义的兵变②民族矛盾激化的结果③检验了中国社会各阶级的抗日态度④促成了抗日民族统一战线初步形成
隋唐五代时期是中国古代商品经济发展史上的一个重要阶段,种类多,交换规模大,交换方式多。试回答问题:下列关于隋唐钱币的表述,不正确的是()
一个在以太网中的主机试图发送一个帧,当它尝试了16次仍然失败之后,它应该()。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
将要相互通信双方怎样进行建立TCP连接?在TCP报文段的首部中只有端口号而没有IP地址,当TCP将其报文段交给IP层时,IP协议怎样知道目的IP地址呢?为什么把IP地址又称为“虚拟地址”,把TCP连接说成是“虚连接”?假设在建立连接时使用2次握手而非3次握
随机试题
七巧板可以阐明若干重要的()
蚤类生活习性与传播疾病没有关系的是
下列常见的前上纵隔肿瘤是
下列不是物权特征的有()。
组织规划包括()。
根据《水电工程设计概算编制规定》(2007年版),施工管理费属于()。
下列哪些属于申请设立专利代理机构应当提交的材料?
下列书法家中不属于河南籍的是()。
开辟中国特色社会主义新道路、开创中国特色社会主义新理论的宣言书是()
(2005年)设α1,α2,α3均为3维列向量,记矩阵A=(α1,α2,α3),B=(α1+α2+α3,α1+2α2+4α3,α1+3α2+9α3).如果|A|=1,那么|B|=_______.
最新回复
(
0
)