拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点　vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。

admin2021-01-13 18

问题拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点　vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。

选项 A、包含回路
B、是强连通图
C、是完全图
D、是有向树

答案A

解析本题考查图数据结构。对有向图进行拓扑排序的方法如下：(1)在AOV网中选择一个入度为0(没有前驱)的顶点且输出它。(2)从网中删除该顶点及其与该顶点有关的所有边。(3)重复上述两步，直至网中不存在入度为0的顶点为止。执行的结果会有两种情况：一种是所有顶点已输出，此时整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。

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

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点　vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。

软件设计师上午基础知识考试

软考中级

阅读下列算法说明和流程图，根据要求回答问题1～问题3。[说明]某机器上需要处理n个作业job1，job2，…，jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]现有如下关系模式：R(A#，B#，C，DE)，其中，A#，B#为组合键，R上存在的函数依赖有(A#，B#)→E，B#→C，C→D

把上面用关系表示的实体，实体与实体之间的联系，用E-R图表示出来，要求在图中表示联系的类型(1:1，L:N，M:N)。用SQL语言写出查询：查询年龄不在20～23岁(包括20岁和23岁)之间的学生的姓名，系别和年龄。

阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历过程如下：若不是空树，根节点入栈，进入左子树；若已

阅读下列说明和图。[说明]某公司欲开发招聘系统以提高招聘效率，其主要功能如下：(1)接受申请验证应聘者所提供的自身信息是否完整，是否说明了应聘职位，受理验证合格的申请，给应聘者发送致谢信息。(2)评估应聘者根

阅读以下说明和Java码，将应填入(n)处的字名写在的对应栏内。[说明]编写一个学生类Student，要求：(1)学生类Student属性有：id:long型，代表学号name:String类对象，代表姓名

医学科研道德的基本要求不包括

患者食少便溏，四肢乏力，形体消瘦，胸脘闷胀，面色萎黄，舌苔白，脉细缓，治宜选用（　　）。

在治疗噎膈时，时刻要考虑的因素是

可与异羟肟酸铁反应生成紫红色的是()。

我国产业结构调整与优化的总原则不包括的内容是()。

()是对会计要素的具体内容进行分类核算的项目。

进口的化妆品必须同时进行标签项目和卫生项目的检验，经检验合格的，检验检疫机构签发《标签审核证书》和《卫生证书》；经检验不合格的，不准销售、使用。()

学校应当推广使用全国通用的普通话，任何学校不得用少数民族通用的语言文字教学。（）

设i是int型变量，f是float型变量，用下面的语句给这2个变量输入值。为了将，100和765.12分别赋给i和f，则正确的输入为______。scanf("i=%d，f=%f”，&i，&f)；

LearntoWalkBeforeYouRunForthispart,youareallowed30minutestowriteanessaycommentingonthesaying"Learnto

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点 vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。

软件设计师上午基础知识考试

软考中级

阅读下列算法说明和流程图，根据要求回答问题1～问题3。[说明]某机器上需要处理n个作业job1，job2，…，jobn，其中：(1)每个作业jobi(1≤i≤n)的编号为i，jobi有一个收益值P[i]和最后期限值d[i]；

阅读以下说明，回答问题1～4，将解答填入对应的解答栏内。[说明]现有如下关系模式：R(A#，B#，C，DE)，其中，A#，B#为组合键，R上存在的函数依赖有(A#，B#)→E，B#→C，C→D

把上面用关系表示的实体，实体与实体之间的联系，用E-R图表示出来，要求在图中表示联系的类型(1:1，L:N，M:N)。用SQL语言写出查询：查询年龄不在20～23岁(包括20岁和23岁)之间的学生的姓名，系别和年龄。

阅读下列说明和C程序，将应填入(n)处的字句写在对应栏中。[说明]借助一个栈结构，可实现二叉树的非递归遍历算法。InOrderTraverse数实现中序非递归遍历，遍历过程如下：若不是空树，根节点入栈，进入左子树；若已

阅读下列说明和图。[说明]某公司欲开发招聘系统以提高招聘效率，其主要功能如下：(1)接受申请验证应聘者所提供的自身信息是否完整，是否说明了应聘职位，受理验证合格的申请，给应聘者发送致谢信息。(2)评估应聘者根

阅读以下说明和Java码，将应填入(n)处的字名写在的对应栏内。[说明]编写一个学生类Student，要求：(1)学生类Student属性有：id:long型，代表学号name:String类对象，代表姓名

医学科研道德的基本要求不包括

患者食少便溏，四肢乏力，形体消瘦，胸脘闷胀，面色萎黄，舌苔白，脉细缓，治宜选用（ ）。

在治疗噎膈时，时刻要考虑的因素是

可与异羟肟酸铁反应生成紫红色的是()。

我国产业结构调整与优化的总原则不包括的内容是()。

()是对会计要素的具体内容进行分类核算的项目。

进口的化妆品必须同时进行标签项目和卫生项目的检验，经检验合格的，检验检疫机构签发《标签审核证书》和《卫生证书》；经检验不合格的，不准销售、使用。()

学校应当推广使用全国通用的普通话，任何学校不得用少数民族通用的语言文字教学。（）

设i是int型变量，f是float型变量，用下面的语句给这2个变量输入值。为了将，100和765.12分别赋给i和f，则正确的输入为______。scanf("i=%d，f=%f”，&i，&f)；

LearntoWalkBeforeYouRunForthispart,youareallowed30minutestowriteanessaycommentingonthesaying"Learnto

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点　vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定(57)。

患者食少便溏，四肢乏力，形体消瘦，胸脘闷胀，面色萎黄，舌苔白，脉细缓，治宜选用（　　）。