数据结构第7章

《数据结构第7章》由会员分享，可在线阅读，更多相关《数据结构第7章（20页珍藏版）》请在金锄头文库上搜索。

1、一、单选题coi、在一个图中，所有顶点的度数之和等于图的边数的一倍。A)l/2 B)102 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的一倍。A)l/2 B)102 D)4B03、有8个结点的无向图最多有条边匚A)14 B)28056 D)112C04、有8个结点的无向连通图最少有条边。A) 5B)607 D)8C05、有8个结点的有向完全图有条边。A)14B)28056D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用一来实现算法的。A)栈B)队列C)树D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用一来实现算法的。A)栈B)队列C)树D)图

2、A08、一个含n个顶点和e条孤的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂 度为一cA) 0 (n) B) 0 (e)C)0 (n+e) D) 0 ()根据算法思想，则从顶点0出发按深度优先遍历的结点序列是C09、已知图的邻接矩阵，0 1)110 110 0 10 0110 0 01 00110 01 1010 110 100 0 0 1I 01110 00A)0 2 4 3 1 5 6B)0 1 3 6 5 4 2B10、已知图的邻接矩阵同上题，根据算法A)0 2 4 3 6 5 1B)0 1 2 3 4 6 5Dll、已知图的邻接表如下所示，根据算法，00 1

3、 3 4 2 5 6D)0 3 6 1 5 4 2则从顶点0出发，按广度优先遍历的结点序列是00 4 2 3 1 5 6D)0 1 3 4 2 5 6则从顶点0出发按深度优先遍历的结点序列是*1j1 2 1 -H 3 1 / 13 I/ IA)0 1 3 2B)0 2 3 1A12、已知图的邻接表如下所示，0-1 _4C)0 3 2 1D)0 1 2 3根据算法，则从顶点0出发按广度优先遍历的结点序列是A)0 3 2 1B)0 1 2 3A13、图的深度优先遍历类似于二叉树的%r1 12T 3 1 4 21 - H i 1 H一3 | - -1117 2 |C)0 1 3 2o /-4 o |

4、 /10 | /D)0 3 1 2A)先序遍历B)中序遍历C)后序遍历D)层次遍历D14、图的广度优先遍历类似于二叉树的A)先序遍历B)中序遍历C)后序遍历D)层次遍历B15、任何一个无向连通图的最小生成树A)只有一棵B) 一棵或多棵C) 一泄有多棵D)可能不存在A16.对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为所有边链表中边 结点的总数为A)n、2e B)n、e C)n. n+e D)2n、2eC17、判断有向图是否存在回路，可以利用一算法。A)关键路径B)最短路径的Dijkstra C)拓扑排序D)广度优先遍历A1&若用邻接矩阵表示一个有向图，则其中每一列包含

5、的“1的个数为一A）图中每个顶点的入度B）图中每个顶点的出度C）图中孤的条数D）图中连通分量的数目C19、求最短路径的Dijkstra算法的时间复杂度是一。A) 0 (n)B) 0 (n+e)C) 0 (n2)D) 0 (n*e)B20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为A) 0 (n)B) 0 (n+e)0 0 (n2)D) 0 (n*e)D21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中_oA) 第i行非8的元素之和B)第i列非8的元素之和0第i行非8且非0的元素个数D)第 i列非8且非0的元素个数C22、一个有n个顶点的无向图最多有条边。A)n B)n(n-l)

6、 C)n(n-l)/2 D)2nD23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是A)n B) (n-l):C) n-1 D) n:A24.对某个无向图的邻接矩阵来说，一aA) 第i行上的非零元素个数和第i9列的非零元素个数一定相等B) 矩阵中的非零元素个数等于图中的边数C) 第i行上，第i列上非零元素总数等于顶点口的度数D) 矩阵中非全零行的行数等于图中的顶点数D25、已知图的表示如下，若从顶点&出发按深度搜索法进行遍历，则可能得到的一种顶点序列为A)abecdfB)acfebdC)aebcfdD)aedfcbB26、已知图的表示如上题，若从顶点a出发按广度搜索法进行

