早教吧考试题库频道 --> 计算机类考试 -->软考中级 -->
A.O(n2)B.O(n)C.O(n-1)D.O(n+1)
题目
A.O(n2)
B.O(n)
C.O(n-1)
D.O(n+1)
参考答案
正确答案:B
解析:不论是深度优先还是广度优先搜索遍历,图中n个顶点都必须被访问一次。从某个顶点出发,要搜索到其他顶点,必须沿着图中的边去找。用邻接矩阵做图的存储结构时,这些边是分布在一个n阶方阵中,要检测出这些边,必须对矩阵中n2个元素进行检测,因此,其时间复杂度为O(n2)。若用邻接表作为存储结构,只需对代表e条无向边的2e个边表结点进行检测,其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号,每个顶点都要进栈一次,故n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号,每个顶点都要进队一次,故队列长度为n,所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。
解析:不论是深度优先还是广度优先搜索遍历,图中n个顶点都必须被访问一次。从某个顶点出发,要搜索到其他顶点,必须沿着图中的边去找。用邻接矩阵做图的存储结构时,这些边是分布在一个n阶方阵中,要检测出这些边,必须对矩阵中n2个元素进行检测,因此,其时间复杂度为O(n2)。若用邻接表作为存储结构,只需对代表e条无向边的2e个边表结点进行检测,其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号,每个顶点都要进栈一次,故n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号,每个顶点都要进队一次,故队列长度为n,所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。
看了A.O(n2)B.O(n)C....的网友还看了以下:
设数列{an}满足a1=a,an+1=can+1-c,n∈N*其中a,c为实数,且c≠0,a≠1, 数学 2020-05-13 …
设随机变量ξ服从正态分布N(01),P(ξ>1)=p,则P(-1<ξ<0)等于()(A)p(B)1 数学 2020-05-13 …
二次函数y=ax²+bx+c的图像如图所示,若M=4a+2b+c,N=a-b+c,P=4a+2b, 数学 2020-05-16 …
A.0≤|N|≤1-2-(n-1)B.0≤|N|≤1-2-nC.0≤|N|≤1-2-(n+1)D.0 计算机类考试 2020-05-26 …
已知数列{an}的通项公式为an=2^(n-1)+1则a1Cn^0+a2Cn^1+a3Cn^2+. 数学 2020-07-09 …
什么是二项式的通式?在二项式定理(a+b)^n=C(n,0)a^n+C(n,1)a^(n-1)b+ 数学 2020-07-31 …
证明组合性质:C(n+1,m)=C(n,m)+C(n,m-1)C(n+1,m)=(n+1)!/m!( 数学 2020-11-01 …
排列数与组合数m等于0时的情况1.首先排列数有Am.n,如果m=0.n>0则Am.n=n×(n-1) 数学 2020-11-18 …
X∪Y=〈1,2,…,n〉求集合方程有序解的个数:X∪Y=〈1,2,…,n〉在此鞠躬致谢.我算出来是 数学 2021-01-13 …
如果正数数列{an}为等差数列,公差d>0那么下列数列中为等差数列的是A.{根号a(n)}B.{根号 数学 2021-02-04 …