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

admin2014-04-17 39

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

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

答案D

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

1938年，英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题，这次会议被称为()，它把英法的绥靖政策推到了顶峰，加速了二战的爆发。

清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏

第一国际成立的时间是()。

北魏建立和统一的时间分别是()。

人民解放军转入战略进攻的方向为大别山地区，主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

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

简述市场化管理的含义。

儿童时期会厌呈哪种形状：

A、吡罗昔康B、洛美昔康C、吲哚美辛D、舒林酸E、双氯芬酸钠结构中含有甲基亚砜基的药物为（）

根据我国刑事诉讼法的规定，下列哪些情况需要省级人民政府指定的医院进行鉴定或者出具证明文件？()

工业建设项目可行性报告的质量评价目标至少包括()、生态环境论证等方面。

扩张性财政政策包括()

简述家校联系的基本方式。

公文处理是指对公文的撰制、传递处理与管理，是使公文得以形成并产生实际效用的全部活动。()

现有26株树苗要分植于5片绿地上，若使每片绿地上分得的树苗数各不相同，则分得树苗最多的绿地至少可分得几株树苗(　　)。

计算机408

学硕统考专业

1938年，英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题，这次会议被称为()，它把英法的绥靖政策推到了顶峰，加速了二战的爆发。

清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏

第一国际成立的时间是()。

北魏建立和统一的时间分别是()。

人民解放军转入战略进攻的方向为大别山地区，主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

试编写一个非递归算法，实现求以二叉链表存储的二叉树中q结点的祖先。

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

简述市场化管理的含义。

儿童时期会厌呈哪种形状：

A、吡罗昔康B、洛美昔康C、吲哚美辛D、舒林酸E、双氯芬酸钠结构中含有甲基亚砜基的药物为（）

根据我国刑事诉讼法的规定，下列哪些情况需要省级人民政府指定的医院进行鉴定或者出具证明文件？()

工业建设项目可行性报告的质量评价目标至少包括()、生态环境论证等方面。

扩张性财政政策包括()

简述家校联系的基本方式。

公文处理是指对公文的撰制、传递处理与管理，是使公文得以形成并产生实际效用的全部活动。()

现有26株树苗要分植于5片绿地上，若使每片绿地上分得的树苗数各不相同，则分得树苗最多的绿地至少可分得几株树苗( )。

现有26株树苗要分植于5片绿地上，若使每片绿地上分得的树苗数各不相同，则分得树苗最多的绿地至少可分得几株树苗(　　)。