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

admin2021-03-17 43

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

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

答案B

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

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

一个3200bit上的TCP报文传到IP层，数据链路层可以发送的最长数据帧中的数据部分只有1200bit。IP层需要向数据链路层发送()。

页式虚拟存储管理的主要特点是()。

有关社会认知理论的基本概念，描述错误的是

关于头孢菌素类特点的叙述正确的是

决定胶片平整度的层面是

某铁矿建设单位按照国家有关安全生产法律法规的规定，向安全生产监督管理部门提出矿山建设项目安全设施设计审查申请时，应提交必要的文件资料。下列资料中，不在提交范围的是()。

在运输机场开放使用的情况下，未经批准在()内进行施工，将由民用航空管理部门责令改正，并处10万元以上50万元以下的罚款。

下列案例中哪些属于USP型战略?()

虚假一致性偏差是指人们常常高估或夸大自己的信念、判断及行为，让人们坚信自己信念、判断的正确性。当遇到与此相冲突的信息时，这种偏差使人坚持自己的社会知觉。根据上述定义，下列属于虚假一致性偏差的是：

兴中会的革命报刊的评价。(山东大学，2008年)

用二维表结构表示实体与实体之间的联系的模型是()。