软件工程
若具有n个顶点且不带权的连通图采用邻接矩阵存储，则该邻接矩阵中至少有（）个非零元素。
题目
若具有n个顶点且不带权的连通图采用邻接矩阵存储，则该邻接矩阵中至少有（）个非零元素。
相似问题和答案
第1题：
A、n
B、(n-1)*(n-1)
C、n-1
D、n*n
第2题：
A、n
B、n^2
C、n-1
D、(n-1)^2
第3题：
●若采用邻接矩阵结构存储具有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的平方阶。
第4题：
对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。
- A、n
- B、（n-1）2
- C、（n+1）2
- D、n2
正确答案:D
第5题：
若具有n个顶点的无向图采用邻接矩阵存储方法，则该邻接矩阵一定为一个（）。
- A、一般矩阵
- B、对角矩阵
- C、对称矩阵
- D、稀疏矩阵
正确答案:C
第6题：
若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个( )。
A．上三解矩阵
B．稀疏矩阵
C．对角矩阵
D．对称矩阵
解析：在邻接矩阵来表示的图中，从一个点到另一个点的边，则相应位置上为1，否则为1，由于是无向图，点a到b存在边，那么点b到a也存在边，因此表示出来的邻接矩阵为对称矩阵。
第7题：
第8题：
A.对称矩阵
B.一般矩阵
C.稀疏矩阵
D.对角矩阵
答案：A
解析：在邻接矩阵来表示的图中，从一个点到另一个点的边，则相应位置上为1，否则为1，由于是无向图，点a到b存在边，那么点b到a也存在边，因此表示出来的邻接矩阵为对称矩阵。无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+...+(n-1)=n(n-1)/2个单元。
第9题：
若具有n个顶点、e条边且不带权的无向图采用邻接矩阵存储，则邻接矩阵中的零元素的数目是（）
正确答案:n2-2e
第10题：
n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。
正确答案:O(n2)