数据结构期末试题及答案样卷7文档格式.docx
《数据结构期末试题及答案样卷7文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构期末试题及答案样卷7文档格式.docx（13页珍藏版）》请在冰点文库上搜索。
A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构
10、下面有向图所示的拓扑排序的结果序列是（）。
A.125634 B.516234C.123456D.521643
11、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（）。
A.顶点序列B.边序列C.权值总和D.边的条数
12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。
A.入边B.出边C.入边和出边D.不是出边也不是入边
13、设G1=（V1,E1）和G2=（V2,E2）为两个图，如果V1V2,E1E2则称（）。
A.G1是G2的子图B.G2是G1的子图C.G1是G2的连通分量D.G2是G1的连通分量
14、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。
A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为0
15、任一个有向图的拓扑序列（）。
A.不存在B.有一个C.一定有多个D.有一个或多个
16、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A.1/2B.1C.2D.4
17、下列关于图遍历的说法不正确的是（）。
A.连通图的深度优先搜索是一个递归过程
B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C.非连通图不能用深度优先搜索法
D.图的遍历要求每一顶点仅被访问一次
18、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中：
（）。
A.第i行非的元素之和B.第i列非的元素之和
C.第i行非且非0的元素个数D.第i列非且非0的元素个数
19、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。
A.先序遍历B.中序遍历C.后序遍历D.按层次遍历
20、一个具有n个顶点的有向图最多有（）条边。
A.n×
（n-1）/2B.n×
（n-1）C.n×
（n+1）/2D.n2
21、已知一个有向图的邻接表存储结构如图所示，根据深度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。
A.v1,v2,v3,v5,v4B.v1,v2,v3,v4,v5
C.v1,v3,v4,v5,v2D.v1,v4,v3,v5,v2
22、关键路径是事件结点网络中（）。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
23、以下说法正确的是（）。
A.连通分量是无向图中的极小连通子图
B.强连通分量是有向图中的极大强连通子图
C.在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧<
a,b>
D.对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
24、假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（）。
A.nB.eC.2eD.n*e
25、设图的邻接矩阵为
，则该图为（）。
A.有向图B.无向图C.强连通图D.完全图
26、为便于判别有向图中是否存在回路，可借助于（）。
A.广度优先搜索算法B.最小生成树算法
C.最短路径算法D.拓扑排序算法
27、任何一个无向连通图的最小生成树（）种。
A.只有一棵 B.有一棵或多棵C.一定有多棵D.可能不存在
28、已知一有向图的邻接表存储结构如图所示，根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。
A.v1,v2,v3,v4,v5B.v1,v3,v2,v4,v5C.v1,v2,v3,v5,v4D.v1,v4,v3,v5,v2
29、对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）。
A.k1 B.k2C.k1+k2D.k1-k2
30、一个具有8个顶点的有向图中，所有顶点的入度之和与所有顶点的出度之和的差等于（）。
A.16B.4C.0D.2
31、无向图中一个顶点的度是指图中（）。
A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数
C.与该顶点连通的顶点数D.通过该顶点的回路数
二、填空题
1、n个顶点的连通图至少有边。
答案：
n-1条
2、一个连通图的生成树是一个，它包含图中所有顶点，但只有足以构成一棵树的n-1条边。
极小连通子图
3、一个图的表示法是惟一的。
邻接矩阵
4、遍历图的基本方法有深度优先搜索和广度优先搜索，其中是一个递归过程。
深度优先搜索
5、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于。
1
6、判定一个有向图是否存在回路，可以利用。
拓扑排序
7、已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是。
8、n个顶点的无向图最多有边。
9、已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是。
10、若以邻接矩阵表示有向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的。
三、判断题
1、图的连通分量是无向图的极小连通子图。
2、一个图的广度优先搜索树是惟一的。
3、图的深度优先搜索序列和广度优先搜索序列不是惟一的。
4、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。
5、存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
6、AOV网是一个带权的有向图。
7、从源点到终点的最短路径是唯一的。
8、邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。
9、图的生成树是惟一的。
四、程序分析题
1、写出下面算法的功能。
typedefstruct{
intvexnum,arcnum;
charvexs[N];
intarcs[N][N];
}graph;
voidfuntion（inti,graph*g）{
intj;
printf（"
node:
%c\n"
g->
vexs[i]）;
visited[i]=TRUE;
for（j=0;
j<
g->
vexnum;
j++）if（（g->
arcs[i][j]==1）&
&
（!
visited[j]））
function（j,g）;
}
实现图的深度优先遍历算法
五、综合题
1、已知图G的邻接矩阵如下所示：
（1）求从顶点1出发的广度优先搜索序列；
（2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。
（用图或者表的方式均可）。
（1）广度优先遍历序列：
1;
2,3,4;
5;
6
（2）最小生成树（prim算法）
2、设一个无向图的邻接矩阵如下图所示：
（1）画出该图；
（2）画出从顶点0出发的深度优先生成树；
（1）图形态
（2）深度优先搜索树
3、写出下图中全部可能的拓扑排序序列。
1，5，2，3，6，41，5，6，2，3，45，1，2，3，6，4
5，1，6，2，3，45，6，1，2，3，4
4、AOE网G如下所示，求关键路径。
（要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径）
（1）最早发生时间和最迟发生时间：
（2）关键路径：
5、已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。
（给出求解过程）
终点
从v0到各终点的d值和最短路径的求解过程
i=1
i=2
i=3
i=4
v1
12（v0,v1）
7（v0,v4,v1）
v2
4（v0,v2）
v3
9（v0,v3）
8（v0,v2,v3）
7（v0,v4,v3）
v4
5（v0,v4）
vj
s
{v0,v2}
{v0,v4}
{v0,v4,v1}
{v0,v4,v3}
6、已知图G如下所示，根据Prim算法，构造最小生成树。
（要求给出生成过程）
prim算法求最小生成树如下：
7、已知有向图如下所示，请写出该图所有的拓扑序列。
拓扑排序如下：
v1,v2,v4,v6,v5,v3,v7,v8v1,v2,v4,v6,v5,v7,v3,v8
v1,v2,v6,v4,v5,v3,v7,v8v1,v2,v6,v4,v5,v7,v3,v8
v1,v6,v2,v4,v5,v3,v7,v8v1,v6,v2,v4,v5,v7,v3,v8
8、如下图所示的AOE网，求：
（1）求事件的最早开始时间ve和最迟开始时间vl；
事件
2
3
4
5
6
7
8
9
Ve
Vl
（2）求出关键路径；
（1）求ve和vl
（2）关键路径
如下所示的有向图，回答下面问题：
（1）该图是强连通的吗？
若不是，给出强连通分量。
（2）请给出图的邻接矩阵和邻接表表示。
（1）是强连通图
（2）邻接矩阵和邻接表为：
9、已知图G的邻接矩阵A=
，试画出它所表示的图G，并根据Prim算法求出图的的最小生成树（给出生成过程）。
（1）图形态：
（2）prim算法求最小生成树：
10、如下图所示的AOV网，写出其中三种拓扑排序序列。
11、已知图G如下，根据克鲁斯卡尔算法求图G的一棵最小生成树。
（要求给出构造过程）
kruskal算法的最小生成树
12、已知图G如下所示，求从顶点a到其余各顶点的最短路径。
最短路径求解过程
b
6（a,b）
5（a,c,b）
c
3（a,c）
d
6（a,c,d）
e
7（a,c,e）
f
9（a,c,d,f）
S
{a,c}
{a,c,b}
{a,c,d}
{a,c,e}
{a,c,d,f}
升级会员 