首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。 说明你所设计算法的时间复杂度。
admin
2017-04-28
38
问题
试设计一个算法,判断一个有向无环图G中是否存在这样的顶点,该顶点到其他任意顶点都有一条有向路径。有向图G以邻接表的形式存储。
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:无论是采用深度优先遍历还是广度优先遍历,可知每个结点均访问了一次,因此时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/WJRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1895年发现X射线,拉开物理学革命序幕的科学家是()。
雅各宾派维护大革命成果的主要措施有()。①颁布严禁囤积居奇的法令②改组救国委员会③发布全民皆兵的法令④制定全面限价法令
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
在1945年提议战后有必要建立一个普遍性的国际组织(即后来的联合国),以维持国际和平与安全的国家不包括()。
下列选项中不属于《国际联盟盟约》内容的是()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
法国里昂工人起义提出:“我们只有一个口号‘人人自由平等!’”英国宪章运动请愿书提出:“我们竭尽自由人的义务,就应享受自由人的权利。我们要求普遍选举。”这些要求表明()。①带有空想社会主义色彩②当时工人的要求还没有超出资产阶级民主主义的范畴
原始群是以()为纽带而组成的社会组织形式。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
TCP协议规定HTTP端口号为80的进程是()。
随机试题
宗气的生理功能有
此时辨证属()此时方药宜选()
中国药典收载品种的中文名称为
患者,女性,57岁,肝性脑病,意识障碍。护士为其口腔护理,可不必准备的用物是
根据《刑法》第263条的规定,构成抢劫罪,有下列情形之一的,处10年以上有期徒刑、无期徒刑或死刑,并处罚金或者没收财产。“下列情形”包括下列哪些情形?()
在美国、加拿大和英国,早餐麦片极受欢迎,是最盈利的行业之一。但是,在法国、德国、意大利以及其他很多国家,早餐麦片就不怎么受欢迎,利润也不高。这体现的是()。
企业自产自用的应税矿产品应交纳的资源税,应计入下列()科目。
在取保候审期间,不得中断对案件的起诉、审理。( )
一、注意事项1.申论考试是对应考者综合分析材料的能力、提出和解决问题能力、文字表达能力的测试。2.作答时限:建议阅读给定资料40分钟,作答1lO分钟。3.仔细阅读给定资料,按照后面提出的“作答要求”依次作答。4.请在指定位置作答,在草稿纸上或者其他
维萨里
最新回复
(
0
)