《数据结构第7章答案》由会员分享，可在线阅读，更多相关《数据结构第7章答案（15页珍藏版）》请在金锄头文库上搜索。
1、一、单选题coi、在一个图中，所有顶点的度数之和等于图的边数的倍。A) l/2B)1C)2D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A) 1/2B)1C)2D)4B03、有8个结点的无向图最多有条边。A) 14B)28C)56D)112C04、有8个结点的无向连通图最少有条边。A) 5B)6C)7D)8C05、有8个结点的有向完全图有条边。A)14B)28C)56D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A)栈B)队列C)树D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A)栈B)队列C)树D)图A08
2、、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。A)O(n)B)O(e)C)O(n+e)D)O(m)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是Dill100110001100101100011100A)02431001100110D10LD1101D56B)01B10、已知图的邻接矩阵同上题,A)0243651B)01D11、已知图的邻接表如下所示,36542C)0134256D)0361542根据算法，则从顶点0出发，按广度优先遍历的结点序列是23465C)0423156D)0134256根据算法，
3、则从顶点0出发按深度优先遍历的结点序列是A)0132B)0231C)0321D)0123A12、已知图的邻接表如下所示，根据算法，贝y从顶点0出发按广度优先遍历的结点序列是A)0321B)0123C)0132D)0312A13、图的深度优先遍历类似于二叉树的。A)先序遍历B)中序遍历C)后序遍历D)层次遍历D14、图的广度优先遍历类似于二叉树的。A)先序遍历B)中序遍历C)后序遍历D)层次遍历B15、任何一个无向连通图的最小生成树。A)只有一棵B)一棵或多棵C)一定有多棵D)可能不存在A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为，所有边链表中边结点的总数为。
4、A)n、2eB)n、eC)n、n+eD)2n、2eC17、判断有向图是否存在回路，可以利用算法。A)关键路径B)最短路径的DijkstraC)拓扑排序D)广度优先遍历A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为。A)图中每个顶点的入度B)图中每个顶点的出度C)图中弧的条数D)图中连通分量的数目C19、求最短路径的Dijkstra算法的时间复杂度是。A)O(n)B)O(n+e)C)O(n2)D)O(n*e)B20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为。A)O(n)B)O(n+e)C)O(n2)D)O(n*e)D21、带权有向图G用邻接矩阵A存储，则顶点i的入
5、度等于A中。A)第i行非a的元素之和B)第i列非a的元素之和C)第i行非a且非0的元素个数D)第i列非a且非0的元素个数C22、一个有n个顶点的无向图最多有条边。A)nB)n(n-1)C)n(n-l)/2D)2nD23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。A)nB)(n1)2C)nTD)n2A24、对某个无向图的邻接矩阵来说，。A) 第i行上的非零元素个数和第i列的非零元素个数一定相等B) 矩阵中的非零元素个数等于图中的边数C) 第i行上，第i列上非零元素总数等于顶点v的度数iD) 矩阵中非全零行的行数等于图中的顶点数D25、已知图的表示如下，若从顶点a出发按深
6、度搜索法进行遍历，则可能得到的一种顶点序列为A)abecdfB)acfebdC)aebcfdD)aedfcbB26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为。A)abcedfB)abcefdC)aebcfdD)acfdebC27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法,从顶点vl出发得到的顶点序列是A)vl,v2,v3,v5,v4B)v1,v2,v3,v4,v5C)v1,v3,v4,v5,v2D)v1,v4,v3,v5,v2B28、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法,从顶点vl出发得到的顶点序列是。A)v
7、1,v2,v3,v4,v5B)v1,v3,v2,v4,v5C)v1,v2,v3,v5,v4D)v1,v4,v3,v5,v2A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用次深度优先遍历算法。A)kB)1C)nkD)nD30、以下不正确的说法是。A) 无向图中的极大连通子图称为连通分量B) 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C) 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D) 有向图的遍历不可采用广度优先搜索方法A31、图中有关路径的定义是_。A)由顶点和相邻顶点序偶构成的边所形成的序列B)由不同顶点所形成的序列C)由不同边
8、所形成的序列D)上述定义都不是B32、设无向图的顶点个数为n,则该图最多有条边。A)n1B)n(n1)/2C)n(n+1)/2D)nA33、一个n个顶点的连通无向图，其边的个数至少为。A)n1B)nC)n+1D)nlognB34、要连通具有n个顶点的有向图，至少需要条边。A)nlB)nC)n+lD)2nB35、在一个无向图中，所有顶点的度数之和等于所有边数倍。A)1/2B)2C)1D)4C36、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。A)l/2B)2C)1D)4A37、用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为。A)5B)6C)8D)9A38、
9、用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是。A)逆拓扑有序B)拓扑有序C)无序的D)原顺序B39、下列的邻接矩阵是对称矩阵。A)有向图B)无向图C)AOV网D)AOE网1F101BBD40、从邻接阵矩b1可可以看出，该图共有个顶点；如果是有向图该图共有条弧；如果是无向图，则共有条边。A)9B)3C)6D)1E)以上答案均不正确A)5B)4C)3D)2E)以上答案均不正确A)5B)4C)3D)2E)以上答案均不正确B41、当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是.B42、下列说法不正确的是。A)图的遍历是从给定的源点出发每一个顶点仅被访问
10、一次B)图的深度遍历不适用于有向图C)遍历的基本算法有两种：深度遍历和广度遍历D)图的深度遍历是一个递归过程D43、无向图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)abecdfB)acfebdC)aebcfdD)aedfcbD44、如图所示，在5个序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”，符合深度优先遍历的序列有个。CC45、图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是，进行广度
11、优先遍历得到的顶点序列是。 A)1354267B)1347652C)1534276D)1247653E)以上答案均不正确 A)1534267B)1726453C)l354276D)1247653E)以上答案均不正确B46、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为。A)O(n)B)O(n+e)C)O(m)D)O(m)CABA47、下面是求连通网的最小生成树的prim算法：集合VT,ET分别放顶点和边，初始为，下面步骤重复n-1次：；最后：。 A)VT，ET为空B)VT为所有顶点，ET为空C)VT为网中任意一点，ET为空D)VT为空，ET为网中所有边 A)选i属于VT,j不属
12、于VT,且(i,j)上的权最小B)选i属于VT,j不属于VT,且(i,j)上的权最大C)选i不属于VT,j不属于VT,且(i,j)上的权最小D)选i不属于VT,j不属于VT,且(i,j)上的权最大 A)顶点i加入VT,(i,j)加入ETB)顶点j加入VT,(i,j)加入ETC)顶点j加入VT,(i,j)从ET中删去D)顶点i,j加入VT,(i,j)加入ET A)ET中为最小生成树B)不在ET中的边构成最小生成树C)ET中有n-1条边时为生成树，否则无解D)ET中无回路时，为生成树，否则无解A48、下面不正确的是。#第7章图数据结构作业答案 求从指定源点到其余各顶点的Dijkstra最短路径算法
13、中弧上权不能为负的原因是在实际应用中无意义; 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是0(n3)；(图用邻接矩阵表示) Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。A)B)C)D)A49、已知有向图G=(V,E)，其中VRVrVzV/VrVyVsV?,EV，*,，V,“,人观,V4,V6，V5,V7，V,则G的拓扑序列是.。465767A)V,V,V,V,V,V,VB)V,V,V,V,V,V,VC)V,V,V,V,V,V,VD)V,V,V,V,V,V,V1346257132645713452671253467D50、在有向图G的拓扑序列中，
14、若顶点Vi在顶点Vj之前，贝y下列情形不可能出现的是。A)G中有弧Vi,VjB)G中有一条从Vi到Vj的路径C)G中没有弧Vi,VjD)G中有一条从Vj到Vi的路径A51、关键路径是事件结点网络中_。A)从源点到汇点的最长路径B)从源点到汇点的最短路径C)最长回路D)最短回路C52、下面关于求关键路径的说法不正确的是A)求关键路径是以拓扑排序为基础的B) 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C) 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D) 关键活动一定位于关键路径上B53、下列关于AOE网的叙述中，不正确的是。A) 关键活动不
15、按期完成就会影响整个工程的完成时间B) 任何一个关键活动提前完成，那么整个工程将会提前完成C) 所有的关键活动提前完成，那么整个工程将会提前完成D) 某些关键活动提前完成，那么整个工程将会提前完成二、填空题01、在有向图中，以顶点v为终点的边的数目称为v的入度。02、含n个顶点的无向连通图中至少含有n-1条边。03、图的存储结构表示有邻接矩阵、邻接表、十字链表、邻接多重表等多种存储结构。04、图的存储结构中，十字链表可以看成是有向图的邻接表和逆邻接表结合起来得到的一种链表。05、遍历图的2种常见方法是深度遍历和广度遍历。06、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。07、如果n个顶点的图是一个环，则它有n棵生
