第7章图习题及参考答案

《数据结构》期末复习题及参考答案- 第7章图//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// 注意：做复习题时，请结合阅读教材，钻研教材，参考课件////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、以下数据结构中，哪种具有非线性结构？A．栈B．队列C．双向链表D．十字链表2、下面关于图的存储的叙述中正确的是（）。

A.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

B.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关。

C.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。

D.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关3、在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的（）A.先根遍历B.中根遍历C.后根遍历D.按层次遍历4、图的广度优先遍历算法类似于树的（）。

A. 中根遍历B. 先根遍历C. 后根遍历D. 按层次遍历5、设无向图的顶点个数为n，则该图最多有（）条边。

A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．06、设有n个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A．n-1 B．n C．n+1 D．nlogn；7、一个含有n个顶点的非连通图，则（）：A．它的边一定不大于n-1 B．它的边一定不大于nC．它的边一定小于n-1 D．它的边一定大于08、要连通具有n个顶点的有向图，至少需要（）条边。

、选择题（每小题 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．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（）A） O(n) B） O(n+e) C） O(n*n) D） O(n*n*n)【答案】B2．设无向图的顶点个数为n，则该图最多有（）条边。

A）n-1 B）n(n-1)/2 C） n(n+1)/2 D）n2【答案】B3．连通分量指的是（）A）无向图中的极小连通子图B）无向图中的极大连通子图C）有向图中的极小连通子图D）有向图中的极大连通子图【答案】B4．n个结点的完全有向图含有边的数目（）A）n*n B）n（n+1）C）n/2 D）n*（n-1）【答案】D5．关键路径是（）A） AOE网中从源点到汇点的最长路径B） AOE网中从源点到汇点的最短路径C） AOV网中从源点到汇点的最长路径D） AOV网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的（）A）入度 B）出度 C）入度与出度之和 D）（入度+出度）/2 【答案】C7．有e条边的无向图，若用邻接表存储，表中有（）边结点。

A） e B） 2e C） e-1 D） 2(e-1)【答案】B8．实现图的广度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】B9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈 B）队列 C）二叉树 D）树【答案】A10．存储无向图的邻接矩阵一定是一个（）A）上三角矩阵 B）稀疏矩阵 C）对称矩阵 D）对角矩阵【答案】C11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A） 1/2 B）1 C） 2 D） 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） 9 B）10 C） 11 D） 12【答案】A15．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A） e B）2e C） n2-e D）n2-2e【答案】D16.对于一个具有n个顶点和e条边的无向图，如果采用邻接表来表示，则其表头向量的大小为。

第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. 图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。

第7章图练习题与答案第七章图一、单选题（C）1.在一个图中，所有顶点的度数之和等于图的边数的倍。

A．1/2B.1C.2D.42.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。

A．1/2B.1C.2D.4（B）3.有8个结点的无向图最多有条边。

A．14B.28C.56D.112（A）一个n个顶点的连通无向图，其边的个数至少为（）。

A．n-1B．nC．n+1D．nlogn；（C）5.有8个结点的有向完全图有条边。

A．14B.28C.56D.112（B）6.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A．栈B.队列C.树D.图（A）7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A．栈B.队列C.树D.图8.下面关于求关键路径的说法不正确的是（C）。

A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上9.已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历0111101100100110001001100110101101000011011100010的结点序列是（D）A．0243156B.0135642C.0423165D.013425610、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>，<4,2>}，则数据结构A是（C）。

(A)线性结构(B)树型结构(C)图型结构(D)集合（C）11.已知图的邻接矩阵同上题9，根据算法，则从顶点0出发，按广度优先遍历的结点序列是A．0243165B.0135642C.0123465D.01234563.已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（D）A．0132B.0231C.0321D.0123（A）13.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是A．0321B.0123C.0132D.0312（A）14.深度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（D）15.广度优先遍历类似于二叉树的A．先序遍历B.中序遍历C.后序遍历D.层次遍历（D）16、下面结构中最适于表示稀疏无向图的是。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

第七章：图练习题一、选择题1、一个有n个顶点的无向图最多有（）条边。

