数据结构测试（长春理工大学精品课）
第7章图
一、选择题
1．设无向图的顶点个数为n，则该图最多有（）条边。
查看答案
A．n-1 B．n(n-1)/2
C．n(n+1)/2 D．n2
正确答案是B
解释: n个顶点相互都有关系，即边数最多。
边数=（n-1）+（n-2）+......+0=n(n-1)/2收起
2．要连通具有n个顶点的有向图，至少需要（）条边。
查看答案
A．n-l B．n
C．n+l D．2n
正确答案是B
解释:有向图要连通边数最少为n条，形成环。
收起
3．一个有n个结点的图，最少有（）个连通分量查看答案
A．0 B．1
C．n-1 D．N
正确答案是B
解释:图是连通图连通分量最少，即1个。
收起
4．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
查看答案
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
正确答案是A收起
5. 关键路径是事件结点网络中（）。
查看答案
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
正确答案是A
解释:关键路径是由关键顶点和关键活动组成的。
收起
6. 求解最短路径的Floyd算法的时间复杂度为( )。
查看答案
A．O（n） B. O（n+c）
C. O（n*n）
D. O（n*n*n）
正确答案是D收起
7. 下列说法不正确的是（）。
查看答案
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
C．图的深度遍历不适用于有向图
B．遍历的基本算法有两种：深度遍历和广度遍历
D．图的深度遍历是一个递归过程
正确答案是B
解释:图的深度遍历同样适用于有向图，算法中每个顶点均出发一次。
收起
8．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。
查看答案
A．1/2 B．2
C．1 D．4
正确答案是B
解释:无向图中每条边连接两个顶点，算顶点度数时一条边被算两次，
因此度数之和是边数的2倍。
收起
9．无向图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．a,b,e,c,d,f B．a,c,f,e,b,d
C．a,e,b,c,f,d D．a,e,d,f,c,b
正确答案是D
解释:深度优先遍历采用递归的方式。
收起
10. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。
查看答案
A. O(n)
B. O(n＋e)
C. O(n*n)
D. O(n*n*n)
正确答案是B收起
二、填空题
1．具有10个顶点的无向图，边的总数最多为______。
查看答案
正确答案是45
解释:10个点组成的无向完全图。
收起
2．G是一个非连通无向图，共有28条边，则该图至少有______个顶点。
查看答案
正确答案是9
解释:若28条边构成的是无向完全图，则再多一个顶点就是最少有可能是图不连通的情况。
n*（n-1）/2=28，得n=8，所以至少有9个顶点图就有可能不连通。
收起
3. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
查看答案
正确答案是深度优先遍历。
收起
4．构造连通网最小生成树的两个典型算法是______。
查看答案
正确答案是普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法。
收起
5. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网
的最小生成树。
查看答案
正确答案是边稠密边稀疏
解释：普里姆算法的时间复杂度O(n2），只和顶点数有关，所以适合边稠密的图。
克鲁斯卡尔算法的时间复杂度是O(eloge)，所以边稀疏的图时间复杂度低。
收起
6. 有向图G=(V,E),其中V(G)={0,1,2,3,4,5}，用<a,b,d>三元组表示弧<a,b>及弧上的权 d.E(G)为{<0,5,100>,<0,2,10><1,2,5><0,4,30><4,5,60><3,5,10><2,3,50><4,3,20>}，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。
查看答案
正确答案是50，经过中间顶点④
解释：采用迪杰斯特拉算法收起
7. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。
（1）．查邻接表中入度为___（1）___的顶点，并进栈；
（2）．若栈不空，则①输出栈顶元素Vj，并退栈；②查Vj的直接后继Vk，对Vk入度处理，处理方法是___（2）___；
（3）．若栈空时，输出顶点数小于图的顶点数，说明有__（3）____，否则拓扑排序完成。
查看答案
正确答案是（1）零（2）V k度减1，若V k入度己减到零，则V k顶点入栈（3）环
收起
8．下图中的强连通分量的个数为______个。
查看答案
正确答案是3
解释：连通分量是极大连通子图。
收起
三、应用题
1．请回答下列关于图(Graph)的一些问题：
（1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边?
（2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？（3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？查看答案
正确答案：
（1）n(n-1)，n
(2) 106，不一定是稀疏矩阵（稀疏矩阵的定义是非零个数远小于该矩阵元素个数，且分布无规律）
（3）使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。
若在执行dfs(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。
收起
2．解答问题。
设有数据逻辑结构为：
B = (K, R), K = {k1, k2, …, k9}
R={<k1, k3>, <k1, k8>, <k2, k3>,<k2, k4>, <k2, k5>, <k3, k9>,<k5, k6>, <k8, k9>, <k9, k7>, <k4, k7>, <k4, k6>}
（1）．画出这个逻辑结构的图示。
（2）．相对于关系r, 指出所有的开始接点和终端结点。
（3）．分别对关系r中的开始结点，举出一个拓扑序列的例子。
查看答案
正确答案:
（2）开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。
（3）拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7收起
K2，K1，K3，K4，K5，K6，K8，K9，K7
规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。
3．将如下图所示的无向图，写出对其分别进行深度，广度优先遍历的结果。
查看答案
正确答案：深度优先遍历序列：125967384
广度度优先遍历序列：123456789
这里的遍历，均从顶点1开始收起。