1单选(2分)‌在一个具有n个顶点的无向连通图中至少有（ ）条边。
A.n/2
B.n+1
C.n-1
D.n
正确答案：C
解析： C、树图是边数最少的连通图，其边数=n-1。

课本考据：1、在无向图G中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。2、若图G中的任意两个顶点多是连通的，则称G为连通图。

2单选(2分)‏设G是一个含有6个顶点的无向图，该图至多有（ ）条边。
A.6
B.15
C.7
D.5
正确答案：B
解析： B、边数最多时为完全无向图，有n(n-1)/2=15条边。

课本考据：若无向图中的每两个顶点之间都存在者一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全有向图。无向完全图包含有n(n-1)/2条边，有向完全图包含有n(n-1)条边。

3单选(2分)​在一个具有n个顶点的有向图中，构成强连通图时至少有（ ）条边。
A.n-1
B.n+1
C.n
D.n/2
正确答案：C
解析： C、边数最少的有向强连通图是一个环，其边数=n。

课本考据：在有向图G中若从顶点i到顶点j有路径，则称从顶点i到顶点j是连通的。若图G中的任意两个顶点i和j都，即从顶点i到顶点j和顶点j到顶点i都有路径，则称图G是强连图。

4单选(2分)‏以下关于有向图的说法中，正确的是（ ）。
A.强连通图是任何顶点到其他所有顶点都有边
B.以上都不对
C.有向图中任一顶点的入度等于出度
D.完全有向图一定是强连通图
正确答案：D
解析： D、强连通图是任何顶点到其他所有顶点都有路径，所以选项A错误。有向图中一个顶点的入度不一定等于出度，所以选项C错误。完全有向图的任意两个顶点之间有边，一定是强连通图，所以选项D正确。

课本考据：若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。

5单选(2分)​非空无向图的邻接矩阵是一个（ ）。
A.上三角矩阵
B.对称矩阵
C.对角矩阵
D.零矩阵
正确答案：B

课本考据：图的邻接矩阵是一种采用邻接矩阵数组表示顶点之间相邻关系的存储结构。无向图的邻接矩阵数组一定一个对称矩阵。

6单选(2分)‍一个图的邻接矩阵是对称矩阵，则该图是（ ）。
A.以上都不对
B.有向图
C.无向图
D.无向图或有向图
正确答案：D
解析： D、有向图的邻接矩阵也可能是对称矩阵，如强连通图。

7单选(2分)‎在含有n个顶点e条边的不带权无向图的邻接矩阵中，零元素的个数为（ ）。
A.e
B.n²-2e
C.n²-e
D.2e
正确答案：B
解析： B、在含有n个顶点e条边的不带权无向图的邻接矩阵中，为0的元素恰好2e个，其他为0元素。

8单选(2分)‍若用邻接矩阵表示一个含有n个顶点不带权的有向图，则其中第i（0≤i≤n-1）列中包含的1的个数为（ ）。
A.图中顶点i的入度
B.图中顶点i的出度
C.图中边的数目
D.图中强连通分量的数目
正确答案：A
解析： A、不带权有向图的邻接矩阵表示中，第i（0≤i≤n-1）行中包含的1的个数为顶点i的出度，第i列行中包含的1的个数为顶点i的入度。

课本考据：在有向图中顶点的度分为入度和出度，以顶点j为终点的边数目，称为改顶点的入度。以顶点i为起点的边数目，称为改顶点的出度。

9单选(2分)​一个图的邻接表表示中有奇数个边节点，则该图是（ ）。
A.以上都不对
B.无向图或有向图
C.无向图
D.有向图
正确答案：D
解析： D、对于含有e条边的无向图，其邻接表表示中恰好有2e个边节点，所以一个图的邻接表表示中有奇数个边节点，则它一定是有向图。

10单选(2分)‏以下叙述中错误的是（ ）。
A.图的深度优先遍历算法是一个递归过程
B.图的深度优先遍历算法适合无向图
C.图的广度优先遍历算法适合有向图
D.图的深度优先遍历算法不适合有向图
正确答案：D
解析： D、图的深度优先遍历算法既适合无向图也适合有向图的遍历。

11单选(2分)‎如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是（ ）。
A.一棵树
B.连通图
C.完全图
D.有回路
正确答案：B
解析： B、对于无向图，从其中任一顶点出发进行一次广度优先遍历能够访问所有的顶点，表示所有顶点之间都有路径，所以它是连通图。

12单选(2分)‌对有n个顶点、e条边且使用邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）。
A.O(n)
B.O(e)
C.O(n*e)
D.O(n+e)
正确答案：D
解析： D、使用邻接表存储时，深度优先遍历过程恰好访问所有的头节点和边节点一次。

13单选(2分)‌对有n个顶点、e条边且使用邻接矩阵存储的有向图进行广度优先遍历，其算法的时间复杂度是（ ）。
A.O(n²)
B.O(nlog2n)
C.O(n*e)
D.O(n)
正确答案：A
解析： A、使用邻接矩阵存储时，广度优先遍历过程中找相邻的时间复杂度为O(n)，另要循环n次处理每个顶点。

14单选(2分)‏一个有向图G=(V，E)，V={0，1，2，3，4}，‏E={<0，1>，<1，2>，<0，3>，<1，2>，<1，4>，<2，4>，<4，3>}，‏现按深度优先遍历算法遍历，从顶点0出发，所得到的顶点序列是（ ）。
A.0，1，3，4，2
B.0，1，2，3，4
C.0，1，4，2，3
D.0，1，2，4，3
正确答案：D

15单选(2分)‍以下关于广度优先遍历的叙述中正确的是（ ）。
A.对任何有向图调用一次广度优先遍历算法便可访问所有的顶点
B.对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点
C.对一个强连通图调用一次广度优先遍历算法便可访问所有的顶点
D.广度优先遍历不适合有向图
正确答案：C
解析： C、强连通图中任何两个顶点之间都有路径，所以调用一次广度优先遍历算法便可访问所有的顶点。