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

admin2021-08-17 80

问题以下关于图的说法正确的是( )。
  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]不等于0，即图中存在从v_i到v_j的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，v_i的位置一定在vj之前，而上述拓扑序列v₀，v₁…，v_n－1中，由于i>j，即v_i的位置在v_j之后，导致矛盾。因此说法Ⅱ是正确的。

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

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

下列关于二叉树的说法中，正确的是()。

指令流水线将一条指令的执行过程分为四步，其中第1、2和4步的经过时间为△t，如下图5-1所示。若该流水线顺序执行，50条指令共用153At，并且不考虑相关问题，则该流水线的瓶颈第3步的时间是()。

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。题47一a表中的IP分组中，哪几个是由H

下列选项中，不能改善磁盘设备I／0性能的是

假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsigtledshortx=65530：unsignedintv=x；得到y的机器数为

CPU内部一般包括PC、MAR、MDR、IR等几个寄存器及若干通用寄存器。图9—1是指令LADR0，(X)的指令流程图，其功能是将主存X号单元的数据取到R0寄存器中，图中M表示主存。　　(1)请完成该指令流程图中未完成的部分。　　(2

CRT显示器显示图形图像的原理是图形图像()。

患者，女，45岁。患水肿10年，近来小便不通，面色苍白，呕吐清水，面色晦滞，畏寒肢冷，大便正常，舌淡苔白滑，脉沉细。治疗应首选

多数生物的最适温度在

国家鼓励哪些人群率先献血

We　understand　the　goods　can　be　supplied　(　　　　　)stock．

一根绳子用去它的3/5后，还剩3/5米，则()．

你认为如何实现经济又好又快地发展?

已知平面上三条不同直线的方程分别为l1＝aχ＋2by＋3c＝0，l2＝bχ＋2cy＋3a＝0，l3＝cχ＋2ay＋3b＝0，试证这三条直线交于一点的充分必要条件为a＋b＋c＝0．

设随机变量X服从n个自由度的t分布，定义tα满足P{X≤tα}=1—α(0＜α＜1)。若已知P{｜X｜＞x}=b(b＞0)，则x=_______。

Takingchargeofyourselfinvolvesputtingtorestsomeveryprevalentmyths.Atthetopofthelististhenotionthatintellig

MakingandWritingWordsI.AbriefintroductionA.Makingwordsisconceptuallyanengagingandeffectiveinstructionaltask.

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

计算机408

学硕统考专业

下列关于二叉树的说法中，正确的是()。

指令流水线将一条指令的执行过程分为四步，其中第1、2和4步的经过时间为△t，如下图5-1所示。若该流水线顺序执行，50条指令共用153At，并且不考虑相关问题，则该流水线的瓶颈第3步的时间是()。

主机H通过快速以太网连接Internet，IP地址为192．168．0．8，服务器S的lP地址为211．68．71．80。H与S使用TCP通信时，在H捕获的其中5个IP分组如题47一a表所示。请回答下列问题。题47一a表中的IP分组中，哪几个是由H

下列选项中，不能改善磁盘设备I／0性能的是

假定编译器规定int和short类型长度分别为32位和16位，执行下列C语言语句：unsigtledshortx=65530：unsignedintv=x；得到y的机器数为

CPU内部一般包括PC、MAR、MDR、IR等几个寄存器及若干通用寄存器。图9—1是指令LADR0，(X)的指令流程图，其功能是将主存X号单元的数据取到R0寄存器中，图中M表示主存。 (1)请完成该指令流程图中未完成的部分。 (2

CRT显示器显示图形图像的原理是图形图像()。

患者，女，45岁。患水肿10年，近来小便不通，面色苍白，呕吐清水，面色晦滞，畏寒肢冷，大便正常，舌淡苔白滑，脉沉细。治疗应首选

多数生物的最适温度在

国家鼓励哪些人群率先献血

We understand the goods can be supplied ( )stock．

一根绳子用去它的3/5后，还剩3/5米，则()．

你认为如何实现经济又好又快地发展?

已知平面上三条不同直线的方程分别为l1＝aχ＋2by＋3c＝0，l2＝bχ＋2cy＋3a＝0，l3＝cχ＋2ay＋3b＝0，试证这三条直线交于一点的充分必要条件为a＋b＋c＝0．

设随机变量X服从n个自由度的t分布，定义tα满足P{X≤tα}=1—α(0＜α＜1)。若已知P{｜X｜＞x}=b(b＞0)，则x=_______。

Takingchargeofyourselfinvolvesputtingtorestsomeveryprevalentmyths.Atthetopofthelististhenotionthatintellig

MakingandWritingWordsI.AbriefintroductionA.Makingwordsisconceptuallyanengagingandeffectiveinstructionaltask.

CPU内部一般包括PC、MAR、MDR、IR等几个寄存器及若干通用寄存器。图9—1是指令LADR0，(X)的指令流程图，其功能是将主存X号单元的数据取到R0寄存器中，图中M表示主存。　　(1)请完成该指令流程图中未完成的部分。　　(2

We　understand　the　goods　can　be　supplied　(　　　　　)stock．