软件水平考试
设某无向图的顶点个数为n，则该图最多（42）条边；若将该图用邻接矩阵存储，则矩阵的行数和列数分别为（）。A.n B.n*(n-1)/2 C.n*(n+1)/2 D.n*n
题目
B.n*(n-1)/2
C.n*(n+1)/2
D.n*n
相似问题和答案
第1题：
有一邻接矩阵
如果是有向图，则该图共有(42)条弧；如果是无向图，则该图共有(43)条边。
A．5
B．4
C．3
D．2
第2题：
●设一个包含N 个顶点、E 条边的简单无向图采用邻接矩阵存储结构（矩阵元素 A[i][j]等于1/0 分别表示顶点i与顶点 j 之间有／无边），则该矩阵中的非零元素数目为 (60)。
(60)
A．N
B．E
C．2E
D．N+E
第3题：
用相邻矩阵A表示图，判定任意两个顶点Vi和Vi，之间都有长度为m的路径相连，则只要检查(40)的第i行第j列的元素是否为0即可。
从邻接矩阵
可以看出，该图共有(41)个顶点。如果是有向图，该图有(42)条弧；如果是无向图，则共有(43)条边。
A．mA
B．A
C．Am
D．Am-1
解析：(40)～(43)(40)要判断相邻矩阵A中任意两个顶点Vi和Vi之间是否有长度为m的路径相连，只要检查Am的第i行第j的元素是否为0即可，若为0则无，否则就存在。(41-43)邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号依次为1，2，…，n，则G的邻接矩阵是n阶方阵，所以该图有3个顶点。如果此图是有向图，则矩阵中非0元素个数即为弧的数目(为4)；如果此图为无向图，则一条边会在矩阵中对应有两个非零元素出现，所以共有两条边。
第4题：
设无向图的顶点个数为n，则该图最多有【】条边
A．n-1
B．n(n-1)/2
C．n(n+l)／2
D．n2
[解析]n个顶点的无向完全图边数最多达到 n(n-1)／2．
第5题：
设某无向图的顶点个数为n，则该图最多（ ）条边；若将该图用邻接矩阵存储，则矩阵的行数和列数分别为（ ）。
A.nB.n*(n-1)/2 C.n*(n+1)/2D.n*nA. n、nB. n、n-1 C. n-1.、nD. n+1、n
第6题：
设无向图的顶点数为n，则该图最多有()条边。
A.n-1
B.n(n-1)/2
C.n(n+1)/2
D.0
第7题：
● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结构 （矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧），则该矩阵的元素数目为 （60） ，其中非零元素数目为 （61） 。
第8题：
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。
若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。
(6)O(n+e) (7)O(n2) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n2)。
第9题：
下图的邻接矩阵表示为(39) （行列均以A、B、C、D、E为序）；若某无向图具有10个顶点，则其完全图应包含(40)条边。
A.A
B.B
C.C
D.D
本题考查数据结构基础知识。图的邻接矩阵是一个方阵，所有行标和列标都与图中的顶点一一对应，这样对于矩阵中的一个元素【ij】值为1表示i、j对应拘顶点间有边（或弧），其值为0则表示i、j对应的顶点间不存在边（或弧）。显然，(39)的选项符合以上说明。完全图是指图中任意一对顶点间都存在边（或弧），在无向图中，边(ij)与(JI)是指同一条边，在有向图中，ij>与ji>是两条不同的弧。若完全无向图具有10个顶点，则边的数目为10*9/2=45。
第10题：
B.n、n-1
C.n-1、n
D.n+1、n
对于有n个顶点的无向图，每个顶点与其余的n-1个顶点都可以有1条边，对于每一对不同的顶点v与w，边（v，w）与（w，v）是同一条，因此该图最多有n*（n-1）/2条边。
图采用邻接矩阵存储时，矩阵的每一行对应一个顶点，每一列对应一个顶点，所以矩阵是个n阶方阵。