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

admin2021-08-17 42

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

学硕统考专业

下列关于二叉树的说法中，正确的是()。

已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成?请简述原因。

关于以太网交换机，下面的论述中不正确的是()。

某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有

下列说法正确的是()。Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

在安装ExchangeServer2003时，运行ForesPrep并且完成复制之后，必须运行DomainPrep,运行DomainPrep的作用是()。

引起高血钾的肌松药是

关于骨关节结核下列不正确的是

不纳入基本医疗保险用药()。

预收账款是一种典型的商业信用形式，一般用于如下情况的货物销售()。

以下构成跨期套利的是()。

在对存货实施监盘程序时，注册会计师的以下做法中不正确的是()。

在警察的萌芽时期，同时伴生的有(　　)的萌芽。

ItwaslateatnightonOctober10,1939,whenDrBethunewasbusyworkinginafieldhospital.AnEighthRouteArmysoldiercam

WorldTrekisanairlinecompany.

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

计算机408

学硕统考专业

下列关于二叉树的说法中，正确的是()。

已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成?请简述原因。

关于以太网交换机，下面的论述中不正确的是()。

某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有

下列说法正确的是()。Ⅰ．当各边的权值相等时，广度优先遍历算法可用来解决单源最短路径问题Ⅱ．广度优先遍历算法可用来求无向图的所有连通分量Ⅲ．广度优先遍历算法类似于树中的后序遍历算法

在安装ExchangeServer2003时，运行ForesPrep并且完成复制之后，必须运行DomainPrep,运行DomainPrep的作用是()。

引起高血钾的肌松药是

关于骨关节结核下列不正确的是

不纳入基本医疗保险用药()。

预收账款是一种典型的商业信用形式，一般用于如下情况的货物销售()。

以下构成跨期套利的是()。

在对存货实施监盘程序时，注册会计师的以下做法中不正确的是()。

在警察的萌芽时期，同时伴生的有( )的萌芽。

ItwaslateatnightonOctober10,1939,whenDrBethunewasbusyworkinginafieldhospital.AnEighthRouteArmysoldiercam

WorldTrekisanairlinecompany.

在警察的萌芽时期，同时伴生的有(　　)的萌芽。