参考教材：数据结构教程（Java语言描述) 作者：李春葆
1 . 容易 （4分）连通图的生成树包含了图中所有顶点。
正确
2 . 普通 （4分）对n个顶点的连通图G来说，如果其中的某个子图有n个顶点、n-1条边，则该子图一定是G的生成树。
错误
这样的子图不一定是连通的。
3 . 容易 （4分）一个连通图的生成树是唯一的。
错误
一个连通图的生成树可能有多棵。
4 . 容易 （4分）n个顶点的连通图的生成树有（ ）条边。
A. n
B. n-1
C. n+1
D. 不确定
5 . 普通 （3分）如果具有n个顶点的图恰好是一个环，则它有（ ）棵生成树。
A. n-1
B. n
C. n+1
D. 2n
如果图恰好是一个环，对于图中每个顶点，都有顺时针和逆时针方向两棵生成树，总计2n棵生成树。
6 . 普通 （3分）若一个具有n个顶点和e条边的无向图是一个森林（n>e），则该森林必有（ ）棵树。
A. e
B. n
C. n-e
D. 1
设该森林有m棵树，结点个数分别为n1、n2、…、nm，则总顶点数n=n1+n2+…+nm，第i棵树的边数=ni-1，总边数=(n1-1)+(n2-1)+…+(nm-1)=n-m=e，所以m=n-e。
7 . 容易 （3分）n个顶点的无向图至多有n(n-1)条边。
错误
n个顶点的无向图至多有n(n-1)/2条边。
8 . 普通 （3分）在有向图中，如果顶点i到顶点j有路径，而顶点i到顶点k没有路径，则顶点j到顶点k也没有路径。
正确
如果顶点j到顶点k有路径，则顶点i有一条通过顶点j到达顶点k的路径，与题中条件矛盾。
9 . 容易 （3分）一个图中的简单路径是指该路径上的边不重复出现。
错误
10 . 普通 （3分）在无向图中，如果顶点i到顶点j有路径，而顶点j到顶点k没有路径，则顶点i到顶点k也没有路径。
正确
顶点i和顶点j属一个连通分量，而顶点k属另一个连通分量，所以顶点i到顶点k没有路径。
11 . 容易 （3分）图是一种结点之间无层次关系的线性结构。
错误
图是一种非线性结构。
12 . 容易 （3分）一个有n个顶点的有向图最多有（ ）条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
当为完全有向图时边数最多。
13 . 容易 （3分）在一个图中，每个顶点的前趋顶点和后继顶点数可以有（ ）。
A. 1个
B. 2个
C. 任意多个
D. 0个
图中顶点之间是多对多的相邻关系。
14 . 容易 （3分）在一个无向图中，所有顶点的度之和等于边数的（ ）倍。
A. 1/2
B. 1
C. 2
D. 4
在无向图中，一条边计入两个顶点的度数。
15 . 容易 （3分）在一个具有n个顶点的无向连通图中至少有（ ）条边。
A. n
B. n+l
C. n-1
D. n/2
树图是边数最少的连通图，其边数=n-1。
16 . 容易 （3分）一个有n个顶点的无向图最多有（ ）条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
17 . 容易 （3分）在一个无向图中，所有顶点的度之和等于边数的______ 倍。
A. 1/2
B. 1
C. 2
D. 4
18 . 容易 （3分）一个图的邻接矩阵是对称矩阵，则该图一定是______。
A. 无向图
B. 有向图
C. 无向图或有向图
D. 以上都不对
19 . 容易 （3分）一个具有n（n≥1）个顶点的有向图，其强连通分量个数最少有______ 个。
A. 0
B. 1
C. n-1
D. n
20 . 容易 （3分）一个具有n（n≥1）个顶点的图，最多有 个连通分量。
A. 0
B. 1
C. n-1
D. n
21 . 容易 （3分）一个有n个顶点的无向图，其中边数大于n-1，则该图必是______。
A. 完全图
B. 连通图
C. 非连通图
D. 以上都不对
22 . 容易 （3分）在一个具有n个顶点的有向图中，构成强连通图时至少有______ 条边。
A. n
B. n+l
C. n-1
D. n/2
23 . 容易 （3分）在一个具有n个顶点的无向连通图中至少有______ 条边。
A. n
B. n+l
C. n-1
D. n/2
24 . 容易 （3分）一个有n个顶点的有向图最多有______ 条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
25 . 容易 （3分）一个有n个顶点的无向图最多有______ 条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
26 . 容易 （3分）一个图的邻接矩阵不是对称矩阵，则该图可能是______。
A. 无向图
B. 有向图
C. 无向图或有向图
D. 以上都不对
27 . 容易 （3分）一个图的邻接矩阵中非0非∞的元素个数为奇数，则该图可能是______。
A. 有向图
B. 无向图
C. 无向图或有向图
D. 以上都不对
28 . 容易 （3分）对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是______。
A. n
B. (n-1)^2
C. n-1
D. n^2
29 . 容易 （3分）对于一个具有n个顶点e条边的不带权无向图，若采用邻接矩阵表示，其中非零元素个数是______。
A. n
B. 2n
C. e
D. 2e
30 . 容易 （3分）用邻接表存储图所用的空间大小______。
A. 与图的顶点和边数有关
B. 只与图的边数有关
C. 只与图的顶点数有关
D. 与边数的平方有关
31 . 容易 （3分）在有向图的邻接表表示中，顶点v的边单链表中结点个数等于______。
A. 顶点v的度
B. 顶点v的出度
C. 顶点v的入度
D. 依附于顶点v的边数
32 . 容易 （3分）在有向图的邻接表表示中，顶点v在边单链表中出现的次数是______。
A. 顶点v的度
B. 顶点v的出度
C. 顶点v的入度
D. 依附于顶点v的边数