淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 21
第7章 图
一、选择题：
1、在一个具有n个结点的无向图中，要连通全部结点至少需要（ ） A．n条边 B．n+1条边 C．n-1条边 D．n/2条边 2、最小生成树指的是（ ）
A．由连通图所得到的边数最少的生成树 B．由连通图所得到的顶点相对较少的生成树 C．连通图的所有生成树中权值之和最小的生成树 D．连通图的极小连通子图
3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ） A．1/2倍 B．1倍 C．2倍 D．4倍 4、有n个结点的无向图的边数最多为（ ）
A．n+1 B．n（n-1）/2 C．n（n+1） D．2n（n+1）
5、若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个（ ） A．一般矩阵 B．对称矩阵 C．对角矩阵 D．稀疏矩阵
6、设有一个有向图如下所示，请指出下列（ ）序列不是该图的拓扑排序序列？
A.EAFBGDC B.AEBCGFD C.ABCEGFD D.EBAGFCD 7、拓扑排序是对（ ）进行的。
A.无向图 B. 有向图 C.任意图 D.有向图和无向图 8、下面哪一种图的邻接矩阵肯定是对称矩阵（ ）。
A．有向图 B. 无向图 C. AOV网 D. AOE网
9、设有向图G有n个顶点，它的邻接矩阵为A，G中第i个顶点Vi的度为（ ）。
A.
?A[j,i] B. ?A[i,j]
j?1j?1nnnC.
?(A[i,j]?A[j,i]) D. 2?A[j,i]
j?1j?1n10、深度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 11、有n个顶点的无向图的邻接矩阵是用（ ）数组存储。
A．n行n列 B．一维 C．任意行n列 D．n行任意列 12、最小生成树的构造可使用（ ）。
A．prim算法 B．冒泡算法 C．迪杰斯特拉算法 D．哈夫曼算法 13、有8个结点的有向完全图有（ ）条边。
A．14 B．28 C．56 D．112 14、有8个结点的无向图最多有（ ）条边。
A．14 B．28 C．56 D．112
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 22
15、广度优先遍历类似于二叉树的（ ）
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历
16、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（ ）。
A． e B．2e C．n2-e D．n2-2e 17、在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。 A． 1/2 B．1 C．2 D．4 18、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）。
A． 深度优先搜索算法 B． 广度优先搜索算法 C．求最小生成树的prim算法 D．拓扑排序算法 19、n个顶点的完全有向图中含有( )。
A．n-1条有向边 B．n条有向边 C．n(n-1)/2条有向边 D．n(n-1)条有向边
20、在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（ ）。
A． 顶点序列 B．边序列 C．权值总和 D．边的条数 21、下面（ ）方法可以判断出一个有向图是否有环（回路）。
A． 求节点的度 B．拓扑排序 C．求最短路径 D．求关键路径
22、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A． 从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路
24、设图的邻接链表如下图所示，则该图的边的数目是（ ）。
25题图 A． 4 B．5 C．10 D．20 25、有8个结点的无向连通图最少有（ ）条边。
A． 5 B． 6 C． 7 D． 8
26、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ）。 ?0111101??1001001?
?? ?1000100??? 1100110?? ?1011010???
0001101?? ??1100010??
A． 0 2 4 3 1 5 6 B． 0 1 3 5 6 4 2 C． 0 4 2 3 1 6 5 D． 0 1 3 4 2 5 6
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 23
27、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ ）。
A．0 1 3 2 B． 0 2 3 1 C． 0 3 2 1 D． 0 1 2 3
28、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ ）。
A． 0 3 2 1 B． 0 1 2 3 C． 0 1 3 2 D． 0 3 1 2
二、填空题：
1、已知一个图用邻接矩阵表示，计算第i个结点的入度的方法是（ ）。 2、图的逆邻接表存储结构只适用于（ ）图。
3、若要求一个稀疏图的最小生成树，最好用（ ）算法来求解；若要求一个稠密图G的最小生
成树，最好用（ ）算法来求解。
4、在有向图中，以顶点v为终点的边的数目称为v的（ ）。
5、一个无向图有n个顶点，e条边，则所有顶点的度数之和为（ ）。
6、图有（ ）、（ ）等存储结构，遍历图有（ ）、（ ）等方法。 7、有向图G用邻接表矩阵存储，其第i行的所有非零元素之和等于顶点i的（ ）。 8、图的BFS生成树的树高比DFS生成树的树高 （ ） 。
9、Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（ ）的次序来得到最短路
径的。
10、拓扑排序算法是通过重复选择具有（ ）个前驱顶点的过程来完成的。
三、判断题：
1、有回路的图不能进行拓扑排序。 （ ） 2、连通分量是无向图中的极小连通子图。 （ ） 3、强连通分量是有向图中的极大强连通子图。 （ ） 4、任何一个有向图，其全部顶点可以排成一个拓扑序列。 （ ）
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 24
四、应用题：
1、写出下面有向图的邻接矩阵表示和拓扑排序序列。 6 1 2 3 5 答：
2.已知有向图如右图所示， 请给出该图的：
(1) 各个顶点的入度、出度 (2) 邻接矩阵示意图 (3) 邻接表示意图 (4) 逆邻接表示意图
答：
4V1 V5 V6 V2 V4 V3