7.1选择题1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（）条边。
A）n-1B）n(n-1)/2C）n(n+1)/2【答案】B3．连通分量指的是（）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2【答案】D5．关键路径是（）A）AOE网中从源点到汇点的最长路径B）AOE网中从源点到汇点的最短路径C）AOV网中从源点到汇点的最长路径D）n2D）n*（n-1）D）AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（）A）入度B）出度C）入度与出度之和D）（入度+出度）/2【答案】C7．有e条边的无向图，若用邻接表存储，表中有（）边结点。
A）e B）2eC）e-1D）2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树【答案】A10．存储无向图的邻接矩阵一定是一个（）A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A）B）1C）2D）4【答案】B12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为（A）O(n)B）O(n+e)C）O(n2)D）O(n3)）【答案】B13．下列关于AOE网的叙述中，不正确的是（）A）关键活动不按期完成就会影响整个工程的完成时间B）任何一个关键活动提前完成，那么整个工程将会提前完成C）所有的关键活动提前完成，那么整个工程将会提前完成D）某些关键活动提前完成，那么整个工程将会提前完成【答案】B14．具有10个顶点的无向图至少有多少条边才能保证连通（）A）9B）10C）11D）12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A）e B）2eC）n2-e D）n2-2e【答案】D7.2填空题1．无向图中所有顶点的度数之和等于所有边数的_____________倍。
、选择题（每小题 1 分，共 10分）1. 一个 n 个顶点的连通无向图，其边的个数至少为（ C ）。
A.n+l B.n C.n-l D.2n2. 下列哪一种图的邻接矩阵是对称矩阵（ B ）。
A. 有向图 B. 无向图 C.AOV 网 D.AOE 网5. 无 向 图 G=（V,E ）, 其 中 ： V={a,b,c,d,e,f}, E={（a,b ）,（a,e ）,（a,c ）,（b,e ）,（c,f ）, （f,d ）,（e,d ）} ，由顶点 a 开始对该图进行深度优先遍历， 得到的顶点序列正确的是 （ D ）。
A. a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b6. 用邻接表表示图进行广度优先遍历时，通常是采用（ B ）来实现算法的。
A. 栈 B. 队列 C. 树 D. 图7. 以下数据结构中，哪一个是线性结构（ D ）。
A. 广义表 B. 二叉树 C. 图 D. 栈8. 下面哪一方法可以判断出一个有向图是否有环（回路） （ B ）。
A. 最小生成树B. 拓扑排序C. 求最短路径D. 求关键路径 9. 在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。
10. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B ）倍。
A. 1/2B. 1C. 2D. 411. 有 8 个顶点无向图最多有（ B ）条边。
A. 14 B. 28 C. 56 D. 11212. 有 8 个顶点无向连通图最少有（ C ）条边。
A. 5 B. 6 C. 7 D. 813. 有 8个顶点有向完全图有（ C ）条边。
A. 14 B. 28 C. 56 D. 11214. 下列说法不正确的是（ A ）。
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次 C. 图的深度遍历不适用于有向图B. 遍历的基本算法有两种：深度遍历和广度遍历 D •图的深度遍历是一个递归过程 二、判断题（每小题 1 分，共 10分）1. n 个顶点的无向图至多有 n （n-1） 条边。
第7章 《图》习题参考答案一、单选题（每题1分，共16分）（ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A ．1/2 B. 1 C. 2 D. 4 （B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。
A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。
A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。
A ．14 B. 28 C. 56 D. 112 （B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A ．栈 B. 队列 C. 树 D. 图 （）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2C. 0 4 2 3 1 6 5D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A ．0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 1 3 4 2 5 6D. 0 3 6 1 5 4 2⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（A）12. 深度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（D）13. 广度优先遍历类似于二叉树的A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历（A）14. 任何一个无向连通图的最小生成树A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在（注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一）二、填空题（每空1分，共20分）1. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。
第七章图一、选择题1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。
A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
