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

admin2012-06-26 108

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

学硕统考专业

下列古希腊哲学家中，唯物主义的代表人物是()。

在半殖民地半封建社会条件下，由于经济地位决定了在政治上带有两重性的阶级是()。

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

1911年，美国工程师()出版《科学管理原理》一书，奠定了科学管理的理论基础，被誉为“科学管理之父”。

下列不是战国时代魏国李悝变法的内容的是()

汉灵帝中平元年(184)，()在7州28郡同时俱起，这是中国历史上第一次组织、准备比较严密的农民起义。

国民政府统治确立后，中国社会仍存在革命条件并成为唯一选择的主要原因是()。

以下选项不属于希腊城邦的形成方式和途径的是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

A．痿软舌B．齿痕舌C．胖大舌D．肿胀舌热邪挟酒毒上壅可见

法律适用是指国家司法机关及其工作人员依照法定职权和程序运用法律处理案件的专门活动。这里的司法机关是指

关于急性肾损伤少尿期的叙述，不正确的是

血涂片计数100个白细胞见25个有核红细胞；如白细胞计数校正前为10×109／L，则校正后应为

依据《招标投标法》的规定，下列说法符合法律规定的是：

对外提供属于国家秘密的测绘成果，应当按照()规定的审批程序，报国务院测绘行政主管部门或者省、自治区、直辖市人民政府测绘行政主管部门。

阳极保护的主要参数有()。

投资人可随时向基金管理人要求赎回的、没有存续期限的是(　　)。

指出下列会计事项对有关指标的影响。假设原来的流动比率为1。增加用“+”表示，减少用“一”表示，没有影响用“0”表示。

2007年1-9月浙江省累计出口()以下的三种说法中，正确的一共有()Ⅰ．2008年1-9月服装、皮革、家具、通信设备行业增加值与去年同期相比下降了Ⅱ．2007年1-9月美资实际到位少于3.4亿美元Ⅲ．2008年

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

计算机408

学硕统考专业

下列古希腊哲学家中，唯物主义的代表人物是()。

在半殖民地半封建社会条件下，由于经济地位决定了在政治上带有两重性的阶级是()。

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

1911年，美国工程师()出版《科学管理原理》一书，奠定了科学管理的理论基础，被誉为“科学管理之父”。

下列不是战国时代魏国李悝变法的内容的是()

汉灵帝中平元年(184)，()在7州28郡同时俱起，这是中国历史上第一次组织、准备比较严密的农民起义。

国民政府统治确立后，中国社会仍存在革命条件并成为唯一选择的主要原因是()。

以下选项不属于希腊城邦的形成方式和途径的是()。

采用散列函数H(k)=3×kMOD13并用线性探测开放地址法处理冲突，在数列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51；(1)构造散列表(画示意图)；(2)装填因子；(3)等概

A．痿软舌B．齿痕舌C．胖大舌D．肿胀舌热邪挟酒毒上壅可见

法律适用是指国家司法机关及其工作人员依照法定职权和程序运用法律处理案件的专门活动。这里的司法机关是指

关于急性肾损伤少尿期的叙述，不正确的是

血涂片计数100个白细胞见25个有核红细胞；如白细胞计数校正前为10×109／L，则校正后应为

依据《招标投标法》的规定，下列说法符合法律规定的是：

对外提供属于国家秘密的测绘成果，应当按照()规定的审批程序，报国务院测绘行政主管部门或者省、自治区、直辖市人民政府测绘行政主管部门。

阳极保护的主要参数有()。

投资人可随时向基金管理人要求赎回的、没有存续期限的是( )。

指出下列会计事项对有关指标的影响。假设原来的流动比率为1。增加用“+”表示，减少用“一”表示，没有影响用“0”表示。

2007年1-9月浙江省累计出口()以下的三种说法中，正确的一共有()Ⅰ．2008年1-9月服装、皮革、家具、通信设备行业增加值与去年同期相比下降了Ⅱ．2007年1-9月美资实际到位少于3.4亿美元Ⅲ．2008年

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

投资人可随时向基金管理人要求赎回的、没有存续期限的是(　　)。