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

admin2021-08-17 33

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

转载请注明原文地址:https://kaotiyun.com/show/qW3i777K

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

计算机408
学硕统考专业

相关试题推荐

随机试题

最新回复(0)

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

计算机408

学硕统考专业

某计算机采用虚拟页式存储技术，系统为每一个进程提供65536B的地址空间，页面大小为4096B，某一个进程的代码段有32768B，数据段16396B，堆栈段在进程创建时为1024B，运行中最大会增长到15284B。那么，对这个进程正确的描述是()。

一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中零元素的个数是()。

某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有

某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：cobegin参观者进程i：{进门；参观；出门；}coend请添加必要的信号量和P、V(或wait()、signal())操作，以实现

下列关于银行家算法的叙述中，正确的是

若x是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是

CPU的CPI与下列哪个因素有关?()Ⅰ．时钟频率Ⅱ．系统结构Ⅲ．指令集

下列关于无向图的说法中，正确的是()。Ⅰ．无向图中某个顶点的度是指图中与该顶点连通的顶点数Ⅱ．在一个具有n个顶点的无向图中，要连通全部顶点至少需要n一1条边Ⅲ．无向图的邻接矩阵是对称矩阵Ⅳ．具有n个顶点的无向

某单位有1个总部和6个分部，各个部门都有自己的局域网。该单位申请了6个C类IP地址202．115．10．0／24～202．115．15．0／24，其中总部与分部4共用一个C类地址。网络采用R1～R7共7台路由器，采用动态路由协议OSPF，并划分了3个OSP

文件系统中，文件访问控制信息存储的合理位置是()。

34岁，女性，入院2小时，左手中指掌指关节处掌面被锐器刺伤，宽3cm，查体发现中指呈伸直位，感觉障碍，手指苍白发凉，Allen试验阳性。该患者诊断考虑为

A．SSDB．SADC．SDDD．STDE．SDA源皮距的英文缩写

无论阴虚或阳虚，多在损及哪脏时才容易发生阴阳互损

一男婴，体重7．5kg，身长66cm，头围44cm左腕骨骨化中心2个。此婴儿可能的月龄是

艾宾浩斯遗忘曲线说明遗忘的规律是_______________。

田和被列为诸侯是在公元前()年。

在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，______的作业将得到优先调度；当各个作业要求运行的时间相同时，等待时间长的作业得到优先调度。

Whatisprobablytheman’sposition?