首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的( )。
修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的( )。
admin
2021-03-17
19
问题
修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的( )。
选项
A、拓扑有序序列
B、逆拓扑有序序列
C、广度优先搜索序列
D、深度优先搜索序列
答案
B
解析
题目已经限定有向无环图图,假设从a结点出发开始深度遍历,那么这一次递归到最大深度,必然终止于某结点(记为h结点),h结点必然没有出度。此时h输出,程序栈退栈,回到h的前一个结点(记为f),如果f还有其他出度,那么此时要访问其他出度,直到每一个出度的分支都访问结束才能访问f,这样来看,一个结点要被访问的前提必须是他的所有出度分支都要被访问,换句话说也就是等一个结点没有出度时才可以访问,这就是逆拓扑排序(每次删除的都是出度为零的结点)。
转载请注明原文地址:https://kaotiyun.com/show/HH3i777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
线索化的二叉树中,某结点*p没有孩子的充要条件是()。
已知一组关键字为(26,36,41,38,44,15,68,12,6,5l,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:汁算出等概率情况下查找失败的平均查找长度。
采用了虚拟存储器的计算机系统中,逻辑地址与物理地址相比()。
编写判定给定的二叉树是否是二叉排序树的函数。
设有3个作业,其运行时间分别为2小时、5小时、3小时,假定它们同时到达,并在同一台处理机上以单道运行方式运行,则平均周转时间最小的执行顺序是()。
下面关于进程的叙述中,正确的是()。
假设有8个记录A、B,C、D、E、F、G、H存放在磁盘里,每个磁道有8个扇区,正好可以存放8个记录。假设磁盘旋转速度为20ms/r,处理程序每读出一个记录后,用2ms的时间进行处理,请问:(1)当记录A、B、C、D、E、F、G、H按顺序放在磁
一台模型机共有7条指令,主频25MHz,各指令的使用频度与CPI如表3—1所列,该机有8位和16位两种指令字长,采用2—4扩展操作码。8位字长指令为寄存器一寄存器(R—R)二地址类型,16位字长指令为寄存器一存储器(R—M)二地址变址类型(地址码范围在-
并发使得处理机的利用率得到提高,其主要原因是处理机与10可以同时为多个进程服务,也即处理机与IO设备真正地并行。但是处理机的利用率提高并不是简单地将二个进程的处理机利用率相加,而是遵循一定的规律。现在有一个计算机系统采用多道程序技术实现了并发,调度算法采用
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们
随机试题
下列有关刑事诉讼的管辖的表述错误的是
急性尿潴留病因中,属于动力性梗阻的是______。
消渴发病常与血瘀有关,其原因是
下列除哪项外可以用川芎治疗()
下列关于水体中污染物的迁移转化过程说法正确的是()。
实际支付利息时,涉及的会计科目有()。
新进企业的工人不知如何完成份内工作,从而招致解雇,其原因是()。
教育目的的本质是()。
Youaregoingtoreadanewspaperarticleabouthumanbeingsgettingtaller.Eightsentenceshavebeenremovedfromthearticle,
Whatwasthewoman’sproblem?
最新回复
(
0
)