首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在 Ⅲ.在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在 Ⅲ.在AOE网中一定只有一条关键路径
admin
2019-12-10
83
问题
以下关于图的说法正确的是( )。
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]不等于O,即图中存在从v
i
到j
j
的一条有向边。由拓扑序列的定义可知,在任意拓扑序列中,v
i
的位置一定在v
j
之前,而上述拓扑序列v
0
,v
1
,v
n-1
中,由于i>j,即v
i
的位置在v
j
之后,导致矛盾。因此说法Ⅱ是正确的。
转载请注明原文地址:https://kaotiyun.com/show/d13i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
现有一个长度为3000B的IP数据报,其IP头部的长度为20B,该IP数据报如在最大帧长度为1518B的以太网中进行传输,那么为了正确传输,需要将其拆分的数据报个数是()。
设需在两台计算机间经两个中间节点传送100M字节的文件,假定:(1)计算机与中间节点间的通信线路以及中间节点间通信线路的通信速率皆为8Kbps;(2)数据传输的差错可以忽略不计;(3)中间节点存储转发时间可忽略不计;
下列排序算法中,时间复杂度为O(nlogn)且占用额外空间最少的是()。
已知有向图G=(V,A),其中V={a,b,c,d,e),A={,,,,,},对该图进行拓扑排序,下面序列中不是拓扑排序的是()。
大部分文件系统以硬盘作为文件存储器。某一个文件系统中,其磁盘物理块的大小为512B,有一个文件,包含了590个逻辑记录,每个记录占255B;其中,为检索方便,采用成组法存储,在每个物理块上只存放2个记录。,文件A在该文件目录中的位置如下图所示。
在连续内存分配管理中,分区分配是最简单的实现并发的内存管理方法。对于该方法,进行内存保护的措施是()。
某二叉树的先序和后序序列正好相反,则该二叉树一定是()。
ICMP协议不具备的功能是()。
某16位计算机中,带符号整数用补码表示,数据Cache和指令cache分离。题44表给出了指令系统中部分指令格式,其中Rs和Rd表示寄存器,mem表示存储单元地址,(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令,各流水段分别是取指(
随机试题
出现冷却系温度过高应先检查冷却液量是否()。
男性,56岁,右上腹不适,食欲不振,消瘦一个月,近半月来尿黄,灰白大便。查体:消瘦病容,巩膜皮肤明显黄染,肝肋下3.0cm,表面光滑,脾未及,触及肿大胆囊,血清总胆红素136μmol/L,直接胆红素90μmol/L,尿胆红素(+),尿胆原(﹣),最可能的诊
患者女,40岁,经行腹痛来诊。腹痛拒按,经色紫红,夹有血块,下血块后痛即缓解,脉象沉涩。治疗宜选用下列哪组穴位( )。
背景资料:某项目经理部承包了南方某运营商的直埋光缆线路工程,工程开工时正逢酷暑天气。项目经理部为了保证工期,在施工过程中坚持全天候作业,致使部分施工人员中暑;部分已挖好的光缆沟在放缆前就被冲塌;部分坡坎保护制作不合格,并被质量监督机构在检查中发现
人民法院对第二审案件的审理,在下列表述中,正确的有()。
(操作员:张主管;账套:101账套;操作日期:2014年1月1日)新增付款方式:付款方式编码:02付款方式名称:转账支票进行票据管理:需要
塔湾金沙是舟山群岛第()大沙滩。
工业和信息化部发布的数据显示,2011年9月份全国电话用户净增1185.6万户,总数达到124073.8万户。其中,同定电话用户减少36.3万户、移动电话用户净增1222万户,创造单月净增用户新纪录。据统计,2011年1~9月全国固定电话用户减少
耐受力
(12年)证明:(-1<χ<1).
最新回复
(
0
)