首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
54
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述当代科技革命发生的背景条件。
在1945年提议战后有必要建立一个普遍性的国际组织(即后来的联合国),以维持国际和平与安全的国家不包括()。
关于德意志宗教改革的说法不正确的是()
三大战役的先后顺序是()
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
八届十中全会对邓子恢等人提倡建立包产到户的生产责任制进行错误批判,并将其称之为()。
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。
某机字长32位,主存容量32MB,按字节编址;该机的Cache采用4路组相联映射方式,Cache容量为16KB,块长为4个字,试回答下列问题:(1)主存地址位数为多少?(2)画出主存地址格式示意图,注明各字段名称及位数。(3)设该Ca
随机试题
男,42岁,饮酒后突然上腹疼痛、呕吐、腹胀,无腹泻。T37.5℃,腹胀、呈橡皮腹,中上腹压痛,无反跳痛。血、尿淀粉酶升高,血钾、血钙降低。最可能的诊断
比释动能率的国际单位是
慢性非特异性唇炎的临床表现为
某大型设备振动试验台施工为大体积的钢筋混凝土施工,负责该项目的专业监理工程师在该工程开工前审查了承包人的施工方案。编制了监理实施细则,设置了质量控制点。[问题]什么是质量控制点?质量控制点设置的原则是什么?
依法批准成立未达3年的会计师事务所,一般不准从事证券业务。()
在资产负债表日至财务报告批准报出日之间发生的下列事项中,不属于资产负债表日后调整事项的是()。
以下是高中美术“绘画”模块《版画》的教学片段。授课对象:高二年级学生教学目标:了解版画的起源及分类,初步掌握一至两种版画的制作方法。教学片段一:学习版画的起源及分类课件出示版画起源的标题和文字介绍,教师进行阅读,并让学生进行齐读。紧接着课件出示版画
设等差数列{an}的前n项和为Sn,若S9=72,则a2+a4+a9=______.
下列不具有法人资格的是()。
针对不同的传输介质,网卡提供了相应的接口。其中适用非屏蔽双绞线的网卡应提供________接口。
最新回复
(
0
)