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

admin2019-12-10 112

问题以下关于图的说法正确的是( )。
  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]不等于O，即图中存在从v_i到j_j的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，v_i的位置一定在v_j之前，而上述拓扑序列v₀，v₁，v_n-1中，由于i＞j，即v_i的位置在v_j之后，导致矛盾。因此说法Ⅱ是正确的。

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

我们知道，有些CPU指令只能授权给操作系统内核运行，不允许普通用户程序使用，但是，以下操作中，()可以不必具有此种特权。

指令系统中设置多种不同的寻址方式，可以()。

由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)是()。

某路由器的IP地址是125．45．23．12，它在以太网上的物理地址为2345AB4F67CD，它收到了一个分组，分组中的目的IP地址是125．11．78．10。(1)试给出这个路由器发出的ARP请求分组中的各项目。假定不划分子网。

操作系统为了管理文件，设计了文件控制块(FCB)，文件控制块的建立是()。

在补码表示的机器中，若寄存器A中原存的数为9EH，现存的数为CFH，则表明执行的一条指令是()。

TCP是采用()来控制流量的。

关于B一树，下列说法不正确的是()。

以下给出UNIXshell的两条命令行：I．1s>outputtxt&wcoutput．txt&Ⅱ．Ls｜wc命令行I与命令行Ⅱ的主要差别在于()。

社会主义改造完成后，我国社会主义社会的基本矛盾是（）

电焊作业人直接接触的带电体包括________等。

邓小平完整提出"三个有利于"标准的时间是（）。

下列有关行政机关申请法院强制执行的说法正确的有：()

种植乔木的分车绿带宽度不得小于()。

已知某砖混结构建筑物体积为900m3，其中毛石带型基础的工程量为110m3。假定1m3毛石基础需要用砌石工20.66个工日，且在该项单位工程中没有其他工程需要砌石工，则1000m3建筑物需要用砌石工为()个工日。

Somepeoplethinkoflifeasagame.Therearesimilaritiesbetweenlifeandgames;bothcanbeplayed,bothhaverules,andbot

SavingthejuniperplantBackgroundJuniperwasoneofthefirstplantstocoloniseBritainafterthelast【31】________Itssmo