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

admin2019-12-10 26

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

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

答案D

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

编写判定给定的二叉树是否是二叉排序树的函数。

关于哈夫曼树，下列说法正确的是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

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

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

在下列排序方法中不需要对排序码进行比较就能进行排序的是()。

分页存储管理中，页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间)，会给页表的设计带来什么样的新问题?请给出一种解决方法，分析它的优点和缺点。

某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45纳秒，主存的存取周期为200纳秒。已知在一段给定的时间内，CPU共访问内存4500次，其中340次访问主存。问：(1)Cache的命中率是多少?(2)CPU访问内存的平均

A．面色深浓B．面色浊暗C．面色枯槁D．病色结聚而深滞(2007年第80，81题)“望色十法中的“夭是指()

《盐铁论》采用的是【】

小便失禁2年余，伴腰膝酸软无力，神疲乏力，舌淡苔白，最宜诊断为

正常分娩出血量一般

蟾酥内服的用量为

施工单位应当在施了现场各种出入口、洞口、施工起重机械、临时用电设施、脚手架、基坑边沿、爆破物及有害危险气体和液体存放等处危险部位，设置明显的安全警示标志。安全警示标志必须符合(　　)。

()不是反映信贷资产质量的指标。

ReadthefollowingtextcarefullyandthentranslatetheunderlinessegmentsintoChinese.Yourtranslationshouldbewrittencl

计算机408

学硕统考专业

编写判定给定的二叉树是否是二叉排序树的函数。

关于哈夫曼树，下列说法正确的是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

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

某计算机的Cache共有16块，采用2路组相联映射方式(即每组2块)。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是()。

若有4个进程共享同一程序段，每次允许3个进程进入该程序段，用P、V操作作为同步机制，则信号量S的取值范围是()。

在下列排序方法中不需要对排序码进行比较就能进行排序的是()。

分页存储管理中，页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间)，会给页表的设计带来什么样的新问题?请给出一种解决方法，分析它的优点和缺点。

某计算机系统的内存储器由Cache和主存构成，Cache的存取周期为45纳秒，主存的存取周期为200纳秒。已知在一段给定的时间内，CPU共访问内存4500次，其中340次访问主存。问：(1)Cache的命中率是多少?(2)CPU访问内存的平均

A．面色深浓B．面色浊暗C．面色枯槁D．病色结聚而深滞(2007年第80，81题)“望色十法中的“夭是指()

《盐铁论》采用的是【】

小便失禁2年余，伴腰膝酸软无力，神疲乏力，舌淡苔白，最宜诊断为

正常分娩出血量一般

蟾酥内服的用量为

施工单位应当在施了现场各种出入口、洞口、施工起重机械、临时用电设施、脚手架、基坑边沿、爆破物及有害危险气体和液体存放等处危险部位，设置明显的安全警示标志。安全警示标志必须符合( )。

()不是反映信贷资产质量的指标。

ReadthefollowingtextcarefullyandthentranslatetheunderlinessegmentsintoChinese.Yourtranslationshouldbewrittencl

施工单位应当在施了现场各种出入口、洞口、施工起重机械、临时用电设施、脚手架、基坑边沿、爆破物及有害危险气体和液体存放等处危险部位，设置明显的安全警示标志。安全警示标志必须符合(　　)。