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

admin2021-08-17 67

问题以下关于图的说法正确的是( )。
  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://www.kaotiyun.com/show/qW3i777K

本试题收录于：计算机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)如

二叉树若用顺序方法存储，则下列4种算法中运算时间复杂度最小的是()。

下列介质访问控制方法中，可能发生冲突的是

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；

计算机硬件的五大基本构件包括运算器、存储器、输入设备、输出设备和()。

已知X＝－0．875×21，Y＝0．625×22，设浮点数格式为阶符1位，阶码2位，数符1位，尾数3位，通过补码求出Z—X—Y的二进制浮点数规格化结果是()。

不作为栓剂质量检查的项目是

地图符号按比例尺关系可分为（）。

资产负债表中的“货币资金”项目包括()。

在计算出售自有住房应缴纳的个人所得税时，个人出售现住房后(　　)年内未重新购房的，其所缴纳的纳税保证金不再退还，应全部作为个人所得税缴入国库。

下列关于绿色信贷的表述，正确的有()。

人的健康不仅要有健康的身体还要有()。

因机构改革，某市物价局被该市人民政府撤销，其职权由某市市场监督局行使，现公民甲欲对某市物价局被撤销前行使职权的行为申请国家赔偿，下列判断正确的是()。

陶冶(情感陶冶)【2011年、2012年－华中师大】【2013年－杭州师大／哈尔滨师大】【2014年－安徽师大】

下面的描述中正确的是

下列选项中属于面向对象设计方法主要特征的是()。

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

计算机408

学硕统考专业

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

二叉树若用顺序方法存储，则下列4种算法中运算时间复杂度最小的是()。

下列介质访问控制方法中，可能发生冲突的是

现有一种解决无向连通图的最小生成树的方法：将图中所有边按权重从大到小排序为(e1，e2，…，em)；i=1；while(所剩边数≥顶点数){从图中删去ei；若图不再连通，则恢复ei；i++；

计算机硬件的五大基本构件包括运算器、存储器、输入设备、输出设备和()。

已知X＝－0．875×21，Y＝0．625×22，设浮点数格式为阶符1位，阶码2位，数符1位，尾数3位，通过补码求出Z—X—Y的二进制浮点数规格化结果是()。

不作为栓剂质量检查的项目是

地图符号按比例尺关系可分为（）。

资产负债表中的“货币资金”项目包括()。

在计算出售自有住房应缴纳的个人所得税时，个人出售现住房后( )年内未重新购房的，其所缴纳的纳税保证金不再退还，应全部作为个人所得税缴入国库。

下列关于绿色信贷的表述，正确的有()。

人的健康不仅要有健康的身体还要有()。

因机构改革，某市物价局被该市人民政府撤销，其职权由某市市场监督局行使，现公民甲欲对某市物价局被撤销前行使职权的行为申请国家赔偿，下列判断正确的是()。

陶冶(情感陶冶)【2011年、2012年－华中师大】【2013年－杭州师大／哈尔滨师大】【2014年－安徽师大】

下面的描述中正确的是

下列选项中属于面向对象设计方法主要特征的是()。

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

在计算出售自有住房应缴纳的个人所得税时，个人出售现住房后(　　)年内未重新购房的，其所缴纳的纳税保证金不再退还，应全部作为个人所得税缴入国库。