第七章图一、选择题1图中有关路径的定义是（） 。 【北方交通大学 2001 一、 24 （2 分） 】A由顶点和相邻顶点序偶构成的边所形成的序列 B 由不同顶点所形成的序列C由不同边所形成的序列 D上述定义都不是2设无向图的顶点个数为n，则该图最多有（）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En23一个 n 个顶点的连通无向图，其边的个数至少为（）。An-1 Bn Cn+1 Dnlogn ；4要连通具有n 个顶点的有向图，至少需要（）条边。An-l Bn Cn+l D2n 5n 个结点的完全有向图含有边的数目（） 。An*n n（n） Cn2 Dn*（nl ）6一个有n 个结点的图，最少有（）个连通分量，最多有（）个连通分量。A0 B1 Cn-1 Dn 7在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A1/2 B 2 C1 D4 8用有向无环图描述表达式(A+B)* （ （A+B ）/A） ，至少需要顶点的数目为( )。A5 B6 C8 D9 9用 DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ( )。A逆拓扑有序 B拓扑有序 C无序的10下面结构中最适于表示稀疏无向图的是（） ，适于表示稀疏有向图的是（） 。A邻接矩阵 B逆邻接表 C邻接多重表 D十字链表 E邻接表11下列哪一种图的邻接矩阵是对称矩阵？（）A有向图 B无向图 CAOV网 DAOE网12从邻接阵矩010101010A可以看出，该图共有（）个顶点；如果是有向图该图共有（）条弧；如果是无向图，则共有（）条边。 A9 B3 C6 D1 E以上答案均不正确 A5 B4 C3 D2 E以上答案均不正确 A5 B4 C3 D2 E以上答案均不正确13当一个有N个顶点的图用邻接矩阵A 表示时，顶点Vi 的度是（） 。AnijiA1, Bn1jj, iA CniijA1, DnijiA1,+ n1ji , jA14用相邻矩阵A表示图，判定任意两个顶点Vi 和 Vj 之间是否有长度为m 的路径相连，则只要检查（）的第 i 行第 j 列的元素是否为零即可。AmA BA CAm DAm-1 15. 下列说法不正确的是（） 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - abedcfA图的遍历是从给定的源点出发每一个顶点仅被访问一次 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)，对该图进行深度优先遍历，得到的顶点序列正确的是（） 。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 17. 设图如右所示，在下面的5 个序列中，符合深度优先遍历的序列有多少？（）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 A5 个 B 4 个 C3 个 D2 个第 17 题图第 18 题图18. 下图中给出由7 个顶点组成的无向图。从顶点1 出发，对它进行深度优先遍历得到的序列是 ( ) ，而进行广度优先遍历得到的顶点序列是（ ） 。 A1354267 B1347652 C1534276 D1247653 E以上答案均不正确 A1534267 B1726453 Cl354276 D1247653 E以上答案均不正确19下面哪一方法可以判断出一个有向图是否有环（回路）：A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径20. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。A. O(n) B. O(n+e) C. O(n2) D. O(n3) 21. 下面是求连通网的最小生成树的prim 算法： 集合 VT， ET分别放顶点和边， 初始为（ 1 ） ，下面步骤重复n-1 次: a ： （ 2 ） ；b： （ 3 ） ；最后：（ 4 ） 。（1） AVT，ET为空 BVT为所有顶点， ET 为空 CVT为网中任意一点，ET为空 DVT为空， ET为网中所有边（2） A. 选 i 属于 VT，j 不属于 VT，且（ i ，j ）上的权最小 B选 i 属于 VT，j 不属于 VT，且（ i ，j ）上的权最大 C选 i 不属于 VT ，j 不属于 VT，且（ i ，j ）上的权最小 D选 i 不属于 VT ，j 不属于 VT，且（ i ，j ）上的权最大（3） A顶点 i 加入 VT ， （i,j）加入 ET B. 顶点 j 加入 VT， （i,j）加入 ET C. 顶点 j 加入 VT ， （i,j）从 ET中删去 D顶点 i,j加入 VT， （ i,j）加入ET （4） AET 中为最小生成树 B不在 ET中的边构成最小生成树 CET中有 n-1 条边时为生成树，否则无解 D ET中无回路时，为生成树，否名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 则无解22. (1). 求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2). 利用 Dijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3) ； （图用邻接矩阵表示）(3). Floyd 求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是（） 。A(1),(2),(3) B (1) C(1),(3) D (2),(3) 23当各边上的权值( )时， BFS算法可用来解决单源最短路径问题。A均相等 B均互不相等 C不一定相等24. 求解最短路径的Floyd 算法的时间复杂度为( )。AO（n） B. O（n+c） C. O（n*n） D. O（n*n*n ）25已知有向图G=(V,E) ，其中 V=V1,V2,V3,V4,V5,V6,V7，E=,G 的拓扑序列是（） 。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V726若一个有向图的邻接距阵中, 主对角线以下的元素均为零, 则该图的拓扑有序序列（） 。A存在 B 不存在27一个有向无环图的拓扑排序序列（）是唯一的。A一定 B不一定28. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（） 。AG中有弧 BG中有一条从Vi 到 Vj 的路径CG中没有弧 DG中有一条从Vj 到 Vi 的路径29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n) 30. 关键路径是事件结点网络中（） 。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路31. 下面关于求关键路径的说法不正确的是（） 。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上32下列关于AOE网的叙述中，不正确的是（） 。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - D某些关键活动提前完成，那么整个工程将会提前完成二、判断题1. 树中的结点和图中的顶点就是指数据结构中的数据元素。（）2在 n 个结点的无向图中，若边数大于n-1, 则该图必是连通图。 （）3对有 n 个顶点的无向图，其边数e 与各顶点度数间满足下列等式e=niViTD1)(。（）4. 有 e 条边的无向图，在邻接表中有e 个结点。（）5. 有向图中顶点V 的度等于其邻接矩阵中第V行中的 1 的个数。（）6强连通图的各顶点间均可达。（）7强连通分量是无向图的极大强连通子图。（）8连通分量指的是有向图中的极大连通子图。（）9邻接多重表是无向图和有向图的链式存储结构。（）10. 十字链表是无向图的一种存储结构。（）11. 无向图的邻接矩阵可用一维数组存储。（）12用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（）13 有 n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。 （）14. 有向图的邻接矩阵是对称的。（）15无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（）16. 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。（）17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）18一个有向图的邻接表和逆邻接表中结点的个数可能不等。（）19需要借助于一个队列来实现DFS算法。（）20. 广度遍历生成树描述了从起点到各顶点的最短路径。（）21任何无向图都存在生成树。（）22. 不同的求最小生成树的方法最后得到的生成树是相同的. （）23带权无向图的最小生成树必是唯一的。（）24. 最小代价生成树是唯一的。（）25一个网（带权图）都有唯一的最小生成树。（）26连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）27带权的连通无向图的最小（代价）生成树（支撑树）是唯一的。（）28. 最小生成树的KRUSKAL 算法是一种贪心法（GREEDY） 。 （）29. 求最小生成树的普里姆(Prim) 算法中边上的权可正可负。（）三、填空题1. 判断一个无向图是一棵树的条件是_。2有向图G的强连通分量是指_。3一个连通图的_是一个极小连通子图。4具有 10 个顶点的无向图，边的总数最多为_。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 5若用 n 表示图中顶点数目，则有_条边的无向图成为完全图。6. 设无向图 G 有 n 个顶点和e 条边，每个顶点Vi 的度为 di （1=i=n ，则 e=_ 7G是一个非连通无向图，共有28 条边，则该图至少有_个顶点。8. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_条弧。9在有 n 个顶点的有向图中，每个顶点的度最大可达_。10设 G为具有 N个顶点的无向连通图，则G中至少有 _条边。11 n 个顶点的连通无向图，其边的条数至少为_。12如果含n 个顶点的图形形成一个环，则它有_棵生成树。13 N 个顶点的连通图的生成树含有_条边。14构造 n 个结点的强连通图，至少有_条弧。15有 N 个顶点的有向图，至少需要量_条弧才能保证是连通的。16右图中的强连通分量的个数为（）个。17 N 个顶点的连通图用邻接矩阵表示时, 该矩阵至少有 _个非零元素。18在图 G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_；对于有向图来说等于该顶点的_。19. 在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是_。20. 对于一个具有n 个顶点 e 条边的无向图的邻接表的表示，则表头向量大小为_，邻接表的边结点个数为_。21. 遍历图的过程实质上是_，breath-first search遍历图的时间复杂度_；depth-first search遍历图的时间复杂度_，两者不同之处在于_，反映在数据结构上的差别是_。22. 已知一无向图G= （V，E ） ，其中 V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd，则采用的是 _遍历方法。23. 一无向图G （V，E） ，其中 V （G）=1,2,3,4,5,6,7，E（G）=（1,2 ）,(1,3） ， （2,4 ） ，（2,5 ） ， （3,6 ） ， （3,7 ） ， （6,7 ） （5,1 ）, 对该图从顶点3 开始进行遍历，去掉遍历中未走过的边，得一生成树G (V ，E ）,V（G ）=V（ G ） ，E （G ）=（1,3 ） ， （3,6 ） ， （7,3 ） ， （1,2 ） ，（1,5 ） ， （2,4 ） ，则采用的遍历方法是_。24. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需 _存放被访问的结点以实现遍历。25. 按下图所示，画出它的广度优先生成树_和深度优先生成树_。26构造连通网最小生成树的两个典型算法是_。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 27求图的最小生成树有两种算法，_算法适合于求稀疏图的最小生成树。28. Prim（普里姆）算法适用于求_的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 _的网的最小生成树。29克鲁斯卡尔算法的时间复杂度为_, 它对 _图较为适合。30对于含N个顶点 E 条边的无向连通图，利用Prim 算法生成最小代价生成树其时间复杂度为 _，利用 Kruskal算法生成最小代价生成树其时间复杂度为_。44已知图的邻接表结构为： CONST vtxnum=图的顶点数 TYPE vtxptr=1.vtxnum; arcptr=arcnode; arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END; vexnode=RECORD vexdata:和顶点相关的信息 ；firstarc:arcptr END; adjlist=ARRAYvtxptrOF vexnode; 本算法是实现图的深度优先遍历的非递归算法。其中，使用一个顺序栈stack 。栈顶指针为top 。visited为标志数组。PROC dfs(g:adjlist;v0:vtxptr); top=0; write(v0); visitedv0:=ture; p:=gv0.firstarc; WHILE (top0)OR(pNIL)DO WHILE(1)_DO v:=p.adjvex; IF(2)_ THEN p:=p.nextarc ELSE write(v); visitedv:=true; top:=top+1; stacktop:=p; (3)_ IF top0 THENp:=stacktop; top:=top-1; (4)_ ENDP. 46 n 个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注： （1） 图的顶点号从 0 开始计；（2） indegree 是有 n 个分量的一维数组，放顶点的入度；（3） 函数 crein 用于算顶点入度；（4） 有三个函数push(data),pop( ),check( )其含义为数据 data进栈，退栈和测试栈是否空（不空返回1，否则 0） 。 crein( array ,indegree,n) for (i=0;in;i+) indegreei= (1)_) for(i=0,in;i+) for (j=0;jn; j+) indegreei+=array(2)_(3)_; topsort (array,indegree,n) count= (4)_) for (i=0;in;i+) if (5)_) push(i) while (check( ) vex=pop( ); printf(vex); count+; for (i=0;in;i+) k=array(6)_ if (7)_ ) indegreei-; if (8)_ ) push(i); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - if( countn) printf(“ “图有回路” ) ； 四、应用题1 （1） 如果 G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？（ 2） 如果 G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？（ 3） 如果 G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边？G3最少有多少条边？2n 个顶点的无向连通图最少有多少条边？n 个顶点的有向连通图最少有多少条边？3一个二部图的邻接矩阵A是一个什么类型的矩阵？4证明：具有n 个顶点和多于n-1 条边的无向连通图G一定不是树。5证明对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且主对角线为全0 的充要条件是该图为无环图。6用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？7请回答下列关于图(Graph) 的一些问题： （每题 4 分）（1） 有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边? （2） 表示有1000 个顶点、 l000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？（3） 对于一个有向图，不用拓扑排序，如何判断图中是否存在环？8解答问题。设有数据逻辑结构为：B = (K, R), K = k1, k2, , k9 R=, , , , , , , , （ 1） 画出这个逻辑结构的图示。（3 分）（ 2） 相对于关系r, 指出所有的开始接点和终端结点。（2 分）（ 3） 分别对关系r 中的开始结点，举出一个拓扑序列的例子。（4 分）（ 4） 分别画出该逻辑结构的正向邻接表和逆向邻接表。（6 分）9有向图的邻接表存储如下：（1） 画出其邻接矩阵存储； （2） 写出图的所有强连通分量；（3） 写出顶点a 到顶点 i 的全部简单路径。10试用下列三种表示法画出网G 的存储结构，并评述这三种表示法的优、缺点：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - （ 1） 邻接矩阵表示法; （2） 邻接表表示法; （3） 其它表示法。11已知无向图G，V（G）=1 ，2，3，4 ，E（G）= （1，2） ， （1，3） ， （2，3） ， （2，4） ，（3，4）试画出 G的邻接多表，并说明，若已知点I ，如何根据邻接多表找到与I 相邻的点 j ？12 如何对有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1 都集中到对角线以上？13假定（V，E）是有向图， V 1,2 ， ,N ，N 1，G以邻接矩阵方式存储，G的邻接矩阵为A，即是一个二维数组，如果i 到 j 有边，则 Ai,j=1，否则 Ai,j=0，请给出一个算法，该算法能判断G是否是非循环图（即G中是否存在回路） ，要求算法的时间复杂性为O(n*n) 。14 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出对其分别进行深度，广度优先遍历的结果。15下面的邻接表表示一个给定的无向图（1）给出从顶点v1 开始 , 对图 G用深度优先搜索法进行遍历时的顶点序列；（ 2）给出从顶点v1 开始 , 对图 G用广度优先搜索法进行遍历时的顶点序列。 15题图 14题图 16题图16给出图G：（1） 画出 G的邻接表表示图；（2） 根据你画出的邻接表，以顶点为根，画出G的深度优先生成树和广度优先生成树。17设 G=(V,E) 以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。3 6 7 5 8 9 4 2 1 3 10 5 7 8 4 2 1 6 9 123451341241232423455名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -