首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的( )。
修改递归方式实现的图的深度优先搜索(DFS)算法,将输出(访问)顶点信息的语句移到退出递归前(即执行输出语句后立刻退出递归)。采用修改后的算法遍历有向无环图G,若输出结果中包含G中的全部顶点,则输出的顶点序列是G的( )。
admin
2021-03-17
37
问题
修改递归方式实现的图的深度优先搜索(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
学硕统考专业
相关试题推荐
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。写出4种寻址方式下,有效地址EA的表达式。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。当指令寻址方式由操作码指出时,直接和间接寻址可寻址的主存空
下列排序算法中,()每一趟都能选出一个元素放在最终位置上,并且是不稳定的。
在某个操作系统中,通过大量的实验,人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比,即可用内存加倍,缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns,但若发生了缺页中断就需要1ms。一个程序运行了60
某机主存容量为1MB,两路组相连方式(每组仅有两块)的Cache容量为64KB,每个数据块为256字节。CPU要顺序访问的地址为20124H、58100H、60140H和60138H等4个主存字节单元中的数。已知访问开始前第2组(组号为1)的地址阵
将任意给定的序列1,2,…,n指定为一棵树的先根遍历序列;同时任意给定这n个数值(1,2,…,n)的一个排列p1,p2…pn为这棵树的后根遍历序列。(1)根据这样的先根遍历序列和后根遍历序列,是否都可以得到一棵树?如果能够,请简述理由(不要求形式化证
已知二叉树采用二叉链表方式存放,要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归,且不用栈来完成?请简述原因。
二叉树若用顺序方法存储,则下列4种算法中运算时间复杂度最小的是()。
随机试题
下列有关衍生金融工具说法错误的是:()。
委托人与监理人签定了委托监理合同后,委托人可以行合( )。
企业收到包装物退回的押金,已存入银行,则应()。
学校及其他教育机构对教学辅助人员和其他专业技术人员实行()制度。
下列不属于幼儿园教师工作职责的内容是()
A.AsHSBCDataProcessing(Shanghai)Limitedcontinuestogrow,weinvitepeoplewhoexcelinachallenginganddynamicwork
A、Itwillputtheproductivefarmlandindanger.B、Itmayimproveconditionsforsomeinvasivespecies.C、Itisawarningsignf
A、Itssouthernpartismostsuitabletolivein.B、Itisawonderfulplaceforshopping.C、Itdoesn’thavemanyentertainmentpl
A、Theleftpan.B、Therightpart.C、Theupperpart.D、Thelowerpan.AForaten-month-oldbaby,whichpartofthebrainisactiv
Mostyoungpeopleenjoysomeformofphysicalactivity.Itmaybewalking,cyclingorswimming,or,inwinter,skatingorskiing
最新回复
(
0
)