数据结构单元5 同步训练及答案.docx
《数据结构单元5 同步训练及答案.docx》由会员分享，可在线阅读，更多相关《数据结构单元5 同步训练及答案.docx（11页珍藏版）》请在冰点文库上搜索。
数据结构单元5同步训练及答案
单元5同步训练
一、单项选择题
1．在一个图中,所有顶点的度数之和等于所有边数的（）倍。
A．1/2B．1C．2D．4
2．在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。
A．1/2B．1C．2D．4
3．一个有n个顶点的无向图最多有（）条边。
A．nB．n（n-1）C．n（n-1）/2D．2n
4．具有4个顶点的无向完全图有（）条边。
A．6B．12C．16D．20
5．具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。
A．5B．6C．7D．8
6．在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。
A．nB．n+1C．n-1D．n/2
7．对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵含元素的个数是（）。
A．nB．（n-1）2C．n-1D．n2
8．含n个顶点的连通图中的任何一条简单路径，其长度不可能超过（）。
A．1B．n/2C．n-1D．n
9．对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（）。
A．nB．n+1C．n-1D．n+e
10．已知无向图如图5-19所示,若从顶点a出发按深度搜索法进行遍历,则可能得到的一种顶点序列为（）。
A．a,b,e,c,d,fB．a,c,f,e,b,d
C．a,e,b,c,f,dD．a,e,d,f,c,b
11．已知一有向图的邻接表存储结构如图5-20所示。
根据有向图的深度优先遍历算法,从顶点v1出发,所得到的顶点序列是（）。
A．v1,v2,v3,v5,v4B．v1,v2,v3,v4,v5
C．v1,v3,v4,v5,v2D．v1,v4,v3,v5,v2
12．已知一有向图的邻接表存储结构如上图所示，根据有向图的广度度优先遍历算法，从顶点v1出发，所得到的顶点序列是（）。
A．v1,v2,v3,v4,v5B．v1,v3,v2,v4,v5
C．v1,v2,v3,v5,v4D．v1,v4,v3,v5,v2
13．采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。
A．先序遍历B．中序遍历
C．后序遍历D．按层遍历
14．在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。
A．eB．2eC．n2-eD．n2-2e
15．任何一个无向连通图的最小生成树（）。
A．只有一棵B．一棵或多棵
C．一定有多棵D．可能不存在
二、问题解答题
1．在图5-21所示的有向图中：
该图是强连通的吗?
若不是，则给出其强连通分量。
请给出所有的简单路径。
请给出每个顶点的度，入度和出度。
2．对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题？
图中有多少条边?
：
任意两个顶点i和j是否有边相连?
任意一个顶点的度是多少?
3．用Prim和Kruskal求最小生成树的时间复杂度各为多少?
它们分别适合于哪类图?
4．对图5-22所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。
5．对下图所示的有向图，试利用Dijkstra算法求出从源点1到其它各顶点的最短路径，并写出执行算法过程中扩充红点集的每次循环状态。
6．试写出如图5-24所示有向图的所有拓扑序列。
三、算法设计题
1．试分别写出求DFS和BFS生成树（或生成森林）的算法，要求打印出所有的树边。
2．试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和vj（i<>j）之间是否有路径。
单元5参考答案
一、选择题
1、C2、B3、C4、A5、A
6、C7、D8、A9、D10、D
11、B12、D
二、解答题
1、答：
（1）该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。
（2）简单路径是指在一条路径上只有起点和终点可以相同的路径：
v1v2、v1v3、v2v4、v3v4、v4v1、v1v2v4、v1v3v4、v2v4v1、v3v4v1、v4v1v2、v4v1v3、v1v3v4、v1v2v4v1、v1v3v4v1、v2v4v1v2、v2v4v1v3、v3v4v1v3、v3v4v1v2、v4v1v2v4、v4v1v3v4
（3）每个顶点的度、入度和出度：
D（v1）=3，ID（v1）=1，OD（v1）=2；D（v2）=2，D（v2）=1，OD（v2）=1；D（v3）=2，ID（v3）,1，OD（v3）=1；D（v4）=3，ID（v4）,2，OD（v4）=1。
2、答：
图中有多少条边?
：
邻接矩阵表示：
无向图：
邻接矩阵中非零元个数的一半或上三角矩阵非零元的个数或下三角矩阵非零元的个数。
有向图：
邻接矩阵中非零元的个数。
邻接表表示：
无向图：
每个顶点边表结点个数的和的一半。
有向图：
每个顶点边表结点个数的和。
任意两个顶点i和j是否有边相连?
邻接矩阵表示：
无向图：
邻接矩阵中第i行第j列（或第j行第i列）元素是否非零。
有向图：
邻接矩阵中第i行第j列元素是否非零。
邻接表表示：
无向图：
第i个（第j个）顶点的边表是否有值为j（i）的结点。
有向图：
第i个顶点的边表是否有值为j的结点。
任意一个顶点的度是多少?
邻接矩阵表示：
无向图：
顶点vi的度为：
第i行（或第i列）非零元的个数。
有向图：
顶点vi的度为：
第i行非零元的个数与第i列非零元的个数的和（顶点vi的出度为：
第i行非零元的个数，入度为：
第i列非零元的个数）。
邻接表表示：
无向图：
该顶点边表结点的个数。
有向图：
顶点vi的度为：
该顶点边表结点的个数与其他顶点的边表中值为i的结点个数的和。
三、算法设计题
1、答：
（1）求DFS生成树
typedefenum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Booleanvisited[MaxVertexNum]；//访问标志向量是全局量
voidDFSTraverseTREE（ALGraph*G）
{//求深度优先生成树（以邻接表表示的图G），而以邻接矩阵表示G时，
//算法完全与此相同,只要将DFSTree（G，i）改为DFSMTree（G，i）即可
inti；
for（i=0;in;i++）
visited[i]=FALSE；//标志向量初始化
for（i=0;in；i++）
if（!
visited[i]）//vi未访问过
DFSTree（G，i）；//以vi为源点开始DFS搜索,求DFS生成树的边
}//DFSTraverse
voidDFSTree（ALGraph*G，inti）{
//以vi为出发点对邻接表表示的图G进行深度优先搜索,打印生成树（生成森林）的边
EdgeNode*p；
visited[i]=TRUE；//标记vi已访问
p=G->adjlist[i].firstedge；//取vi边表的头指针
while（p）{//依次搜索vi的邻接点vj，这里j=p->adjvex
if（!
visited[p->adjvex]）//若vj尚未被访问
{printf（"（%c,%c）\n",G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex） ；
//打印边
DFSTree（g，p->adjvex）;//则以Vj为出发点向纵深搜索
}
p=p->next；//找vi的下一邻接点
}
}//DFS
voidDFSMTree（MGraph*G，inti）
{//以vi为出发点对邻接矩阵表示的图G进行深度优先搜索,打印生成树（生成森林）的边
intj；
visited[i]=TRUE；
for（j=0；jn；j++）//依次搜索vi的邻接点
if（G->edges[i][j]==1&&!
visited[j]）
{
printf（"（%c,%c）\n",G->vexs[i],G->vexs[j]）;//打印边
DFSMTree（G，j）;//（vi，vj）∈E，且vj未访问过，故vj为新出发点
}
}//DFSMTree
（2）求BFS生成树
typedefenum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
Booleanvisited[MaxVertexNum]；//访问标志向量是全局量
voidBFSTraverseTREE（ALGraph*G）
{//求广度优先生成树（以邻接表表示的图G），而以邻接矩阵表示G时，
//算法完全与此相同,只要将BFSTree（G，i）改为BFSMTree（G，i）即可
inti；
for（i=0;in;i++）
visited[i]=FALSE；//标志向量初始化
for（i=0;in；i++）
if（!
visited[i]）//vi未访问过
BFSTree（G，i）；//以vi为源点开始BFS搜索,求BFS生成树的边
}//BFSTraverse
voidBFSTree（ALGraph*G，intk）
{//以vk为源点对用邻接表表示的图G进行广度优先搜索,并求出BFS生成树边
inti；
CirQueueQ；//须将队列定义中DataType改为int
EdgeNode*p；
InitQueue（&Q）；//队列初始化
visited[k]=TRUE；
EnQueue（&Q，k）；//vk已访问，将其人队。
（实际上是将其序号人队）
while（!
QueueEmpty（&Q））{//队非空则执行
i=DeQueue（&Q）；//相当于vi出队
p=G->adjlist[i].firstedge；//取vi的边表头指针
while（p）{//依次搜索vi的邻接点vj（令p->adjvex=j）
if（!
visited[p->adivex]）{//若vj未访问过
printf（"（%c,%c）\n"，G->adjlist[i].vertex,G->adjlist[p->adjvex].vertex）；
//打印边
visited[P->adjvex]=TRUE；
EnQueue（&Q，p->adjvex）；／／访问过的vj人队
}//endif
p=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
}//endofBFSTree
voidBFSMTree（MGraph*G，intk）
{//以vk为源点对用邻接矩阵表示的图G进行广度优先搜索,并求出BFS生成树边
inti，j；
CirQueueQ；
InitQueue（&Q）；
visited[k]=TRUE；
EnQueue（&Q，k）；
while（!
QueueEmpty（&Q））{
i=DeQueue（&Q）；//vi出队
for（j=0;jn;j++）//依次搜索vi的邻接点vj
if（G->edges[i][j]==1&&!
visited[j]）{//vi未访问
printf（"（%c,%c）\n"，G->vexs[i],G->vexs[j]）；//打印边
visited[j]=TRUE；
EnQueue（&Q，j）；//访问过的vj人队
}
}//endwhile
}//BFSMTree
2、答：
（1）基于采用邻接矩阵的DFS
intpathDFSM（MGraph*G，inti,intj）
{//以邻接矩阵为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
intk;
visited[i]=TRUE；
for（k=0；kn；k++）//依次搜索vi的邻接点
if（G->edges[i][k]==1&&!
visited[k]）
if（k==j）return1;//有路径相通
elsereturn（pathDFSM（G,k,j）;
return0;//无路径相通
}//DFSM
（2）基于采用邻接表的DFS
intPATHDFS（ALGraph*G，inti,intj）{
//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
EdgeNode*p；
visited[i]=TRUE；//标记vi已访问
p=G->adjlist[i].firstedge；//取vi边表的头指针
while（p）{//依次搜索vi的邻接点vk，这里k=p->adjvex
if（!
visited[p->adjvex]）//若vk尚未被访问
if（p->adjvex==j）
return1;
elseruturnPATHDFS（g，p->adjvex,j）;//则以Vk为出发点向纵深搜索
p=p->next；//找vi的下一邻接点
}
return0;
}//PATHDFS
（3）基于邻接矩阵的BFS算法
intpathBFSM（MGraph*G，inti,intj）
{//以邻接矩阵为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
intk；
CirQueueQ；
initQueue（&Q）；
visited[i]=TRUE；
EnQueue（&Q，i）；
while（!
QueueEmpty（&Q））{
i=DeQueue（&Q）；//vi出队
for（k=0;kn;k++）//依次搜索vi的邻接点vk
if（G->edges[i][k]==1&&!
visited[k]）{//vk未访问
if（k==j）return1;
visited[k]=TRUE；
EnQueue（&Q，k）；//访问过的vk人队
}
}//endwhile
return0;
}//pathBFSM
（4）基于邻接表为存储结构的BFS算法
intBFS（ALGraph*G，inti,intj）
{//以邻接表为存储结构，判断vi和vj之间是否有路径，若有返回1，否则返回0
inti；
CirQueueQ；//须将队列定义中DataType改为int
EdgeNode*p；
InitQueue（&Q）；//队列初始化
visited[i]=TRUE；
EnQueue（&Q，i）；//vi已访问，将其人队。
（实际上是将其序号人队）
while（!
QueueEmpty（&Q））{//队非空则执行
i=DeQueue（&Q）；//相当于vi出队
p=G->adjlist[i].firstedge；//取vi的边表头指针
while（p）{//依次搜索vi的邻接点vk（令p->adjvex=k）
if（!
visited[p->adjvex]）//若vk未访问过
if（p->adjvex==j）
return1;
else{
visited[P->adjvex]=TRUE；
EnQueue（&Q，p->adjvex）；
}//访问过的vk人队
p=p->next；//找vi的下一邻接点
}//endwhile
}//endwhile
return0;
}//endofpathBFS
升级会员 