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

admin2019-12-10 83

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

学硕统考专业

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

设需在两台计算机间经两个中间节点传送100M字节的文件，假定：(1)计算机与中间节点间的通信线路以及中间节点间通信线路的通信速率皆为8Kbps；(2)数据传输的差错可以忽略不计；(3)中间节点存储转发时间可忽略不计；

下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。

已知有向图G=(V，A)，其中V={a，b，c，d，e)，A={，，，，，}，对该图进行拓扑排序，下面序列中不是拓扑排序的是()。

在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是()。

某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

ICMP协议不具备的功能是()。

出现冷却系温度过高应先检查冷却液量是否()。

患者女，40岁，经行腹痛来诊。腹痛拒按，经色紫红，夹有血块，下血块后痛即缓解，脉象沉涩。治疗宜选用下列哪组穴位（　　）。

人民法院对第二审案件的审理，在下列表述中，正确的有()。

(操作员：张主管；账套：101账套；操作日期：2014年1月1日)新增付款方式：付款方式编码：02付款方式名称：转账支票进行票据管理：需要

塔湾金沙是舟山群岛第()大沙滩。

耐受力

(12年)证明：(－1＜χ＜1)．

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

计算机408

学硕统考专业

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

设需在两台计算机间经两个中间节点传送100M字节的文件，假定：(1)计算机与中间节点间的通信线路以及中间节点间通信线路的通信速率皆为8Kbps；(2)数据传输的差错可以忽略不计；(3)中间节点存储转发时间可忽略不计；

下列排序算法中，时间复杂度为O(nlogn)且占用额外空间最少的是()。

已知有向图G=(V，A)，其中V={a，b，c，d，e)，A={，，，，，}，对该图进行拓扑排序，下面序列中不是拓扑排序的是()。

在连续内存分配管理中，分区分配是最简单的实现并发的内存管理方法。对于该方法，进行内存保护的措施是()。

某二叉树的先序和后序序列正好相反，则该二叉树一定是()。

ICMP协议不具备的功能是()。

出现冷却系温度过高应先检查冷却液量是否()。

患者女，40岁，经行腹痛来诊。腹痛拒按，经色紫红，夹有血块，下血块后痛即缓解，脉象沉涩。治疗宜选用下列哪组穴位（ ）。

人民法院对第二审案件的审理，在下列表述中，正确的有()。

(操作员：张主管；账套：101账套；操作日期：2014年1月1日)新增付款方式：付款方式编码：02付款方式名称：转账支票进行票据管理：需要

塔湾金沙是舟山群岛第()大沙滩。

耐受力

(12年)证明：(－1＜χ＜1)．

患者女，40岁，经行腹痛来诊。腹痛拒按，经色紫红，夹有血块，下血块后痛即缓解，脉象沉涩。治疗宜选用下列哪组穴位（　　）。