以下有关拓扑排序的说法中，错误的是( )。 Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序 Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列 Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1

admin2022-06-07 32

问题以下有关拓扑排序的说法中，错误的是( )。
Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序
Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列
Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1

选项 A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ

答案D

解析 Ⅰ：如果一个有向图存在环路，则肯定不会存在拓扑排序，因为该环路找不到入度为0的结点，拓扑排序自然也就进行不下去了，故Ⅰ正确。
Ⅱ:使用栈来表示拓扑排序的序列，最后的出栈序列是逆拓扑排序，只需逆转过来即可，只是效率比较低；使用队列时，出队序列就是拓扑排序序列，故使用栈和队列都是可以的，只是效率不等而已，故Ⅱ正确。
Ⅲ: —个反例如图8—9所示。该图的拓扑有序序列是唯一的，但各个顶点的入度和出度可以超出1，故Ⅲ错误。

转载请注明原文地址:https://jikaoti.com/ti/WzDjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是()。

下列说法中，正确的是()。

下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是____。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1)，C(1)，E(2)E

已知下列各种初始状态(长度为n)元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)?(1)关键字自小到大有序(key1＜key2＜…＜keyn)。(2)关键字自大到小逆序(key1＞key2

下列叙述中，不符合m阶B树定义要求的是_______。

下列关于总线仲裁方式的说法中，不正确的是()。

为了处理参数及返回地址，在递归过程或函数调用时，要用一种称为()的数据结构。

国有独资公司董事会成员为________人。()

正常月经周期中后半期的基础体温较前半期升高________。

脑血管意外最常见的原因是（）

投资效益指标是投资经济活动成效的数量表现，是()项目投入和产出对比关系的工具。

商品化会计核算软件开发经销单位在售出软件后应承担售后服务工作，在下列工作中，()不是软件开发销售商必须提供的。

宪法的地位主要体现在()。

蚂蚁，一种令人生厌的“小生命”，如今以它为原料制成的保健品却()地闯进了市民的保健领域。

下列()属于契约型金融机构。

根据作用的途径，法的价值可以分为()