首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
25
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
下列关于清朝军机处的叙述,不正确的是()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
下列关于湘军的叙述中不正确的是()。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
美国工业革命的有利条件包括()。①美国自然资源丰富②独立战争后,美国创立了资产阶级共和制度③地理位置优越,远离动乱的欧洲④拥有潜在的广阔的国内市场
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
(1)根据无类IP地址的规则,每个网段中有两个地址是不分配的:主机号全0表示网络地址,主机号全1表示广播地址。因此8位主机号所能表示的主机数就是28-2,即254台。该网络要划分为两个子网,每个子网要120台主机,因此主机位数X应该满足下面三个条件:
一个由高速缓冲存储器Cache与主存储器组成的二级存储系统。已知主存容量为1MB,按字节编址,缓存容量为32KB,采用组相联方式进行地址映射与变换,主存与缓存的每一块为64B,缓存共分8组。(1)写出主存与缓存的地址格式(标明各字段名称与位数)
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
随机试题
拉线衬环又称拉线环、三角圈、心形圈。()
双务合同订立后应后为给付的一方当事人发生了财产减少致难为对待履行的情形或者发生应后为给付的一方当事人明示或默示预期拒绝履行合同义务的情形,应先为给付的一方当事人在对方提供合适担保前享有的拒绝向相对方履行合同义务的权利。此种抗辩属于_______。
接诊时,如出现以下症状,哪项最具特征性下列哪种治疗是错误的
慢性阻塞性肺疾病的自然疗法不包括下列中的哪一项
下列属于人工费的是()。
加何引导幼儿“喜欢听故事,看图书”?
光明小学举办三次义务劳动,共100人次参加,在参加义务劳动的学生中,只参加1次、2次、3次的人数之比为3:2:1,该校共有()人参加义务劳动。
提出共鸣理论的学者是
软件测试的对象不包括()。
为了最终实现目标系统,必须设计出组成这个系统的所有程序和文件,通常分为两个阶段完成,即过程设计和
最新回复
(
0
)