A、nB、n(n-1)C、n(n-1)/2D、2n2、具有6个顶点的无向图至少有（）条边才能保证是一个连通图。

A、5B、6C、7D、83、具有n个顶点且每一对不同的顶点之间都有一条边的图被称为（）。

A、线性图B、无向完全图C、无向图D、简单图4、具有4个顶点的无向完全图有（）条边。

A、6B、12C、16D、205、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点A、6B、7C、8D、96、存储稀疏图的数据结构常用的是（）。

A、邻接矩阵B、三元组C、邻接表D、十字链表7、对一个具有n个顶点的图，采用邻接矩阵表示则该矩阵的大小为（）。

A、nB、(n-1)2C、(n+1)2D、n28、设连通图G的顶点数为n，则G的生成树的边数为（）。

A、n-1B、nC、2nD、2n-19、n个顶点的无向图的邻接表中结点总数最多有（）个。

A、2nB、nC、n/2D、n(n-1)10、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表向量的大小为（），所有顶点邻接表的结点总数为（）。

A、nB、n+1C、n-1D、2nE、e/2F、eG、2eH、n+e11、在有向图的邻接表存储结构中，顶点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、acfdeb13、采用邻接表存储的图的深度和广度优先搜索遍历算法类似于二叉树的（）和（）。

A、中序遍历B、先序遍历C、后序遍历D、层次遍历14、已知一有向图的邻接表存储结构如下图所示，分别根据图的深度和广度优先搜索遍历算法，从顶点v1出发，得到的顶点序列分别为（）和（）。

第7章图二.判断题部分答案解释如下。

2. 不一定是连通图，可能有若干连通分量 11. 对称矩阵可存储上（下）三角矩阵14．只有有向完全图的邻接矩阵是对称的 16. 邻接矩阵中元素值可以存储权值21. 只有无向连通图才有生成树 22. 最小生成树不唯一，但最小生成树上权值之和相等26. 是自由树，即根结点不确定35. 对有向无环图，拓扑排序成功；否则，图中有环，不能说算法不适合。

42. AOV网是用顶点代表活动，弧表示活动间的优先关系的有向图,叫顶点表示活动的网。

45. 能求出关键路径的AOE网一定是有向无环图46. 只有该关键活动为各关键路径所共有，且减少它尚不能改变关键路径的前提下，才可缩短工期。

48．按着定义，AOE网中关键路径是从“源点”到“汇点”路径长度最长的路径。

自然，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

三．填空题1.有n个顶点，n-1条边的无向连通图2.有向图的极大强连通子图3. 生成树9. 2(n-1) 10. N-1 11. n-1 12. n 13. N-1 14. n15. N16. 3 17. 2（N-1） 18. 度出度 19. 第I列非零元素个数 20.n 2e21.(1)查找顶点的邻接点的过程 (2)O(n+e) (3)O(n+e) (4)访问顶点的顺序不同 (5)队列和栈22. 深度优先 23.宽度优先遍历 24.队列25.因未给出存储结构，答案不唯一。

本题按邻接表存储结构，邻接点按字典序排列。

