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

admin2012-06-26 64

问题以下关于图的说法正确的是( )。．
I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧
Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在
Ⅲ在．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的位置一定在v_j之前，而上述拓扑序列v₀，v₁，…，v_n-1中，由于i>j，即v_i的位置在v_j之后，导致矛盾。因此说法Ⅱ是正确的。

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

西藏自治区的设立时间是()。

明治维新中，事实上废除了封建领主土地所有制的举措是()。

中国境内已发现的猿人化石不包括()。

简述戴高乐独立自主外交政策产生的背景、内容和意义。

在美国独立过程中，极力地宣传美国国家独立思想的民主主义者是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

抗日战争期间，日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理，而名义是()

1916年研究短波无线电通信，为现代远距离无线电通信奠定了基础的发明家是()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

痛风病的病因是由于

A、中极B、天枢C、中脘D、膻中E、关元位于前正中线上，脐下4寸的腧穴是

下列疾病，可见板状腹的是()

(2008)供暖地区宿舍建筑的供暖系统设计，以下哪一项不正确?

修筑土坝过程中，当施工期较长，而洪水来临前又不能完建时，导流时段就要以()为标准。

下列关于水闸止水设置的说法，正确的是()。

企业的财务风险主要体现在()。

我国著名药学家屠呦呦获得诺贝尔医学奖，这源于她在创制新型抗疟疾药()的突出贡献。

设某存储器总线的工作频率为100MHz，数据宽度为16位，每个总线周期传输2次，其带宽为【59】MB／s，1分钟可传输【60】MB数据。

A.rootB.controlC.subjectsD.howeverE.realityF.sharpG.intenseH.measureI.expressJ.impulsiveK.pessimist

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

计算机408

学硕统考专业

西藏自治区的设立时间是()。

明治维新中，事实上废除了封建领主土地所有制的举措是()。

中国境内已发现的猿人化石不包括()。

简述戴高乐独立自主外交政策产生的背景、内容和意义。

在美国独立过程中，极力地宣传美国国家独立思想的民主主义者是()。

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

抗日战争期间，日本将沦陷区的许多矿产业、钢铁业等交给日本公司管理，而名义是()

1916年研究短波无线电通信，为现代远距离无线电通信奠定了基础的发明家是()。

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

痛风病的病因是由于

A、中极B、天枢C、中脘D、膻中E、关元位于前正中线上，脐下4寸的腧穴是

下列疾病，可见板状腹的是()

(2008)供暖地区宿舍建筑的供暖系统设计，以下哪一项不正确?

修筑土坝过程中，当施工期较长，而洪水来临前又不能完建时，导流时段就要以()为标准。

下列关于水闸止水设置的说法，正确的是()。

企业的财务风险主要体现在()。

我国著名药学家屠呦呦获得诺贝尔医学奖，这源于她在创制新型抗疟疾药()的突出贡献。

设某存储器总线的工作频率为100MHz，数据宽度为16位，每个总线周期传输2次，其带宽为【59】MB／s，1分钟可传输【60】MB数据。

A.rootB.controlC.subjectsD.howeverE.realityF.sharpG.intenseH.measureI.expressJ.impulsiveK.pessimist

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