修改递归方式实现的图的深度优先搜索(DFS)算法，将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G，若输出结果中包含G中的全部顶点，则输出的顶点序列是G的( )。

admin2021-03-17 58

问题修改递归方式实现的图的深度优先搜索(DFS)算法，将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G，若输出结果中包含G中的全部顶点，则输出的顶点序列是G的( )。

选项 A、拓扑有序序列
B、逆拓扑有序序列
C、广度优先搜索序列
D、深度优先搜索序列

答案B

解析题目已经限定有向无环图图，假设从a结点出发开始深度遍历，那么这一次递归到最大深度，必然终止于某结点(记为h结点)，h结点必然没有出度。此时h输出，程序栈退栈，回到h的前一个结点(记为f)，如果f还有其他出度，那么此时要访问其他出度，直到每一个出度的分支都访问结束才能访问f，这样来看，一个结点要被访问的前提必须是他的所有出度分支都要被访问，换句话说也就是等一个结点没有出度时才可以访问，这就是逆拓扑排序(每次删除的都是出度为零的结点)。

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

已知4位有效信息为1010，试根据下列要求进行编码。(1)按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。(2)将其编码为循环冗余校验码，生成多项式G(x)=1011。

三类线程search、insert、delete共享(访问)单链表，利用P、V原语操作实现这三类线程。限定如下：(1)search可以与同类线程同时执行；(2)insert类线程之间互斥，但是可以与任意多search同时执行；(3)delete不但同类之间

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

若一组记录的排序码序列F={50，80，30，40，70，60}，利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为()。

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

由于CPU内部的操作速度较快，而CPU访问一次主存所花的时间较长，因此机器周期通常用()来规定。

企业的资本金倘若采用一次性筹集的，应当在营业执照签发之口起()内筹足。

就牙的明度而言，下列说法不正确的是A．女性比男性牙齿明度高B．牙中部明度最高C．活髓牙明度高于死髓牙D．中切牙明度最高E．尖牙明度最高

促进机体产热的主要激素是

下列行为构成滥用市场支配地位的行为有：()

下列对松散材料保温要求正确的是（）。

根据《建设工程工程量清单计价规范》(GB50500——2013)，若合同未约定，当工程量清单项目的工程量偏差在()以内时，其综合单价不作调整，执行原有的综合单价。

()是一部世界上最早的寓言故事集，《农夫与蛇》《龟兔赛跑》都出自这里。

中国有句古话：“橘生淮南则为橘，橘生淮北则为枳”。意思是说，橘这种水里适于淮南一带种植，如果将它移植到淮北去，情况就会大不相同，柑橘会变成一种又小又苦的枳了。这说明()。

以下不属于英美法系特点的是：

有如下程序：#includeusingnamespacestd；classTestClass{public：TestClass(){cout