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

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

admin2014-04-17  60
问题 以下有关拓扑排序的说法中，错误的是(    )。
Ⅰ．如果某有向图存在环路，则该有向图一定不存在拓扑排序
Ⅱ．在拓扑排序算法中，既可以使用栈，也可以使用队列
Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1
选项 A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ
答案D
解析 Ⅰ：如果一个有向图存在环路，则该有向图肯定不会存在拓扑排序，这是因为该环路找不到入度为0的结点，拓扑排序自然也就进行不下去了，故Ⅰ正确。
    Ⅱ：使用栈来表示拓扑排序的序列，最后的出栈序列是逆拓扑排序，只需逆转过来即可，只是效率比较低；使用队列时，出队序列就是拓扑排序序列，故使用栈和队列都是可以的，只是效率不等而已，故Ⅱ正确。
    Ⅲ：一个反例如图8—9所示。该有向图的拓扑有序序列是唯一的，但各个顶点的入度和出度可以超出1，故Ⅲ错误。
转载请注明原文地址:https://www.kaotiyun.com/show/oixi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)