首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I在一个有向图的拓扑序列中,若顶点a在顶点b:之前,则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0,则该图的拓扑序列必定存在 Ⅲ 在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 I在一个有向图的拓扑序列中,若顶点a在顶点b:之前,则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0,则该图的拓扑序列必定存在 Ⅲ 在AOE网中一定只有一条关键路径
admin
2021-08-17
62
问题
以下关于图的说法正确的是( )。
I在一个有向图的拓扑序列中,若顶点a在顶点b:之前,则图中必有一条弧
Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0,则该图的拓扑序列必定存在
Ⅲ 在AOE网中一定只有一条关键路径
选项
A、I、Ⅱ
B、Ⅱ、Ⅲ
C、I、Ⅲ
D、仅有Ⅱ
答案
D
解析
说法I是错误的,在一个有向图的拓扑序列中,若顶点a在顶点b之前,只能说明顶点a到顶点b有一条路径。
说法Ⅲ是错误的,AOE网中可能有不止一条关键路径,它们的路径长度相同。
说法Ⅱ是正确的。任意n个顶点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v
0
,v
1
,…,v
n-1
,证明此时的邻接矩阵A为上三角矩阵,可用反证法证明。假设此时的邻接矩阵不是上三角矩阵,那么,存在下标i和j(i>j),使得A
[j]不等于0,即图中存在从v
i
到v
j
的一条有向边。由拓扑序列的定义可知,在任意拓扑序列中,v
i
的位置一定在vj之前,而上述拓扑序列v
0
,v
1
…,v
n-1
中,由于i>j,即v
i
的位置在v
j
之后,导致矛盾。因此说法Ⅱ是正确的。
转载请注明原文地址:https://kaotiyun.com/show/qW3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归,且不用栈来完成?请简述原因。
一个含有n个顶点和e条边的简单无向图,在其邻接矩阵存储结构中零元素的个数是()。
若用户1与用户2之间发送和接收电子邮件的过程如下图所示,则图中①、②、③阶段分别使用的应用层协议可以是
某计算机存储器按字节编址,采用小端方式存放数据。假定编译器规定int和shorI型长度分别为32位和16位,并且数据按边界对齐存储。某C语言程序段如下:struct{inta:charb:shOrtc:}record:record.a=273:
若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为
某32位计算机,CPU主频为800MHz,cache命中时的CPI为4,cache块大小为32字节;主存采用8体交叉存储方式,每个体的存储字长为32位、存储周期为40ns;存储器总线宽度为32位,总线时钟频率为200MHz,支持突发传送总线事务。每次读突发
下列说法正确的是()。Ⅰ.当各边的权值相等时,广度优先遍历算法可用来解决单源最短路径问题Ⅱ.广度优先遍历算法可用来求无向图的所有连通分量Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
一个公司有两个部门,研发部和市场部,研发部有29台计算机,市场部有11台计算机。现在,公司申请了一个C类地址212.112.32.0,规划的网络拓扑如图1一5所示。试问:如果路由器R1和R2都采用了路由信息协议(RoutingInformation
设一个一维整数数组中有n(n>1)个元素,设计一个在时间和空间两方面尽可能高效的算法,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求:说明你所设计算法的时间复杂度和空间复杂度。
某自治系统内采用RIP协议,若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量,距离矢量中包含信息,则能得出的结论是____。
随机试题
Youcandoitifyouwantto,butinmyopinionit’snotworththe______itinvolves.
下列哪一项对心瓣膜功能的叙述是错误的()
宫颈活检为鳞癌,正确的诊断是患者进行了放疗,下列哪项治疗目的是正确的
离子交换法适宜分离
下列选项中不属于无效合同的特征的是()
会计的基本职能是( )。
古巴比伦王国的文明表现在()。
在窗体上画两个单选按钮,名称分别为Option1和Option2,标题分别为“黑体”和“楷体”;一个复选框,名称为Check1,标题为“粗体”。要求程序运行时,“黑体”单选按钮和“粗体”复选框被选中,则能够实现上述要求的语句序列是()。
Readtheextractbelowfromtheannualreportofacompanywithmanufacturinginterestsaroundtheworld.Choosethebestwo
differ,experience,inform,little,patience,prefer,quality,rely,limit,tame,familiar,violateThoughbountyhuntin
最新回复
(
0
)