对于具有n个顶点、6条边的图()。A.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n2) B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关 C.采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e) D.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关

第1题：

第2题：

要使得具有n个顶点的有向图成为强连通图，至少需要有多少条边？

正确答案:要使得具有n个顶点的有向图成为强连通图，至少需要有n条边。

第3题：

对于具有n个顶点和e条边的无向图，在其对应的邻接链表中一共包含（）个表结点。

正确答案:2e

第4题：

要连通具有n个顶点的有向图，至少需要（）条边。

• A、n-l
• B、n
• C、n+l
• D、2n

正确答案:B

第5题：

具有n个顶点的有向图最多有（）条边。

• A、N
• B、n（n-1）
• C、n（n+1）
• D、n²

正确答案:B

第6题：

具有n个顶点的有向无环图最多有多少条边？

正确答案: 具有n个顶点的有向无环图最多有n×（n—1）/2条边。
这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。

第7题：

具有n个顶点的连通图至少有多少条边？

正确答案: 具有n个顶点的连通图至少有n-1条边。
这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。因此，具有n个顶点的连通图至少有n-1条边。

第8题：

对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为（）、（）和（）。

正确答案:O（n）；O（e/n）；O（e）

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为（）

• A、n
• B、n+1
• C、n-1
• D、n+e

正确答案:A

第15题：

对于一个具有n个顶点的有向图的边数最多有（）。

• A、n
• B、n（n-1）
• C、n（n-1）/2
• D、2n

正确答案:B

第16题：

对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为（）和（）条。

正确答案:e；e

第17题：

对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为（）和（）

正确答案:2e；e

第18题：

对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）。

• A、n-1
• B、n+1
• C、n
• D、n+e

正确答案:C

第19题：

对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（）和（）。

正确答案:n；n-1

第20题：

对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为（）和（）条。

正确答案:e；2e

第21题：

第22题：

第23题：

第24题：