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

admin2021-01-13 21

问题拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点　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

阅读以下算法说明和C程序，根据要求回答问题1至问题2。[说明][算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。在[算法4-1

阅读以下说明和C++代码，将应填入(n)处的字句写上。[说明]现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显不display()。需要新增图形Circle，又已知有类XX

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

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

将艺术品分为语音层、语义层、图式层和客体层这四个层次的美学家是【】

简述建设性冲突与破坏性冲突。

20周末胎儿发育特征为（）

某生物滤池进水量Q=300m3／h、BOD5=300mg／L，生物滤料体积为2400m3，则有机负荷为()。

工程项目计划和工作成果是()输入的重要内容。

银行代理业务不构成商业银行表内资产负债业务。()

瓦格纳所说的税收的“社会正义原则”是指税收具有公共性。()

内部学习动机强的学生外部学习动机一定弱。

A.thoughtitradicallyB.felttheposteralittlecynicalC.wasnothappywiththedecisionsmadeD.positivelyf

Whoarethedonorsforthedesignsusedinthecards?_________fromallovertheworld.Whatkindofpaperisusedwhenmakin

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点 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

阅读以下算法说明和C程序，根据要求回答问题1至问题2。[说明][算法4-1]的功能是：用来检查文本文件中的圆括号是否匹配。若文件中存在圆括号没有对应的左括号或者右括号，则给出相应的提示信息，如图4-18所示。在[算法4-1

阅读以下说明和C++代码，将应填入(n)处的字句写上。[说明]现有一个显示系统，要显示的图形有线Line、矩形Square，抽象出一个Shape类(接口)，有方法显不display()。需要新增图形Circle，又已知有类XX

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

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

将艺术品分为语音层、语义层、图式层和客体层这四个层次的美学家是【】

简述建设性冲突与破坏性冲突。

20周末胎儿发育特征为（）

某生物滤池进水量Q=300m3／h、BOD5=300mg／L，生物滤料体积为2400m3，则有机负荷为()。

工程项目计划和工作成果是()输入的重要内容。

银行代理业务不构成商业银行表内资产负债业务。()

瓦格纳所说的税收的“社会正义原则”是指税收具有公共性。()

内部学习动机强的学生外部学习动机一定弱。

A.thoughtitradicallyB.felttheposteralittlecynicalC.wasnothappywiththedecisionsmadeD.positivelyf

Whoarethedonorsforthedesignsusedinthecards?_________fromallovertheworld.Whatkindofpaperisusedwhenmakin

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