7、遍历，则可能得到的一种顶点序列为A)abcedfB)abcefdC)aebcfdD)acfdebC27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法,从顶点vl出发得到的顶点序列是A) vl, v2, v3, v5, v4 B) vl, v2, v3, v4, v5 C) vl, v3, v4, v5, v2 D) vl, v4, v3, v5, v2B28、有向图的邻接表存储结构如上题所示，则根拯有向图的广度遍历算法,从顶点vl出发得到的顶点序列是_。A)vl, v2, v3, v4, v5 B) vl, v3, v2, v4, v5 C) vl, v2, v3, v5, v

8、4 D) vl, v4, v3, v5, v2A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用一次深度优先遍 历算法。A)k B)1 C)n-k D)nD30、以下不正确的说法是一oA) 无向图中的极大连通子图称为连通分量B) 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C) 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D) 有向图的遍历不可采用广度优先搜索方法A31、图中有关路径的定义是A)由顶点和相邻顶点序偶构成的边所形成的序列B)由不同顶点所形成的序列0由不同边所形成的序列 D)上述定义都不是B32、设无向图的顶点个数为n,则该

9、图最多有一条边。A) n-1 B) n (n-1) /2 C) n (n+l)/2 D) nA33、一个n个顶点的连通无向图，其边的个数至少为一oA) n-1 B)n C)n+1 D)nlognB34、要连通具有n个顶点的有向图，至少需要一条边。A)n-1B)nC)n+1D)2nB35、在一个无向图中，所有顶点的度数之和等于所有边数一倍。A)l/2B)201D)4C36、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的一倍。A)l/2B)201D)4A37、用有向无环图描述表达式(A+B)* ( (A+B) /A),至少需要顶点的数目为一。A)5B)608D)9A38、用DFS遹历一个

10、无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是A)逆拓扑有序B)拓扑有序 C)无序的D)原顺序B39、下列一的邻接矩阵是对称矩阵。A)有向图B)无向图C)A0V网 D)A0E网0 1 0 1 0 1BBD40、从邻接阵矩 1 可以看出，该图共有个顶点:如果是有向图该图共有型条孤：如果是无向图，则共 有条边。 A)9B)306D)1E)以上答案均不正确 A) 5B)403D)2E)以上答案均不正确 A) 5B)403D)2E)以上答案均不正确B41、当打个有N个顶点的缪用邻接矩阵A者示时，顶点Vi岁度是一A. 观，J B. S4/,y c.D. 如，刀 +B42、下说法不

11、正确的墓A)图的遍历是从给左的源点出发每一个顶点仅被访问一次B)图的深度遍历不适用于有向图C)遍历的基本算法有两种：深度遍历和广度遍历D)图的深度遹历是一个递归过程D43、无向图 G 二(V,E),-其中：V=a,b, cfd, e, f, E=(a, b), (a, e), (a,c), (b, e), (c,f), (f, d), (etd) 对该图进 行深度优先 遍历，得到的顶点序列正确的是一。A)abecdf B)acfebd C)aebcfd D)aedfcbD44A如图所示，在5个序列aebdfc. acfdebx aedfcb、aefdcb aefdbcM符合深度优先遍历的序列有

12、 个。A)5 _CC45、图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先迪历得到的序列是一，进行广度 优先遍历得到的顶点序列是)13勇267B) 1347652C) 1534276D)1247653E)以上答案均不正确 A)1534267 B) 1726453C)1354276D)1247653E)以上答案均不正确B46、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为一 cA) 0 (n) B) 0 (n+e) C) 0 (n) D) 0 (n)CABA47.下面是求连通网的最小生成树的prim算法：集合VT, ET分别放顶点和边，初始为下面步骤重复n-l次:：

13、最后： o 而，EF另空B而勺所有顶点，ET为空C)VT为网中任意一点，ET为空 D)VT为空，ET为网中所有边 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)上的权最大 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中有1条边时为生成树，否则无解D)ET中无回路时，为生成树，否则无解A4&下而不正确的是一o意义； 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是0()：(图用邻接矩阵表示) Floyd求每对不同顶点对的算法中允许孤上的权为负，但不能有权和为负的回路。A)B)(D C)D)A49、已知有向图 G=(V E), 其中 V=Vi V V V V VSV： E= V V 、，, ,s, ： J,、Y。, ,235b 33 t b26 f 55, . , ,则 G 的拓扑序列是一0 A)V V3 V VVrV V： B) V： V V V VV V： C) Vi