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

admin2012-06-26 74

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

学硕统考专业

下列属于明太祖采取的措施的是()。

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

西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()

京军三大营的成分不包括()。

美国首次提出争夺世界霸权的纲领性文件是()。

下列各项不是“南北议和”形成的原因的是()。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

心脏性猝死最主要的病因是

下列中最常见的卵巢生殖细胞肿瘤是

患者面色萎黄，纳呆脘痞，肢倦乏力，稍进油腻之物则大便次数增多而溏稀，舌淡，脉细弱。治疗最佳选方是

预应力可使混凝土构件在使用荷载作用下不致开裂或推迟开裂，或者使裂缝宽度减小。()

已知椭圆=1(a＞b＞0)上有一个顶点到两个焦点之间的距离分别为．如果直线x=t(t∈R)与椭圆相交于A，B，若C(一3，0)，D(3，0)，证明直线CA与直线BD的交点K必在一条确定的双曲线上；

四元方程组的一个基础解系是_________．

在FTP协议中，控制连接是由(66)主动建立的。

设工程文件包含两个窗体文件Form1．frm、Form2．frm及一个标准模块文件Modulel．bas。两个窗体上分别只有一个名称为Commanl的命令按钮。Forml的代码如下：Form2的代码如下：Public

A、Interviews.B、Televisionads.C、Playingwithchildren.D、Speeches.C信息明示题。男士指出，想要成为政党候选人就要筹集资金、获得政党成员的支持、发表演讲、与社区领导会面、参加辩论等。而在

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

计算机408

学硕统考专业

下列属于明太祖采取的措施的是()。

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

西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()

京军三大营的成分不包括()。

美国首次提出争夺世界霸权的纲领性文件是()。

下列各项不是“南北议和”形成的原因的是()。

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

古埃及第24朝法老波克利斯进行改革，宣布废除奴隶制，债权人只能索取债务人的财产作抵偿，而不能占有债务人的人身，因为财产属于个人，而公民人身属于国家，国家需要他们服役。该改革旨在

心脏性猝死最主要的病因是

下列中最常见的卵巢生殖细胞肿瘤是

患者面色萎黄，纳呆脘痞，肢倦乏力，稍进油腻之物则大便次数增多而溏稀，舌淡，脉细弱。治疗最佳选方是

预应力可使混凝土构件在使用荷载作用下不致开裂或推迟开裂，或者使裂缝宽度减小。()

已知椭圆=1(a＞b＞0)上有一个顶点到两个焦点之间的距离分别为．如果直线x=t(t∈R)与椭圆相交于A，B，若C(一3，0)，D(3，0)，证明直线CA与直线BD的交点K必在一条确定的双曲线上；

四元方程组的一个基础解系是_________．

在FTP协议中，控制连接是由(66)主动建立的。

设工程文件包含两个窗体文件Form1．frm、Form2．frm及一个标准模块文件Modulel．bas。两个窗体上分别只有一个名称为Commanl的命令按钮。Forml的代码如下：Form2的代码如下：Public

A、Interviews.B、Televisionads.C、Playingwithchildren.D、Speeches.C信息明示题。男士指出，想要成为政党候选人就要筹集资金、获得政党成员的支持、发表演讲、与社区领导会面、参加辩论等。而在

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