第七章 图
一 单选题
1．在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为（ ）。
A s B s-1 C s+1 D n
2． 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为（ ）。 A n B s-1 C s+1 D 2s 3． 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（ ）。 A s B e C n+e D 2e 4． 在一个具有n个顶点的无向完全图中，所含的边数为（ ）。 A n B n(n-1) C n(n-1)/2 D n(n+1)/2 5． 在一个具有n个顶点的有向完全图中，所含的边数为（ ）。 A n B n(n-1) C n(n-1)/2 D n(n+1)/2 7． 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（ ）次深度优先搜索遍历的算法。 A k B 1 C k-1 D k+1 8． 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（ ）。 A n B n×e C e D 2×e 9． 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（ ）。 A n B n×e C e D 2×e 10．对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（ ）。 A k1 B k2 C k1- k2 D k1+ k2 11．在一个有向图的邻接表中，每个顶点单链表中结点的个数等于顶点的（ ）。 A 出边数 B 入边数 C 度数 D 度数减1 12．若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（ ）。 A A，B，C，F，D，E B A，C，F，D，E，B C A，B，D，C，F，E D A，B，D，F，E，C 13．若一个图的边集为{（A，B），（A，C），（B，D），（C，F），（D，E），（D，F）}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（ ）。 A A，B，C，F，D，E B A，B，D，E，F， C C A，B，D，C，E，F D A，C，B，F，D，E 14．若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（ ）。 A 1，2，5，4，3 B 1，2，3，4，5 C 1，2，5，3，4 D 1，4，3，2，5 15．若一个图的边集为{<1，2>，<1，4>，<2，5>，<3，1>，<3，5>，<4，3>}，则从顶点1开始对
该图进行深度优先搜索，得到的顶点序列可能为（ ）。 A 1，2，3，4，5 B 1，2，4，3，5 C 1，2，4，5，3 D 1，4，2，5，3 16．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个（ ）。 A 上三角矩阵 B 稀疏矩阵 C 对角矩阵 D 对称矩阵 17．一个有n个顶点和n条边的无向图一定是（ ）。 A 连通的 B 不连通的 C 无环的 D 有环的 18．为了实现图的广度优先遍历，其广度优先搜索算法使用的一个辅助数据结构为（ ）。 A 栈 B 队列 C 二叉树 D 树 19．若要把n个顶点连接为一个连通图，则至少需要（ ）条边。 A n B n+1 C n-1 D 2n 20．由一个具有n个顶点的连通图生成的最小生成树中，具有（ ）条边。 A n B n-1 C n+1 D 2n 21．已知一个有向图的边集为{，，，
ab得到的一种顶点序列为（ ）。 A a，c，e，d，b B a，c，d，b，e C a，d，c，e，b D a，b，c，e，d 24．对于图7-11中的无向图，若从顶点A出发按广度优先搜索遍历，则可能cd得到的一种顶点序列为（ ）。 A a，c，e，d，b B a，c，d，b，e C a，d，c，e，b D a，b，c，d，e e 25．设无向图的顶点个数为n，则该图最多有（ ）条边。
图 7-11 A n-1 B n(n-1)/2 C n(n+1)/2 D 0 26．一个有n个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。 A 0 B 1 C n-1 D n 【北京邮电大学2000二、5（20/8分）】 27．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。【哈尔滨工业大学2001二、3（2分）】 A 1/2 B 2 C 1 D 4 28．要连通具有n个顶点的有向图，至少需要（ ）条边。 A n-1 B n C n+1 D 2n 29．用邻接表存储图所用的空间大小（ ）。【北京交通大学2004一、7（2分）】 A 与图的顶点数和边数都有关 B 只与图的边数有关 C 只与图的顶点数有关 D 与边数的平方有关 30．下列哪一种图的邻接矩阵是对称矩阵？（ ）【北京交通大学2001一、11（2分）】 A 有向图 B 无向图 C AOV网 D AOE网
31．无向图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）}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 【南京理工大学2001一、14（1.5分）】 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，b 32．设如图7-22所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ） 【南京理工大学2000一、20（1.5分）】 aebdfc acfdeb aedfcb aefdcb aefdbc A 5个 B 4个 C 3个 D 2个
abecd图 7-22 f
33．在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（ ）。 A 顶点v的度 B 顶点v的出度
C 顶点v的入度 D 依附于顶点v的边数 【北京理工大学2004一、7（1分）】 34．关键路径是AOE网中（ ）。【中南大学2003一、10（1分）】 A 从始点到终点的最短路径 B 从始点到终点的最长路径
C 从始点到终点的边数最多的路径 D 从始点到终点的边数最少的路径 35．下列关于AOE网的叙述中，不正确的是（ ）。【北方交通大学1999一、7（3分）】 A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成
C 所有的关键活动提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完成 【北京工业大学1999一、1（2分）】【哈尔滨工业大学2004二、3（1分）】
二 填空题
1．一个有向图的顶点集为{a，b，c，d，e，f}，边集为{，，
8．图的逆邻接表存储结构只适用于（ ）图。
三 判断题
1．有e条边的无向图，在邻接表中有e个结点。（ ）
2．有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ） 3．强连通图的各顶点间均可达。（ ）
4．强连通分量是无向图的极大强连通子图。（ ） 5．连通分量指的是有向图中的极大连通子图。（ ）
6．对于任意一个图，从它的某个顶点进行一次先深或先广搜索可以访问到该图的每个顶点。（ ） 7．有n-1条边的图肯定都是生成树。（ ）
8．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ） 9．对一个无向图进行先深搜索时，得到的先深序列是唯一的。（ ） 10．有向图的邻接矩阵是对称的。（ ）
11．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是非对称矩阵。（ ）
12．邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（ ）
13．用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（ ）
14．一个带权的无向连通图的最小生成树的权值之和是唯一的。（ ） 15．最小代价生成树是唯一的。（ ）
16．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 17．采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环。（ ） 18．无环有向图才能进行拓扑排序。（ ） 19．有环图也能进行拓扑排序。（ ）
20．对一个AOV网，从源点到终点的路径最长的路径称作关键路径。（ ） 21．关键路径是AOE网中从源点到终点的最长路径。（ ）
A四 简答题
1．对于图7-12所示的有向图G1，请给出： （1）各顶点的入度和出度； （2）画出图的强连通分量； （3）邻接矩阵； DE （4）画出邻接表。
图 7-12 2．对于图7-17给出的有向图和无向图，分别给出其邻接矩阵、邻接表和逆邻接表，并计算每个顶点的度（对有向图需先确定入度和出度）。
BCV2V5V2V1V1V4V3V3（a） 有向图V6V4（b）无向图V5图 7-17 有向图和无向图 3．对于图7-1： （1）从顶点0出发，根据普里姆算法求出最小生成树的过程中，把依次得到的各条边按序写出来。 （2）根据克鲁斯卡尔算法求出最小生成树的过程中，把依次得到的各条边按序写出来。 4．在图7-16中的无向网，从顶点1出发按照Kruskal算法和Prim算法分别求出其最小生成树，并用图的序列来说明最小生成树的求解过程。
120611225图 7-1 无向带权图58156920103511316251084126图 7-16 无向网6374131172445
5．对于图7-18给出的无向网G2，分别给出 （1）邻接矩阵
（2）深度优先搜索遍历序列（分别从V1和V4开始）和深度优先生成树 （3）广度优先搜索遍历序列（分别从V1和V4开始）和广度优先生成树 （4）用Prim算法求得最小生成树的过程。 （5）用Kruskal算法求得最小生成树的过程。 6．图7-23所示的邻接表表示一个给定的无向图。【复旦大学1998年考研试题六（10分）】 （1）给出从顶点v1开始，对图G用深度优先搜索法进行遍历时的顶点序列； （2）给出从顶点v1开始，对图G用广度优先搜索法进行遍历时的顶点序列。