以下关于图的说法正确的是( )。 I在一个有向图的拓扑序列中，若顶点a在顶点b：之前，则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0，则该图的拓扑序列必定存在 Ⅲ 在AOE网中一定只有一条关键路径

admin2021-08-17 78

问题以下关于图的说法正确的是( )。
  I在一个有向图的拓扑序列中，若顶点a在顶点b：之前，则图中必有一条弧
  Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0，则该图的拓扑序列必定存在
  Ⅲ 在AOE网中一定只有一条关键路径

选项 A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅲ
D、仅有Ⅱ

答案D

解析说法I是错误的，在一个有向图的拓扑序列中，若顶点a在顶点b之前，只能说明顶点a到顶点b有一条路径。
说法Ⅲ是错误的，AOE网中可能有不止一条关键路径，它们的路径长度相同。
说法Ⅱ是正确的。任意n个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v₀，v₁，…，v_n－1，证明此时的邻接矩阵A为上三角矩阵，可用反证法证明。假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j(i>j)，使得A[j]不等于0，即图中存在从v_i到v_j的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，v_i的位置一定在vj之前，而上述拓扑序列v₀，v₁…，v_n－1中，由于i>j，即v_i的位置在v_j之后，导致矛盾。因此说法Ⅱ是正确的。

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

以下关于图的说法正确的是( )。 I在一个有向图的拓扑序列中，若顶点a在顶点b：之前，则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0，则该图的拓扑序列必定存在 Ⅲ 在AOE网中一定只有一条关键路径

计算机408

学硕统考专业

主机A向主机B发送IP分组，途中经过了4个路由器，那么，在IP分组的发送和转发过程中，共使用ARP协议的次数是()。

通道是一种IO设备，它用于传输数据的是()。

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是I．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排序V．二路归并排序

某32位计算机，CPU主频为800MHz，cache命中时的CPI为4，cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns；存储器总线宽度为32位，总线时钟频率为200MHz，支持突发传送总线事务。每次读突发

下列关于银行家算法的叙述中，正确的是

有一结点的关键字序列F={129，72，180，105，147，96，45，69}，散列函数为H(k)=kmod11，其中k为关键字，散列地址空间为0～10。要求：画出相应的散列表。当发生冲突时，以链地址法解决。计算在等概率情况下，查找成功和查找不成功

文件系统中，文件访问控制信息存储的合理位置是()。

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。补码定点小数；

中华文明五千年的历史沉淀给我们留下了无数瑰宝，这不仅是灿烂的中华文化的见证，也是古老的中国献给世界的遗产。下列关于我国的“世界文化遗产”，表述有误的一项是()。

________的通路称为内电路。

内环境包括

A．50g／dB．300mg／dC．4μg／dD．40g／dE．10μg／d低胆固醇饮食胆固醇摄入量应不超过

A．420nmB．550nmC．633nmD．820nmE．950nm感蓝胶片的吸收光谱峰值是

下列不属于肝硬化门静脉高压症表现的是

有些可转换债券在赎回条款中设置不可赎回期，其目的是()。2016年

Jackwouldratherspendtimecomplainingthan______theproblembyhimself.