25题（1） 25题（2） 26.普里姆（prim ）算法和克鲁斯卡尔（Kruskal ）算法 27.克鲁斯卡尔28.边稠密 边稀疏 29. O(eloge ） 边稀疏 30.O(n 2） O(eloge) 31.(1）（V i ，V j ）边上的权值 都大的数 （2）1 负值 （3）为负 边32.(1)n-1 (2)普里姆 (3)最小生成树 33.不存在环 34.递增 负值 35.16036.O(n 2） 37. 50，经过中间顶点④ 38. 75 39.O(n+e ）40.(1）活动 （2）活动间的优先关系 （3）事件 （4）活动 边上的权代表活动持续时间41.关键路径 42.（1）某项活动以自己为先决条件 （2）荒谬 （3）死循环 43.（1）零 （2）V k 度减1，若V k 入度己减到零，则V k 顶点入栈 （3）环44.（1）p<>nil (2)visited[v]=true (3)p=g[v].firstarc (4)p=p^.nextarc45.(1)g[0].vexdata=v (2)g[j].firstin (3)g[j].firstin (4)g[i].firstout (5)g[i].firstout (6)p^.vexj (7)g[i].firstout (8)p:=p^.nexti (9)p<>nil (10)p^.vexj=j(11)firstadj(g,v 0) (12)not visited[w] (13)nextadj(g,v 0,w)46.(1)0 (2)j (3)i (4)0 (5)indegree[i]==0 (6)[vex][i] (7)k==1 (8)indegree[i]==047.(1)p^.link:=ch[u ].head (2)ch[u ].head:=p (3)top<>0 (4)j:=top (5)top:=ch[j].count(6)t:=t^.link48.（1）V1 V4 V3 V6 V2 V5(尽管图以邻接表为存储结构，但因没规定邻接点的排列，所以结果是不唯一的。

第7章习题一、单项选择题1.在无向图中定义顶点的度为与它相关联的（）的数目。

A. 顶点B. 边C. 权D. 权值2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。

A. 顶点序列B. 边序列C. 权值总和D. 边的条数3.图的简单路径是指（）不重复的路径。

A. 权值B. 顶点C. 边D. 边与顶点均4.设无向图的顶点个数为n，则该图最多有（）条边。

A. n-1B. n(n-1)/2C. n(n+1)/2D. n(n-1)5.n个顶点的连通图至少有（）条边。

A. n-1B. nC. n+1D. 06.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。

A. 3B. 2C. 1D. 1/27.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。

A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵8.图的深度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次9.图的广度优先搜索类似于树的（）次序遍历。

A. 先根B. 中根C. 后根D. 层次10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）。

A. 重边B. 有向环C. 回路D. 权值重复的边11.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。

A. 非零B. 非整C. 非负D. 非正12.设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 ? V2，E1 ? E2，则称（）。

A. G1是G2的子图B. G2是G1的子图C. G1是G2的连通分量D. G2是G1的连通分量13.有向图的一个顶点的度为该顶点的（）。

A. 入度B. 出度C. 入度与出度之和D. (入度﹢出度))／214.一个连通图的生成树是包含图中所有顶点的一个（）子图。

A. 极小B. 连通C. 极小连通D. 无环15.n (n＞1) 个顶点的强连通图中至少含有（）条有向边。

第七章习题答案7.1.1 指出下列存储系统各具有多少个存储单元，至少需要几根地址线和数据线。

（1）64K×1 （2）256K×4 （3）lM×1 （4）128K×8解：求解本题时，只要弄清以下几个关系就能很容易得到结果：存储单元数=字数×位数地址线根数（地址码的位数）n与字数N的关系为：N=2n数据线根数＝位数（1）存储单元〓64K×1〓64K（注：lK＝1024）；因为，64K〓2’。

，即亢〓16，所以地址线为16根；数据线根数等于位数，此处为1根。

同理得：（2）1M个存储单元，18根地址线，4根数据线。

（3）1M个存储单元，18根地址线，1根数据线。

！＿（4）lM个存储单元，17根地址线，8根数据线。

7.1.2 设存储器的起始地址为全0，试指出下列存储系统的最高地址为多少？（1）2K×1 （2）16K×4 （3）256K×32解：因为存储系统的最高地址＝字数十起始地址一1，所以它们的十六进制地址是：（1）7FFH （2）3FFFH （3）3FFFFH ＇7，2．4 一个有1M×1位的DRAM，采用地址分时送人的方法，芯片应具有几条地址线？解：由于1M=210×210，即行和列共需20根地址线。

所以，采用地址分时送人的方法，芯片应具有10根地址线。

7．2．5 试用一个具有片选使能CE、输出使能OE、读写控制WE、容量为8 K×8位的sRAM 芯片，设计一个16K×16位的存储器系统，试画出其逻辑图。

解：采用8K×8位的sRAM构成16K×16位的存储器系统，必须同时进行字扩展和位扩展。

用2片8K×8位的芯片，通过位扩展构成8K×16位系统，此时需要增加8根数据线。

要将8K×16位扩展成16K×16位的存储器系统，还必须进行字扩展。