一、单选题
C01、在一个图中，所有顶点的度数之和等于图的边数的 倍。 A)1/2 B)1 C)2 D)4 B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A)1/2 B)1 C)2 D)4
B03、有8个结点的无向图最多有 条边。 A)14 B)28 C)56 D)112
C04、有8个结点的无向连通图最少有 条边。 A)5 B)6 C)7 D)8
C05、有8个结点的有向完全图有 条边。 A)14 B)28 C)56 D)112
B06、用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A)栈 B)队列 C)树 D)图
A07、用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A)栈 B)队列 C)树 D)图
A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 。
2
A)O(n) B)O(e) C)O() D)O(n)
C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 。
A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2
B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是 。
A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6
D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 。
A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3
A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历
的结点序列是 。
A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2 A13、图的深度优先遍历类似于二叉树的 。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 D14、图的广度优先遍历类似于二叉树的 。
A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历 B15、任何一个无向连通图的最小生成树 。
A)只有一棵 B)一棵或多棵 C)一定有多棵 D)可能不存在
A16、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为 ，所有边链表中边结点的总数为 。 A)n、2e B)n、e C)n、 D)2n、2e C17、判断有向图是否存在回路，可以利用算法。
A)关键路径 B)最短路径的 C)拓扑排序 D)广度优先遍历
A18、若用邻接矩阵表示一个有向图，则其中每一列包含的“1”的个数为 。 A)图中每个顶点的入度 B)图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目
C19、求最短路径的算法的时间复杂度是。
2
A)O(n) B)O() C)O(n) D)O(n*e)
B20、设图G采用邻接表存储，则拓扑排序算法的时间复杂度为 。 2
A)O(n) B)O() C)O(n) D)O(n*e)
D21、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 。 A)第i行非∞的元素之和 B)第i列非∞的元素之和
C)第i行非∞且非0的元素个数 D)第i列非∞且非0的元素个数 C22、一个有n个顶点的无向图最多有 条边。 A)n B)n(1) C)n(1)/2 D)2n
D23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。
22
A)n B)(1) C)1 D)n
A24、对某个无向图的邻接矩阵来说， 。
A)第i行上的非零元素个数和第i列的非零元素个数一定相等 B)矩阵中的非零元素个数等于图中的边数
C)第i行上，第i列上非零元素总数等于顶点的度数 D)矩阵中非全零行的行数等于图中的顶点数
D25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 。
A) B) C) D)
B26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为 。 A) B) C) D)
C27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是 。
A)v12354 B)v12345 C)v13452 D)v14352
B28、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是 。
A)v12345 B)v13245 C)v12354 D)v14352
A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用 次深度优先遍历算法。 A)k B)1 C) D)n D30、以下不正确的说法是 。
A)无向图中的极大连通子图称为连通分量
B)连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C)图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D)有向图的遍历不可采用广度优先搜索方法 A31、图中有关路径的定义是。
A)由顶点和相邻顶点序偶构成的边所形成的序列 B)由不同顶点所形成的序列
C)由不同边所形成的序列 D)上述定义都不是 B32、设无向图的顶点个数为n，则该图最多有条边。 A)1 B)n(1)/2 C)n(1)/2 D)n
A33、一个n 个顶点的连通无向图，其边的个数至少为。 A)1 B)n C)1 D)
B34、要连通具有n 个顶点的有向图，至少需要条边。 A) B)n C) D)2n
B35、在一个无向图中，所有顶点的度数之和等于所有边数倍。 A)1/2 B)2 C)1 D)4
C36、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的倍。
A)1/2 B)2 C)1 D)4
A37、用有向无环图描述表达式()*（（）），至少需要顶点的数目为。 A)5 B)6 C)8 D)9
A38、用 遍历一个无环有向图，并在 算法退栈返回时打印相应的顶点，则输出的顶点序列是。
A)逆拓扑有序 B)拓扑有序 C)无序的 D)原顺序 B39、下列的邻接矩阵是对称矩阵。
A)有向图 B)无向图 C)网 D)网
40、从邻接阵矩 可以看出，该图共有 ① 个顶点；如果是有向图该图共有 ② 条弧；如果是无向图，则共有 ③ 条边。 ① 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)以上答案均不正确 B41、当一个有N 个顶点的图用邻接矩阵A 表示时，顶点 的度是。
B42、下列说法不正确的是。
A)图的遍历是从给定的源点出发每一个顶点仅被访问一次 B)图的深度遍历不适用于有向图
C)遍历的基本算法有两种：深度遍历和广度遍历 D)图的深度遍历是一个递归过程
D43、无向图()，其中：{}{(),(),(),(),(),(),()}，对该图进行深度优先遍历，得到的顶点序列正确的是。 A) B) C) D)
D44、如图所示，在5个序列“、、、、”，符合深度优先遍历的序列有个。
A)5 B)4 C)3 D)2
45、图中给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的序列是 ① ，进行广度优先遍历得到的顶点序列是 ② 。
① A)1354267 B)1347652 C)1534276 D)1247653 E)以上答案均不正确
② A)1534267 B)1726453 C)l354276 D)1247653 E)以上答案均不正确
B46、在图采用邻接表存储时，求最小生成树的算法的时间复杂度为。
23
A)O(n) B)O() C)O(n) D)O(n) 47、下面是求连通网的最小生成树的算法：集合，分别放顶点和边，初始为 ① ，下面步骤重复1次： ② ； ③ ；最后： ④ 。 ① A)， 为空 B)为所有顶点，为空
C)为网中任意一点，为空 D)为空，为网中所有边
② A)选i属于，j不属于，且()上的权最小 B)选i属于，j不属于，且()上的权最大
C)选i不属于，j不属于，且()上的权最小 D)选i不属于，j不属于，且()上的权最大
③ A)顶点i加入，()加入 B)顶点j加入，()加入 C)顶点j加入，()从中删去 D)顶点加入，()加入 ④ A)中为最小生成树 B)不在中的边构成最小生成树
C) 中有1条边时为生成树，否则无解 D)中无回路时，为生成树，否则无解
A48、下面不正确的是。
①求从指定源点到其余各顶点的最短路径算法中弧上权不能为负的原因
数据结构第7章-答案
