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

admin2019-12-10 35

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

转载请注明原文地址:https://jikaoti.com/ti/sqDjFFFM

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

计算机系统总线包括①地址总线、②数据总线和③控制总线。若采用DMA方式传送数据，需要DMA控制器控制的是()。

采用段式存储管理时，一个程序分段的时机是()。

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是____。

TCP是采用()来控制流量的。

E-mail中的存取协议IMAP与POP3协议的差别包括()。

交往动机

钢中含碳量的变化对力学性能有什么影响?

美国管理学家卡茨(RobertL．katz)认为，一个管理者至少拥有的三大基本技能是技术技能、概念技能和______。

面色赤与下列哪项病证有关

A、卡比多巴B、苯海索C、左旋多巴D、溴隐亭E、维生素B6青光眼、前列腺肥大者慎用

湖泊简化时，下列说法正确的是()。

预测性财务信息的审核不属于注册会计师的审计业务。（）

公安机关要建立()，通过治安信息的收集与分析，不断提高对治安危害的预见性，加强超前控制。

某次考试共有9题，做对第1～9题的人数分别占到参加考试总人数的82％、65％、92％、93％、68％、98％、70％、60％、72％，如果做对5道或5道以上为及格，则这次考试的及格率至少为：