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

admin2019-12-10 49

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

学硕统考专业

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

UNIX系统中，输入／输出设备看作是()。

现采用调相与调幅相结合的调制方式，载波有四种相位变化和两种振幅变化，调制速率是600波特，那么数据速率是()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

下列哪味药属于孕妇慎用药

企业法律顾问注册有效期为2年，有效期满前()，持证者应当按规定重新办理注册登记。

在对入境人员的检疫查验中，发现患有艾滋病、性病、麻风病、精神病、开放性肺结核的外国人被禁止入境。　　　　(　　)

下列选项中关于杜邦分析法的说法错误的是()。

燕京八绝是指具有“京作”特色的八种工艺门类，它们充分汲取了各地民间工艺的精华，又承袭了宫廷文化的精髓，是北京的艺术典范。下列关于燕京八绝的说法中，正确的是()。

字长是CPU的主要性能指标之一，它表示()。

Thehumanbraincontains10thousandmillioncellsandeachofthemmayhaveathousandconnections.Soenormous【M1】______numb

Urbancongestionwouldgreatlyberelievedifthe________chargedonpublictransportWeremorereasonable.

Itisnecessaryforourcollegestudentsto______toarapidlychangingsociety.

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

计算机408

学硕统考专业

一个字节多路通道连接D1、D2、D3、D4、D5共5台设备，这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求，请回答下列问题：(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字

UNIX系统中，输入／输出设备看作是()。

现采用调相与调幅相结合的调制方式，载波有四种相位变化和两种振幅变化，调制速率是600波特，那么数据速率是()。

描述滑动窗口机制及其作用。比较停止一等待协议，多帧滑动窗口和后退N帧协议，多帧滑动窗口与选择重传协议的区别。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

下列哪味药属于孕妇慎用药

企业法律顾问注册有效期为2年，有效期满前()，持证者应当按规定重新办理注册登记。

在对入境人员的检疫查验中，发现患有艾滋病、性病、麻风病、精神病、开放性肺结核的外国人被禁止入境。 ( )

下列选项中关于杜邦分析法的说法错误的是()。

燕京八绝是指具有“京作”特色的八种工艺门类，它们充分汲取了各地民间工艺的精华，又承袭了宫廷文化的精髓，是北京的艺术典范。下列关于燕京八绝的说法中，正确的是()。

字长是CPU的主要性能指标之一，它表示()。

Thehumanbraincontains10thousandmillioncellsandeachofthemmayhaveathousandconnections.Soenormous【M1】______numb

Urbancongestionwouldgreatlyberelievedifthe________chargedonpublictransportWeremorereasonable.

Itisnecessaryforourcollegestudentsto______toarapidlychangingsociety.

在对入境人员的检疫查验中，发现患有艾滋病、性病、麻风病、精神病、开放性肺结核的外国人被禁止入境。　　　　(　　)