首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
以下关于图的说法正确的是( )。 I在一个有向图的拓扑序列中，若顶点a在顶点b：之前，则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0，则该图的拓扑序列必定存在 Ⅲ 在AOE网中一定只有一条关键路径
以下关于图的说法正确的是( )。 I在一个有向图的拓扑序列中，若顶点a在顶点b：之前，则图中必有一条弧 Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为0，则该图的拓扑序列必定存在 Ⅲ 在AOE网中一定只有一条关键路径
admin
2021-08-17
40
问题
以下关于图的说法正确的是( )。
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
学硕统考专业
相关试题推荐
假定某采用页式虚拟存储管理的计算机系统中，主存储器容量为1GB，被分为262144块物理块，物理块号为0，1，2，…，262143。某进程的地址空间占4页，逻辑页号为0，1，2，3，被分配到主存储器的第20，45，101，58号物理块中。回答：
一个32位的计算机系统中，虚拟存储系统采用了物理地址扩展的三级分页方式，第一级页表占用地址的最高2位，第二、三级页表依次占用9位地址，最低12位用于页内偏移量，如图2—3所示。一个进程的地址空间为4GB，每个页表项占用8个字节，请问：(1)一个
假定某计算机的CPU主频为80MHz，CPI为4，并且平均每条指令访存1．5次，主存与cache之间交换的块大小为16B，Caehe的命中率为99％，存储器总线宽度为32位。请回答下列问题。该计算机的MIPS数是多少?平均每秒Cache缺失的次数是多少
假定站点A和B在同一个10Mbit／s以太网的网段上，这两个站点之间的传播时延为225bit时间。现假定A开始发送一帧，并且在A发送结束之前B也发送一帧。如果A发送的是以太网所允许的最短的帧，试问：在(1)中的站点A和B在t=0时同时发送了数据帧。当t
在一个分页存储管理系统中，地址空间分页(每页1K)，物理空间分块，设主存总容量是256KB，描述主存分配情况的位示图如图6-4所示(0表示未分配，1表示已分配)，此时，作业调度程序选中一个长为5．2K的作业投入内存。试回答以下问题：为该作业分配内存后
设表7-2为路由器R的不完整的路由表(其中下一跳给出的是路由器的端口)。路由器R收到下述分别发往6个目的主机的数据报。H1：20．134．245．78H2：166．111．64．129H3：166．111．35．72
假设一个主频为1GHz、CPI为5的CPU需要从某个成块传送的I／O设备读取1000B的数据到主存缓冲区中，该I／O设备一旦启动即按50KB／s的数据传输率向主机传送1000B数据，每个字节的读取、处理并存入内存缓冲区需要1000个时钟周期，则以下4种
一个有50个路由器的网络，采用基于距离一向量的路由选择算法，路由表的每个表项长度为6B，每个路由器都有3个邻接路由器，每秒与每个邻接路由器交换1次路由表，则每条链路上由于路由器更新路由信息而耗费的带宽为()。
设有一个二维数组A[m][n]在存储中按行优先存放(数组的每一个元素占一个窄间)，假设A[0][0]存放位置在780(10)，A[4][6]存放位置在1146(10)，则A[6][20]存放在()位置(其中(10)、表明用十进制数表示)。
设有一个由正整数组成的无序(后向)单链表，编写能够完成下列功能的算法：(1)找出最小值结点，且打印该数值。(2)若该数值为奇数，则将其与直接后继结点的数值交换。(3)若该数值为偶数，则将其直接后继结点删除。
随机试题
A．益母草B．淫羊藿C．花茵陈D．肉苁蓉E．广金钱草茎呈扁圆柱形，表面淡紫色或紫色，有纵条纹的药材是
可以提高焊接电弧稳定性的方法是()。
丙烯氧化生产丙烯酸中，原料丙烯投料量为600kg／h，出料中有丙烯醛640kg／h，另有未反应的丙烯25kg／h，原料丙烯的选择性为()。
在Windows中，双击一个文本文档，系统默认启动的是____________应用程序。
通常，在微机中标明的P4或奔腾4是指()。
李某若提起侵权诉讼，应将()作为被告起诉。关于张某的钱包丢失，正确的说法是()。
在航空运输中，承运人对各种资料或单证是否正确或完备没有检查的义务。
结构化分析采用结构化语言、【】、判定树这3种半形式化的方法编写加工说明。
A、Therearemanygrammarmistakes.B、Ithasexceededthewordlimit.C、Thethesisisn’teffectiveenough.D、Itisbuiltonweek
Obama’sSuccessIsn’tAllGoodNewsforBlackAmericansA)AsErinWhitewatchedtheelectionresultsheadtowardsvictoryfor
最新回复
(
0
)
