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

admin2019-12-10 28

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

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

答案D

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。(1)原码定点小数；(2)补码定点小数；(3)反码定点小数；(4)IEEE754标准短

在一个双链表中，在p结点之前插入q结点的操作是()。

文件系统的主要目的是()。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

下列关于并行微程序控制器的说法正确的是()。

苏轼的《水调歌头》(明月几时有)是一首

患者，男，24岁。近3年来反复餐后3～4小时上腹痛，持续至下次进餐后才缓解。应首先考虑的是

A．α-CYDB．β-CYDC．γ-CYDD．HP-CYDE．乙基-CYD水溶性最好的环糊精是()。

有下列()合同,当事人可以请求人民法院或者仲裁机构撤销合同。

下列选项中，属于我国沪菜系名菜的是()。

抗生素的发明和使用，使病菌一度不再是人类的致命威胁。但是，在人类使用抗生素治疗疾病的同时，病菌的耐药性也在增加，由于滥用抗生素，出现了目前难以控制的“超级病菌”。上述事实表明()。

做一个平凡的人并不可悲。一个才疏学浅的人如果______，那才是最可悲的。

A．近中沟B．横嵴C．切缘结节D．斜嵴E．轴嵴属于上颌第一磨牙的解剖标志的是()。

某投机者预测10月份大豆期货合约价格将上升，故买入10手(10吨／手)大豆期货合约，成交价格为2030元／吨。可此后价格不升反降，为了补救，该投机者以2015元／吨的价格再次买入5手合约，当市价反弹到()时才可以避免损失。

计算机408

学硕统考专业

假设系统的所有资源是同类型的，系统中的进程每次申请资源数最多1个，那么，下面列出的4种情况中，()可能发生死锁。情况序号系统中进程数资源总量

已知某32位二进制机器数为11000000000000000000000000000000，试计算在下列各种编码方式下其代表的真值。(1)原码定点小数；(2)补码定点小数；(3)反码定点小数；(4)IEEE754标准短

在一个双链表中，在*p结点之前插入*q结点的操作是()。

文件系统的主要目的是()。

序列的“中值记录”指的是：如果将此序列排序后，它是第n／2个记录。试写出一个求中值记录的算法。

现有一个长度为3000B的IP数据报，其IP头部的长度为20B，该IP数据报如在最大帧长度为1518B的以太网中进行传输，那么为了正确传输，需要将其拆分的数据报个数是()。

下列关于并行微程序控制器的说法正确的是()。

苏轼的《水调歌头》(明月几时有)是一首

患者，男，24岁。近3年来反复餐后3～4小时上腹痛，持续至下次进餐后才缓解。应首先考虑的是

A．α-CYDB．β-CYDC．γ-CYDD．HP-CYDE．乙基-CYD水溶性最好的环糊精是()。

有下列()合同,当事人可以请求人民法院或者仲裁机构撤销合同。

下列选项中，属于我国沪菜系名菜的是()。

抗生素的发明和使用，使病菌一度不再是人类的致命威胁。但是，在人类使用抗生素治疗疾病的同时，病菌的耐药性也在增加，由于滥用抗生素，出现了目前难以控制的“超级病菌”。上述事实表明()。

做一个平凡的人并不可悲。一个才疏学浅的人如果______，那才是最可悲的。

A．近中沟B．横嵴C．切缘结节D．斜嵴E．轴嵴属于上颌第一磨牙的解剖标志的是()。

某投机者预测10月份大豆期货合约价格将上升，故买入10手(10吨／手)大豆期货合约，成交价格为2030元／吨。可此后价格不升反降，为了补救，该投机者以2015元／吨的价格再次买入5手合约，当市价反弹到()时才可以避免损失。

在一个双链表中，在p结点之前插入q结点的操作是()。