工学
填空题n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。
题目
参考答案和解析
相似问题和答案
第1题：
●若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 (47) 。
(47) A．O(n)
B．O(n2)
C．O(n2+1)
D．以上都不对
【解析】n个顶点的图的邻接矩阵是一个n阶方阵，有n行n列。从顶点vi出发，对图进行广度优先遍历，需对矩阵的第i行逐列检测非零元(若a[i][j]1,则说明顶点vj与vi之间有边存在，vj就是vi的邻接顶点)。根据广度优先遍历的思想，每一个顶点都要轮换着做出发顶点，即矩阵的每一行都将要被逐列检测。显然，算法中要用一个两重循环来组织逐行逐列的检测操作，所以，算法的时间复杂度是n的平方阶。
第2题：
邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，( )。
A．进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
B．进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C．采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*c)
D．采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为o(n2)
解析：具有n个顶点的有向图可以用一个n*n的方形矩阵表示。假设该矩阵的名称为M，则当<vi，vj>是该有向图中的一条弧时，M[i，j]=1；否则M[i，j]=O。第i个顶点的出度为矩阵中第i行中“1”的个数；人度为第i列中“l”的个数，并且有向图弧的条数等于矩阵中“1”的个数。
第3题：
●具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为 (48) ；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为 (49) ；深度优先或广度优先搜索遍历的空间复杂度为 (50) 。
(48) ,(50) A．O(n2)
B．O(n)
C．O(n-1)
D．O(n+1)
(49) A．O(e)
B．O(e-1)
C．O(e2)
D．O(e+10)
【解析】不论是深度优先还是广度优先搜索遍历，图中n个顶点都必须被访问一次。从某个顶点出发，要搜索到其他顶点，必须沿着图中的边去找。用邻接矩阵做图的存储结构时，这些边是分布在一个n阶方阵中，要检测出这些边，必须对矩阵中n2个元素进行检测，因此，其时间复杂度为O(n2)。若用邻接表作为存储结构，只需对代表e条无向边的2e个边表结点进行检测，其时间复杂度为O(e)。深度优先搜索遍历需要用一个栈来保存本身已被访问但可能还有邻接顶点未被访问的那些顶点的序号，每个顶点都要进栈一次，故 n个顶点需要开辟n个元素的栈(若用递归算法则由系统开辟)。广度优先搜索遍历需要用一个队列来保存顶点的序号，每个顶点都要进队一次，故队列长度为n，所以深度优先或广度优先搜索遍历的空间复杂度为O(n)。
第4题：
第5题：
第6题：
● 邻接矩阵和邻接表是图（网）的两种基本存储结构，对于具有 n个顶点、e条边的图， （59） 。
（59）A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)
D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2)
解析：具有n个顶点的有向图可以用一个n*n的方形矩阵表示。假设该矩阵的名称为M，则当<vi，vj>是该有向图中的一条弧时，M[i，j]=1；否则M[i，j]=O。第i个顶点的出度为矩阵中第i行中“1”的个数；人度为第i列中“l”的个数，并且有向图弧的条数等于矩阵中“1”的个数。
第7题：
具有n个顶点e条边的无向图，若用邻接矩阵作为存储结构，则深度优先或广度优先搜索遍历的时间复杂度为(48)；若用邻接表作为存储结构，则深度优先或广度优先搜索遍历时的时间复杂度为(49)；深度优先或广度优先搜索遍历的空间复杂度为(50)。
A．O(n2)
B．O(n)
C．O(n-1)
D．O(n+1)
第8题：
A.A
B.B
C.C
D.D
第9题：
B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)
D.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
第10题：
若具有n个顶点、e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中的零元素的数目是（）
正确答案:n2-2e