设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )A．O(n)B．O(n+e)C．O(n2)D．O(n×e)
题目
设图G采用邻接表存储，则拓扑排序算法的时间复杂度为( )
A．O(n)
B．O(n+e)
C．O(n2)
D．O(n×e)
相似考题
参考答案和解析
更多“设图G采用邻接表存储,则拓扑排序算法的时间复杂度为()A.O(n)B.O(n＋e)C.O(n2)D.O(n×e) ”相关问题
-
第1题：
●直接选择排序的平均时间复杂度为 (46) 。
(46) A．O(n)
B．O(nlogn)
C．O(n2)
D．O(logn)
正确答案：C
【解析】本题主要考查排序算法的时间复杂度。排序算法的时间复杂度是用元素的平均比较次数和元素的平均移动次数来衡量的，它是评价排序算法的主要标准。 -
第2题：
设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为()。
A.O(n+e)
B.O(n^2)
C.O(ne)
D.O(n^3)
正确答案：A
-
第3题：
对于长度为n的顺序存储的线性表,访问结点和插入、删除结点的平均时间复杂度为()。A.O(0)
B.O(1)
C.O(n)
D.O(n2)
正确答案：C
-
第4题：
直接选择排序的平均时间复杂度为(46)。
A．O(n)
B．O(nlogn)
C．O(n2)
D．O(logn)
正确答案：C
解析：本题主要考查排序算法的时间复杂度。排序算法的时间复杂度是用元素的平均比较次数和元素的平均移动次数来衡量的，它是评价排序算法的主要标准。 -
第5题：
在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。
A.O(n)
B.O(n+e)
C.O(n2)
D.O(n3)
正确答案：B
-
第6题：
若n表示问题的规模、O(f(n))表示算法的时间复杂度随n变化的增长趋势，则算法时间复杂度最小的是(59)。
A．O(n2)
B．O(n)
C．O(logn)
D．O(nlogn)
正确答案：C
解析：本题考查的是算法消耗的时间度量。一般情况下，一个算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T(n)=O(f(n))，它表示随问题n的增大，算法执行时间的增长率和 f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。显然，在O(n2)、O(n)、 O(logn)和O(nlogn)中，复杂度最小的是O(logn)。 -
第7题：
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为(63)。
A．O(n2)
B．O(e2)
C．O(n*e)
D．O(n+e)
正确答案：D
解析：本题考查数据结构基础知识。深度优先和广度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n2)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为 O(n+e)。 -
第8题：
设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____。
A.O(1)
B.O(n)
C.O(n2)
D.O(log2n)
正确答案：D
-
第9题：
设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(1)。
A．O(lgn)
B．O(nlgn)
C．O(n)
D．O(n2)
正确答案：B
解析：运用数学递推公式，可以推算出数量级O(nlgn)。 -
第10题：
求最短路径的FLOYD算法的时间复杂度为(16)。
A．O(n)
B．O(n+e)
C．O(n2)
D．O(n3)
正确答案：D
解析：FLOYD算法的时间复杂度为n3。 -
第11题：
在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)
B.O(n+e)
C.On×n
D.O(n×n×n)答案：B解析：拓扑排序中每个顶点都需要出入栈(当用邻接表表示图时的执行次数为n)，然后把入度减1(当用邻接表表示图时的执行次数为e)，所以拓扑排序的时间复杂度为O(n+e)。 -
第12题：
对有 n 个结点、e 条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历, 时间复杂度为（ ）。A.O（n^2）
B.O（e^2）
C.O（n+e）
D.O（n*e）答案：A解析：图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有 n 个结点的图，其邻接矩阵是一个n阶方阵。对于无向图来说，其邻接矩阵如下图所示
当采用深度优先进行遍历的时候，查找所有邻接点所需要的时间是O(n^2) 。 -
第13题：
设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(59)。
A．O(1gn)
B．O(nlgn)
C．O(n)
D．O(n2)
正确答案：B
解析：本题考查的是算法的时间复杂度概念。 -
第14题：
假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点VI相关的所有弧的时间复杂度是【】
A．O(n)
B．O(e)
C．O(n+e)
D．O(n*e)
正确答案：C
-
第15题：
设n为正整数。则下面程序段的时间复杂度为()。 k=0; for(i=1;i<=n;i＋＋){ for(j=i;j<=n;j＋＋) @ k＋＋; }A.O(1)
B.O(n)
C.O(nlogn)
D.O(n2)
参考答案：D
-
第16题：
冒泡排序的时间复杂度为A．O(n) B．O(n2) C．O(log2n) D．O(nlog2n)
正确答案：B
冒泡排序的基本概念是：以升序为例，依次比较相邻的两个数，将小数放在前面，大数放在后面。第一趟排序过程是这样的，首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。这样一次排序后，最后一个数为所有数中的最大数。第二趟排序重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。
冒泡排序的时间复杂度是指执行冒泡排序算法所需要的时间。冒泡排序算法最好的时间复杂度为所要排序的数列为正序，即在执行排列算法之前就已经达到目标的顺序。这样只需要执行一次排序算法，算法所需要进行数据比较的次数为n-1次。冒泡排序算法最差的时间复杂度为当前所要进行排列的数列顺序与目标数列的顺序相反。算法所需要进行数据比较的次数为n(n-1)/2=O(n2)。算法的平均时间复杂度为O(n2)。 -
第17题：
若长度为n的线性表采用顺序存储结构，在第i≤1≤i≤n+1) 个位置插入一个新元素的算法时间复杂度为(1)。
A．O(0)
B．O (1)
C．O(n)
D．O(n2)
正确答案：C
解析：性表上插入元素，时间主要耗费在移动元素上。不失一般性，假定性表上的任何位置插入元素是等概率的，即：Pi=1/(n+1)，那么在插入一个元素时所需要移动元素的次数的平均值为：。因此，在长度为n的线性表中插入一个元素的时间复杂度为。 -
第18题：
对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。
A.O（n2）和O（n）
B.O（n）和O（n）
C.O（n2）和O（1）
D.O（n）和O（1）
正确答案：C
本题考查基本排序算法的时间复杂度与空间复杂度。 -
第19题：
设某算法的计算时间表示为递推关系式T(n)＝T(n-1)+n(n＞O)及T(0)＝1，则该算法的时间复杂度为(65)。
A．O(lgn)
B．O (nlgn)
C．O(n)
D．O(n2)
正确答案：D
解析：本题考查算法设计基础知识。根据题目中给出的递推关系：T(n)＝T(n-1)+n＝T(n-2)+n-1+n＝…＝T(0)+1+2+…+n-1+n＝1+n(n+1)/2 -
第20题：
下面算法的时间复杂度为()
A.O(1)
B.O(n)
C.O(n*n)
D.O(n!)
正确答案：B
-
第21题：
具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。
A．O(n2)
B．O(n)
C．O(n-1)
D．O(n+1)
正确答案：A
-
第22题：
冒泡排序在最好情况下的时间复杂度为（ ）。A.O（1）
B.O（log2n）
C.O（n）
D.O（n2）答案：C解析：若初始序列为“正序”，则只需进行一趟排序，在排序过程中进行n-l次比较，且不移动记录，因此时间复杂度为n。 -
第23题：
对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历,时间复杂度为（ ）。A.O（n^2）
B.O（e2）
C.O（n+e）
D.O（n*e）答案：A解析：图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有 n 个结点的图，其邻接矩阵是一个n阶方阵。对于无向图来说，其邻接矩阵如下图所示
当采用深度优先进行遍历的时候，查找所有邻接点所需要的时间是O(n^2) 。