计算机专业基础综合数据结构（图）模拟试卷1
单选题
1.下面是一个求最小生成树的算法，其中G是连通无向图，T是所求的生成树。
T：=G：
While T中存在回路do
begin在T中找一条权值最大的边e；
T：=T一[e]； (T中去掉e边)
EnD．
试问该算法是哪一种求最小生成树的算法?( )(B)
A. Prim(普里姆)算法
B. Kruskal(克鲁斯卡尔算法)
C. 罗巴赫算法
D. 其他算法
解析：由算法可以看出使用的是Kruskal算法。
2.邻接表是图的一种( )。(B)
A. 顺序存储结构
B. 链接存储结构
C. 索引存储结构
D. 散列存储结构
解析：图的邻接表存储结构是一种链接存储结构。
3.下面试图对图中路径进行定义，说法正确的是( )。(A)
A. 由顶点和相邻顶点序列构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
解析：由图的定义可知，B与C是错误的。
4.无向图中顶点个数为n，那么边数最多为( )。(B)
A. n一1
B. n(n一1)／2
C. n(n+1)／2
D. n2
解析：无向图中有n个顶点，如果每两个顶点之间均是相互连通的，那么此时无向图中的边数最多，为n(n一1)／2。
5.在一个具有n(n＞0)个顶点的连通无向图中，至少需要的边数是( )。(C)
A. n
B. n+1
C. n一1
D. n／2
解析：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以具有n个顶点的连通无向图至少有n—1条边。
6.以下叙述中正确的是( )。
I．对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
Ⅱ．连通图的广度优先搜索中一般要采用队列来暂存访问过的顶点
Ⅲ．图的深度优先搜索中一般要采用栈来暂存访问过的顶点(B)
A. I，Ⅱ
B. Ⅱ，Ⅲ
C. I，Ⅲ
D. I，Ⅱ，Ⅲ
解析：I的叙述是错误的，因为如果有向图构成双向有向环时，则从任一顶点出发均能访问到每个顶点，但该图却非完全图。Ⅱ、Ⅲ的叙述显然是正确的。
7.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中( )。(D)
A. 第i行非∞的元素之和
B. 第i列非∞的元素之和
C. 第i行非∞且非0的元素个数
D. 第i列非∞且非0的元素个数
解析：有向图的邻接矩阵中，0和∞表示的都不是有向边，而入度是由邻接矩阵的列中元素计算出来的。
8.在一个无向图中，所有顶点的度之和等于边数的( )倍。(C)
A. 1／2
B. 1
C. 2
D. 4
解析：在无向图中，一条边计入两个顶点的度数。
9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )算法。(A)
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
解析：由图的深度优先遍历算法和二叉树的前序遍历可知选A。
10.任何一个无向连通图( )最小生成树。(B)
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
解析：无向连通图应有一棵或多棵最小生成树。
11.判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用的是( )。(C)
A. 求关键路径的方法
B. 求最短路径的迪杰斯特拉方法
C. 深度优先遍历算法
D. 广度优先遍历算法
解析：当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序(退出DFSTra—verse算法)即为逆向的拓扑序列。
12.有n个顶点e条边的无向图，采用邻接表存储时，有( )个表头结点，有( )个链表结点。(A)
A. n，2e
B. n，2e+1
C. n一1，2e
D. n—1．2e+1
解析：根据邻接表的结构，无向图对应的邻接表有n个表头结点，有2e个链表结点(每条边对应两个链表结点)。
13.对于由n个顶点组成的有向完全图来说，图中共包含( )条边，对于由n个顶点组成的无向完全图来说，图中共包含( )条边。(D)
A. n，n(n一1)
B. n，n(n一1)／2
C. 2n，n(n一1)
D. n(n—1)，n(n一1)／2
解析：由完全图的定义可知本题答案为D。
14.在一个( )图中寻找拓扑序列的过程称为( )。(A)
A. 有向，拓扑排序
B. 无向，拓扑排序
C. 有向，最短路径搜索
D. 无向，最短路径搜索
解析：寻找拓扑序列就是拓扑排序，只能对有向图进行拓扑排序。
15.用邻接矩阵A表示图，判定任意两个顶点vi和vj之间是否有长度为m的路径相连，则只要检查( )的第i行第j列的元素是否为零即可。(C)
A. mA
B. A
C. Am
D. Am-1
解析：此题考查的知识点是图的邻接矩阵存储。在图的邻接矩阵中，两点之间有边，则值为1，否则为0。本题只要考虑Am=A×A×…×A(m个A矩阵相乘后的乘积矩阵)中(i，j)的元素值是否为0
本文档预览：3000字符，共18368字符，源文件无水印，下载后包含无答案版和有答案版，查看完整word版点下载
