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

admin2021-08-17 71

问题以下关于图的说法正确的是( )。
  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

学硕统考专业

某字长为8位的计算机中，已知整型变量x、y的机器数分别为[x]补=10000100，[y]补=10110000。若整型变量z=2×x+y／2，则z的机器数为

在系统总线中，地址总线的位数()。

在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：语句“movr2,4+(sp)”的功能是什么?

下列不属于DMA控制器的是()。

下列给出的指令系统特点中，有利于实现指令流水线的是____。I．指令格式规整且长度一致Ⅱ．指令和数据按边界对齐存放Ⅲ．只有Load／Store指令才能对操作数进行存储访问

硬盘平均寻道时间为12ms，传输速率为10MB／s，磁盘控制器延时为2ms，则一个转速为7200r／min的硬盘写1KB数据时间为()。

先生不羞，乃有意欲为收责于薛乎？

患者，女性，30岁。主动脉瓣关闭不全。左室扩大，快速走路或上二楼时感心慌气短，超声心动图示左室射血分数40％。该患者的心功能处于

环境影响评价要求实行环境与经济协调发展的政策，其协调发展的主要含义包括()。

城建税按纳税人所在地的不同，设置了三档地区差别比例税率，其中，市区、县城的分别为(　　)。

讲述是教师主要的教学手段，一般可以分_____三个阶段进行。【】

【2016年福建】根据《中华人民共和国教师法》，下列属于教师义务的是()。

小张在M公司担任程序员，他执行本公司工作任务，独立完成了某应用程序的开发和设计，那么该应用程序的软件著作权应当归属______享有。

Thenatureofsleepandtheroleitplaysinourliveshaslongfascinatedscienceandbeenthefocusofmanystudiesandagrea

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

计算机408

学硕统考专业

某字长为8位的计算机中，已知整型变量x、y的机器数分别为[x]补=10000100，[y]补=10110000。若整型变量z=2×x+y／2，则z的机器数为

在系统总线中，地址总线的位数()。

在一个段式存储管理系统中，逻辑地址为32位，其中高16位为段号，低16位为段内偏移，以下是段表(其中的数据均为十六进制，如表7-1所示)。以下是代码段的内容：试问：语句“movr2,4+(sp)”的功能是什么?

下列不属于DMA控制器的是()。

下列给出的指令系统特点中，有利于实现指令流水线的是____。I．指令格式规整且长度一致Ⅱ．指令和数据按边界对齐存放Ⅲ．只有Load／Store指令才能对操作数进行存储访问

硬盘平均寻道时间为12ms，传输速率为10MB／s，磁盘控制器延时为2ms，则一个转速为7200r／min的硬盘写1KB数据时间为()。

先生不羞，乃有意欲为收责于薛乎？

患者，女性，30岁。主动脉瓣关闭不全。左室扩大，快速走路或上二楼时感心慌气短，超声心动图示左室射血分数40％。该患者的心功能处于

环境影响评价要求实行环境与经济协调发展的政策，其协调发展的主要含义包括()。

城建税按纳税人所在地的不同，设置了三档地区差别比例税率，其中，市区、县城的分别为( )。

讲述是教师主要的教学手段，一般可以分_____三个阶段进行。【】

【2016年福建】根据《中华人民共和国教师法》，下列属于教师义务的是()。

小张在M公司担任程序员，他执行本公司工作任务，独立完成了某应用程序的开发和设计，那么该应用程序的软件著作权应当归属______享有。

Thenatureofsleepandtheroleitplaysinourliveshaslongfascinatedscienceandbeenthefocusofmanystudiesandagrea

城建税按纳税人所在地的不同，设置了三档地区差别比例税率，其中，市区、县城的分别为(　　)。