第七章图
一、选择题
1．一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学 1999 四、4 (4
分)】
A．n-1 B．n C．n+1 D．nlogn；
2．n个结点的完全有向图含有边的数目（）。【中山大学 1998 二、9 （2分）】
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
3．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所
有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学 2001 二、3 （2
分）】
A．1/2 B．2 C．1 D．4
4．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网
5. 下列说法不正确的是（）。【青岛大学 2002 二、9 （2分）】
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用
于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个
递归过程
二、判断题
1．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1997
一、4(1分）】
2. 有e条边的无向图，在邻接表中有e个结点。（）【南京理工大学 1998 二、5 （2
分）】
3．强连通图的各顶点间均可达。（）【北京邮电大学 2000 一、3 （1分）】
4．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）
【东南大学 2001 一、4 （1分）】【中山大学 1994 一、3 （2分）】
5．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）
【东南大学 2001 一、3 （1分）】【哈尔滨工业大学 1999 三、4】
6．需要借助于一个队列来实现DFS算法。（）【南京航空航天大学 1996 六、8 （1分）】
7. 最小代价生成树是唯一的。（）【山东大学 2001 一、5 （1分）】
8. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（）
【合肥工业大学 2000 二、7（1分）】
三、填空题
1．具有10个顶点的无向图，边的总数最多为_ ___。【华中理工大学 2000 一、7 （1分）】
2．G是一个非连通无向图，共有28条边，则该图至少有_____ _个顶点。
【西安电子科技大 2001软件一、8 （2分）】
3．N个顶点的连通图的生成树含有__ ____条边。【中山大学 1998 一、9 （1分）】
4．构造n个结点的强连通图，至少有__ ____条弧。【北京轻工业学院 2000 一、4（2分）】
5．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。【中科院计算所
1998 一、6（1分）】【中国科技大学1998 一、6（15/6分）】
6. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需___ __ _存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2分）】
四、应用题
1．（1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有
多少条边？
（2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少
有多少条边？
（3）．如果G3是一个具有n个顶点的弱连通有向图，那么G3最多有多少条边？G3最少
有多少条边？【复旦大学 1997 一（9分）】
2．如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线以
上？【清华大学 1999 一、5 （2分）】
3．对一个图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有
哪些？【北京航空航天大学 1998 一、7 （4分）】
4．一带权无向图的邻接矩阵如下图，试画出它的一棵最小生成树。
【浙江大学 1994 五 (8分)】
五、算法设计题
1．试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点V i到顶点V j的路径（i<>j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001 九（12分）】
2．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。【东南大学 1999 三（10分）】
1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧
关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）
第七章图 一、选择题 1．图中有关路径的定义是（ A ） A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ B ）条边。】 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（ D ）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 7．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A)。 A．5 B．6 C．8 D．9 9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A )。 A．逆拓扑有序 B．拓扑有序 C．无序的 10．下面结构中最适于表示稀疏无向图的是（ C ），适于表示稀疏有向图的是（ BDE ）。 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表 11．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网 12．从邻接阵矩可以看出，该图共有（B）个顶点；如果是有向图该图共有（B）条弧；如果是无向图，则共有（D）条边。 ①．A．9 B．3 C．6 D．1 E．以上答案均不正确 ②．A．5 B．4 C．3 D．2 E．以上答案均不正确 ③．A．5 B．4 C．3 D．2 E．以上答案均不正确 14．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m的路径相连，则只要检查（ C ）的第i行第j列的元素是否为零即可。 A．mA B．A C．A m D．Am-1 15.下列说法不正确的是（ C ）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程 16．无向图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)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ 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,b 17.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ D ） a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A．5个 B．4个 C．3个 D．2个 18.下图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是(C)，而进行广度优先遍历得到的顶点序列是（C）。 ①．A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确 ②．A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确 19．下面哪一方法可以判断出一个有向图是否有环（AB）： A．深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 20.在图采用邻接表存储时，求最小生成树的 Prim算法的时间复杂度为( B )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 21.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ C），下面步骤重复n-1次: a：（ A）；b：（ B）；最后：（A）。 （1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边 （2）．A.选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大
第七章：图练习题 一、选择题 1、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。 A、5 B、6 C、7 D、8 3、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。 A、线性图 B、无向完全图 C、无向图 D、简单图 4、具有4个顶点的无向完全图有（）条边。 A、6 B、12 C、16 D、20 5、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点 A、6 B、7 C、8 D、9 6、存储稀疏图的数据结构常用的是（）。 A、邻接矩阵 B、三元组 C、邻接表 D、十字链表 7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。 A、n B、(n-1)2 C、(n+1)2 D、n2 8、设连通图G的顶点数为n，则G的生成树的边数为（）。 A、n-1 B、n C、2n D、2n-1 9、n个顶点的无向图的邻接表中结点总数最多有（）个。 A、2n B、n C、n/2 D、n(n-1) 10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。 A、n B、n+1 C、n-1 D、2n E、e/2 F、e G、2e H、n+e 11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。 A、顶点v的度 B、顶点v的出度 C、顶点v 的入度 D、依附于顶点v的边数 12、已知一个图，若从顶点a出发进行深度和广度优先搜索遍历，则可能得到的顶点序列分别为（）和（） （1）A、abecdf B、acfebd C、acebfd D、acfdeb （2）A、abcedf B、abcefd C、abedfc D、acfdeb 13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的 （）和（）。 A、中序遍历 B、先序遍历 C、后序遍历 D、层次遍历 14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。 A、v1,v2,v3,v4,v5 B、v1,v3,v2,v4,v5 C、v1,v2,v3,v5,v4 D、v1,v4,v3,v5,v2
第七章图 一、选择题 1．一个n个顶点的连通无向图，其边的个数至少为（）。【浙江大学 1999 四、4 (4 分)】 A．n-1 B．n C．n+1 D．nlogn； 2．n个结点的完全有向图含有边的数目（）。【中山大学 1998 二、9 （2分）】 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 3．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所 有顶点的入度之和等于所有顶点出度之和的（）倍。【哈尔滨工业大学 2001 二、3 （2 分）】 A．1/2 B．2 C．1 D．4 4．下列哪一种图的邻接矩阵是对称矩阵？（）【北方交通大学 2001 一、11 （2分）】A．有向图 B．无向图 C．AOV网 D．AOE网 5. 下列说法不正确的是（）。【青岛大学 2002 二、9 （2分）】 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用 于有向图 B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个 递归过程 二、判断题 1．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（）【中科院软件所1997 一、4(1分）】 2. 有e条边的无向图，在邻接表中有e个结点。（）【南京理工大学 1998 二、5 （2 分）】 3．强连通图的各顶点间均可达。（）【北京邮电大学 2000 一、3 （1分）】 4．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（） 【东南大学 2001 一、4 （1分）】【中山大学 1994 一、3 （2分）】 5．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（） 【东南大学 2001 一、3 （1分）】【哈尔滨工业大学 1999 三、4】 6．需要借助于一个队列来实现DFS算法。（）【南京航空航天大学 1996 六、8 （1分）】 7. 最小代价生成树是唯一的。（）【山东大学 2001 一、5 （1分）】 8. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（） 【合肥工业大学 2000 二、7（1分）】 三、填空题 1．具有10个顶点的无向图，边的总数最多为_ ___。【华中理工大学 2000 一、7 （1分）】 2．G是一个非连通无向图，共有28条边，则该图至少有_____ _个顶点。 【西安电子科技大 2001软件一、8 （2分）】 3．N个顶点的连通图的生成树含有__ ____条边。【中山大学 1998 一、9 （1分）】 4．构造n个结点的强连通图，至少有__ ____条弧。【北京轻工业学院 2000 一、4（2分）】 5．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。【中科院计算所 1998 一、6（1分）】【中国科技大学1998 一、6（15/6分）】 6. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需___ __ _存放被访问的结点以实现遍历。【南京理工大学 1999 二、9 （2分）】 四、应用题
第七章图 一、判断题 （）1. 在每个AOE网络中只有一条关键路径。 （）2. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（）3．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。 （）4．图的深度优先搜索序列和广度优先搜索序列不是唯一的。 （）5. 对AOV网进行拓扑排序时，如果存在从Vi到Vj的路径，则在拓朴序列中，结点Vi一定排在结点Vj的前面。 二、单项选择题 1. 在一个有向图的邻接矩阵表示中，删除一条边
C）将A[k][i]置为1 D）将A[i][k]和A[k][i]同时置为1 三、填空题（在横线处填写合适内容） 1. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个________ 上，才会被加入到生成树中。 2．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将累加。 3．已知有向图的邻接矩阵，要计算i号结点的出度，计算方法是：将累加。 四、综合题 1.用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？ 2.用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 3.有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。 4.对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题：图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？ 5.用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？ 6.设有一有向图为G=(V，E)。其中，V={v0, v1, v2, v3}，E={
第七章图 一．选择题 1．任何一个无向连通图的最小生成树________。 A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 2．下列算法中，________算法用来求图中每对顶点之间的最短路径。A．Dijkstra B．Floyed C．Prim D．Kruskal 3．由N个顶点组成的有向图，最多可以有________条边。 A．N*N B．N（N+1） C．N（N-1） D．N(N-1)/2 4．关键路径是结点网络中________。 A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 5．在一个图中，所有顶点的度数之和等于所有边数的________倍。 A．2 B．3 C．1 D．1.5 6. 下面关于图的存储的叙述中正确的是________ 。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 7. AOV 网是一种________。 A．有向图 B．无向图 C．无向无环图 D．有向无环图 8. 在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有 n 个顶点的有向完全图中，包含有 ________ 条边。 A．n+2 B．n(n-1) C．n2 D．2n 9. 设完全无向图中有n个顶点，则该完全无向图中有________条边。 A．n(n-1)/2 B．n(n-1) C．n(n+1)/2 D．(n-1)/2 10.设有向无环图 G 中的有向边集合 E={<1，2> ，<2，3>，<3，4> ，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是________。 A．1，2，3，4 B．2，3，4，1 C．1，4，2，3 D．1，2，4，3 11.设某无向图有n个顶点，则该无向图的邻接表中有________个表头结点。A．2n B．n C．n/2 D．n(n-1) 12.设无向图G 中有n个顶点，则该无向图的最小生成树上有________条边。A．n B．n-1 C．2n D．2n-1 13.设无向图G 中的边的集合E={(a ，b) ，(a，e)，(a，c)，(b，e)，(e，d) ，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为________。 A．aedfcb B．acfebd C．aebcfd D．aedfbc 14.有n个顶点 e 条边的无向图 G,它的邻接表中的表结点总数是________。A．2n B．n C．2e D．e
第七章 图的基本概念 一、 单项选择题 1. 设V ＝{a,b,c,d},与V 能构成强连通图的边集E ＝(A ) (A) {
第七章 图 7.1、 ★画出图1的存储结构(1)邻接矩阵(2)邻接表(3)逆邻接表 (4)十字链表(5)邻接多重表。 7.2、★在图1中，从顶点A 出发深度优先搜索得（__），从B 出发广度优先搜索得（__）。在图2中从顶点A 出发深度优先搜索和广度优先搜索分别得（__）和（__）。 7.3、★对图2进行拓扑排序得（__）。 7.4、★用普里姆算法计算图3的最小生成树（写出过程）。 7.5、★用克鲁斯卡尔算法计算图3的最小生成树。计算该生成树的代价。 7.6、★设图4为某工程的AOE 网，弧上的权值表示活动(i,j)所用的时间（天）。问：整个工程需要多少天才能完成？请计算工程中的关键路径。 7.7、★用迪杰斯特拉算法计算图3和图5中顶点A 到其他 A B C D E 图1 A B C D E 图3 F 4 3 2 4 1 2 4 1 3 3 4
各顶点的最短路径（写出过程）。 7.8、 用弗洛伊德算法计算图5中各个顶点之间的最短路径。 （本题满分为10分）试利用Dijkstra 算法求下图中从顶点1到其它各顶点间的最短路径，写出执行算法过程中各步的状态。 已知一个有向图的邻接矩阵表示，计算第i 个结点的出度的方法是求矩阵第i 列非零元的个数。 ( ) （本题10分）下面画出了一个AOE 网表示各工序之间的 优先关系和各工序所需时间，要求： 1. 列出各事件的最早最迟发生时间 2. 求出该AOE 网中的关键路径，及完成该工程所需要的最短时间。 写出求从某个源点到其余各顶点最短路径
的Dijkstra算法。要求说明主要的数据结构及其作用，最后针对所给有向图，利用该算法，求V0到各顶点的最短距离和路线，即填写下表： 终点从V0到到各终点的dist的值和最短距离和路线 V1 V2 V3 V4 V5 Vj V2 V3 V4 V5 1.一个有n个结点的图，最少有（）个连通分量，最多有 （）个连通分量。A．0 B．1 C．n-1 D．n 2.在一个无向图中，所有顶点的度数之和等于所有边数（） 倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 3.从邻接矩阵可以看出，该图共有（）个顶点；如 果是有向图该图共有（）条弧；如果是无向图，则共有（）条边。 4.下列说法不正确的是（）。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．图的深度遍历不适用于有向图 C．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程