首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在 Ⅲ.在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 I.在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧 Ⅱ.若一个有向图的邻接矩阵中对角线以下元素均为0,则该图的拓扑序列必定存在 Ⅲ.在AOE网中一定只有一条关键路径
admin
2019-12-10
114
问题
以下关于图的说法正确的是( )。
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
学硕统考专业
相关试题推荐
下图是三个计算机局域网A,B和C,分别包含10台,8台和5台计算机,通过路由器互联,并通过该路由器接口d联入因特网。路由器各端口名分别为a、b、c和d(假设端口d接入IP地址为61.60.21.80的互联网地址)。LANA和LANB公用一个C类IP地址
42.设有带头结点的循环双链表表示的线性表L=(a1,a2,……,an-1,an)。设计在时间和空间上都尽可能高效的算法,将L改造成L=(a1,a2,……,an,……a4,a2)。要求:(1)给出算法的基本设计思想。(2)根据设计思想,
实现一个经典的“读者一写者”算法时,若当前临界区中有读者访问,写者再来时必须在临界区外面等候,如果其后读者源源不断地到达,按策略他们均可以进入临界区,始终保持临界区中有读者访问,那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题,我们修改访问策略,
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成?请简述原因。
已知有向图G=(V,A),其中V={a,b,c,d,e),A={,,,,,},对该图进行拓扑排序,下面序列中不是拓扑排序的是()。
采用段式存储管理时,一个程序分段的时机是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
当系统发生抖动(thrashing)时,可以采取的有效措施是____。I.撤销部分进程Ⅱ.增加磁盘交换区的容量Ⅲ.提高用户进程的优先级
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为lms。设I/O系统的性能只与磁盘和控制器有关,单磁盘中连续访问
某16位计算机中,带符号整数用补码表示,数据Cache和指令cache分离。题44表给出了指令系统中部分指令格式,其中Rs和Rd表示寄存器,mem表示存储单元地址,(x)表示寄存器x或存储单元x的内容。该计算机采用5段流水方式执行指令,各流水段分别是取指(
随机试题
为保证公正司法,提高司法公信力,让人民群众在每一个司法案件中感受到公平正义,《中共中央关于全面推进依法治国若干重大问题的决定》中提出了相应的要求,以下哪项不包括在内?()
外围血管阻力升高可由于()。
下列哪种说法是错误的?
使用第二手统计数据,必须注意()。
农场中种植着粮食作物、果树,饲养着家禽、家畜等。运用生态系统信息传递的原理,可以有效提高农畜产品的产量。下列措施不属于此项原理的是()。
下列说法正确的是().
教学是学校教育工作的中心,学校教育工作要坚持“以教学为主,全面安排”的原则。()
1,-3,3,3,9,()
事务处理是所有信息系统的基础工作,所以事务处理系统应达到多方面的目标,但是不包括()。
JohnWoodendiedlastFridayattheageofninety-nine.Hewasoneofthegreatesttwentieth-centuryAmericansinsports.Hewas
最新回复
(
0
)