一、单选题
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、用邻接表表示图进行深度优先遍历时，通常是采用05网全部答案 来实现算法的。
A)栈 B)队列 C)树 D)图
A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 。
A)O(n) B)O(e) C)O(n+e) D)O(n2)
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、n+e D)2n、2e
C17、判断有向图是否存在回路，可以利用___算法。
A)关键路径 B)最短路径的Dijkstra C)拓扑排序 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的入度等于A中 。
A)第i行非∞的元素之和 B)第i列非∞的元素之和
C)第i行非∞且非0的元素个数 D)第i列非∞且非0的元素个数
C22、一个有n个顶点的无向图最多有 条边。
A)n B)n(n-1) C)n(n-1)/2 D)2n
D23、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。
A)n B)(n-1)2 C)n-1 D)n2
A24、对某个无向图的邻接矩阵来说， 。
A)第i行上的非零元素个数和第i列的非零元素个数一定相等
B)矩阵中的非零元素个数等于图中的边数
C)第i行上，第i列上非零元素总数等于顶点vi的度数
D)矩阵中非全零行的行数等于图中的顶点数
D25、已知图的表示如下，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为 。
A)abecdf B)acfebd C)aebcfd D)aedfcb
B26、已知图的表示如上题，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为 。
A)abcedf B)abcefd C)aebcfd D)acfdeb
C27、有向图的邻接表存储结构如下图所示，则根据有向图的深度遍历算法，从顶点v1出发得到的顶点序列是 。
A)v1,v2,v3,v5,v4 B)v1,v2,v3,v4,v5 C)v1,v3,v4,v5,v2 D)v1,v4,v3,v5,v2
B28、有向图的邻接表存储结构如上题所示，则根据有向图的广度遍历算法，从顶点v1出发得到的顶点序列是 。
A)v1,v2,v3,v4,v5 B)v1,v3,v2,v4,v5 C)v1,v2,v3,v5,v4 D)v1,v4,v3,v5,v2
A29、一个图中有n个顶点且包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用 次深度优先遍历算法。
A)k B)1 C)n-k D)n
D30、以下不正确的说法是 。
A)无向图中的极大连通子图称为连通分量
B)连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C)图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D)有向图的遍历不可采用广度优先搜索方法
A31、图中有关路径的定义是___。
A)由顶点和相邻顶点序偶构成的边所形成的序列 B)由不同顶点所形成的序列
C)由不同边所形成的序列 D)上述定义都不是
B32、设无向图的顶点个数为n，则该图最多有___条边。
A)n-1 B)n(n-1)/2 C)n(n+1)/2 D)n
A33、一个n 个顶点的连通无向图，其边的个数至少为___。
A)n-1 B)n C)n+1 D)nlogn
B34、要连通具有n 个顶点的有向图，至少需要___条边。
A)n-l B)n C)n+l D)2n
B35、在一个无向图中，所有顶点的度数之和等于所有边数___倍。
A)1/2 B)2 C)1 D)4
C36、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的___倍。
A)1/2 B)2 C)1 D)4
A37、用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为___。
A)5 B)6 C)8 D)9
A38、用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是___。
A)逆拓扑有序 B)拓扑有序 C)无序的 D)原顺序
B39、下列___的邻接矩阵是对称矩阵。
A)有向图 B)无向图 C)AOV网 D)AOE网
BBD40、从邻接阵矩 可以看出，该图共有 ① 个顶点；如果是有向图该图共有 ② 条弧；如果是无向图，则共有 ③ 条边。
① 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 表示时，顶点Vi 的度是___。
B42、下列说法不正确的是___。
A)图的遍历是从给定的源点出发每一个顶点仅被访问一次 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)}，对该图进行深度优先遍历，得到的顶点序列正确的是___。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论