数据结构单元8练习参考答案.docx
《数据结构单元8练习参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构单元8练习参考答案.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构单元8练习参考答案
单元练习8
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）
（√）
（1）图可以没有边，但不能没有顶点。
（ㄨ）
（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。
（ㄨ）（3）邻接表只能用于有向图的存储。
（√）（4）一个图的邻接矩阵表示是唯一的。
（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。
（ㄨ）（6）有向图不能进行广度优先遍历。
（√）（7）若一个无向图的以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。
（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。
（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。
（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。
二．填空题
（1）图常用的存储方式有邻接矩阵和邻接表等。
（2）图的遍历有：
深度优先搜和广度优先搜等方法。
（3）有n条边的无向图邻接矩阵中，1的个数是_2n____。
（4）有向图的边也称为_弧___。
（5）图的邻接矩阵表示法是表示__顶点____之间相邻关系的矩阵。
（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的__出度____。
（7）n个顶点e条边的图若采用邻接矩阵存储，则空间复杂度为：
O（n2）。
（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：
O（n+e）。
（9）设有一稀疏图G，则G采用_邻接表____存储比较节省空间。
（10）设有一稠密图G，则G采用_邻接矩阵____存储比较节省空间。
（11）图的逆邻接表存储结构只适用于__有向____图。
（12）n个顶点的完全无向图有n（n-1）/2_条边。
（13）有向图的邻接表表示适于求顶点的出度。
（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点Vi的入度。
（15）对于具有n个顶点的图，其生成树有且仅有n-1条边。
（16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e个结点。
（17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图
的遍历。
（18）无向图的邻接矩阵一定是对称矩阵。
（19）一个连通网的最小生成树是该图所有生成树中权最小的生成树。
（20）若要求一个稠密图G的最小生成树，最好用Prim算法来求解。
三．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的（C）倍。
A．1/2B.1C.2D.4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。
A．1/2B.1C.2D.4
（3）对于一个具有n个顶点的有向图的边数最多有（B）。
A．nB．n（n-1）C．n（n-1）/2D．2n
（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。
A．nB．n+1C．n-1D．n/2
（5）有8个结点的有向完全图有（C）条边。
A．14B.28C.56D.112
（6）深度优先遍历类似于二叉树的（A）。
A．先序遍历B．中序遍历C．后序遍历D．层次遍历
（7）广度优先遍历类似于二叉树的（D）。
A．先序遍历B．中序遍历C．后序遍历D．层次遍历
（8）任何一个无向连通图的最小生成树（A）。
A．只有一棵B．一棵或多棵C．一定有多棵D．可能不存在
（9）无向图顶点v的度是关联于该顶点（B）的数目。
A．顶点B．边C．序号D．下标
（10）有n个顶点的无向图的邻接矩阵是用（B）数组存储。
A．一维B．n行n列C．任意行n列D．n行任意列
（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。
A．n-1B．n+1C．nD．n+e
（12）在图的表示法中，表示形式唯一的是（A）。
A．邻接矩阵表示法B．邻接表表示法
C．逆邻接表表示法D．邻接表和逆邻接表表示法
（13）在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。
A．nB．eC．2nD．2e
（14）下列图中，度为3的结点是（B）。
A．V1B.V2C.V3D.V4
（15）下列图是（A）。
A．连通图B.强连通图C.生成树D.无环图
（16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（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
（17）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。
A.a，b，e，c，d，f
B.a，b，e，c，f，d
C.a，e，b，c，f，d
D.a，e，d，f，c，b
（18）最小生成树的构造可使用（A）算法。
A．prim算法B．卡尔算法C．哈夫曼算法D．迪杰斯特拉算法
（19）下面关于图的存储结构的叙述中正确的是（A）。
A．用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关
B．用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关
C．用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关
D．用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关
（20）连通分量是（C）的极大连通子图。
A．树B．图C．无向图D．有向图
四．应用题（30分）
1．有向图如下图所示，画出邻接矩阵和邻接表
解：
（1）邻接矩阵
12345
（2）邻接表
1
2
3
5
∧
2
4
∧
3
5
∧
4
1
∧
5
4
∧
2．已知一个无向图有6个结点，9条边，这9条边依次为（0，1）,（0，2）,（0，4）,（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。
试画出该无向图，并从顶点0出发，分别写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。
（5分）
2
3
1D
0
4
5
解：
从顶点0出发的深度优先搜索遍历的结点序列：
012345（答案不唯一）
从顶点0出发的广度优先搜索遍历的结点序列：
012453（答案不唯一）
3．已知一个无向图的顶点集为：
{a，b，c，d，e}，其邻接矩阵如下，画出草图，写出顶点a出发按深度优先搜索进行遍历的结点序列。
（5分）
解：
（1）
（2）深度优先搜索：
abdce（答案不唯一）
广度优先搜索：
abedc（答案不唯一）
4．网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。
解：
最小生成树：
811
108
34
13734
7
5.已知某图G的邻接矩阵如图，
（1）画出相应的图；
（2）要使此图为完全图需要增加几条边。
解：
（1）
（2）完全无向图应具有的边数为：
n*（n-1）1/2=4*（4-1）/2=6，所以还要增加2条边（如右图）。
6．已知如图所示的有向图，请给出该图的:
（1）每个顶点的入/出度；
（2）邻接表；
（3）邻接矩阵。
解：
（1）
（2）
顶点
1
2
3
4
5
6
入度
3
2
1
1
2
2
出度
0
2
2
3
1
3
（3）
7．如图，请完成以下操作：
（2）写出无向带权图的邻接矩阵；
（3）设起点为a，求其最小生成树。
解：
（1）邻接矩阵为：
（2）起点为a，可以直接由原始图画出最小生成树
8．给定下列网G:
（1）画出网G的邻接矩阵；
（2）画出网G的最小生成树。
解：
（1）邻接矩阵
（2）最小生成树
五．程序题填空题
图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边（v,w）的操作：
DeleteArc（G,v,w）。
若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返回“OK”。
（提示：
删除一条边的操作，可以将邻接矩阵的第i行全部置0）
解：
StatusDeleteArc（MGraph&G,charv,charw）dj）
{[i][j].adj=0;
--;（或=）
}
returnOK;
}
六．算法题
1．编写一个无向图的邻接矩阵转换成邻接表的算法。
2．以知有n个顶点的有向图邻接表，设计算法分别实现以下功能：
（1）求出图G中每个顶点的出度、入度。
（2）求出G中出度最大的一个顶点，输出其顶点序号。
（3）计算图中度为0的顶点数。
1．解：
本题思想是逐个扫描邻接矩阵的各个元素，若第i行第j列的元素为1，则相应的邻接表的第i个单链表上增加一个j结点。
voidtrans（intedges[n][n],Adjlistadj）
{inti,j;
edgenode*p;
for（i=0;i{adj[i].data=i;
adj[i].link=NULL;
}
for（i=0;ifor（j=0;j{if（edges[i][j]==1）
{p=（edgenode*）malloc（sizeof（edgenode））;
p->adjvex=j;
p->next=adj[i].link;
adj[i].link=p;
}
}
}
2．
（1）求出度的思想：
计算出邻接表中第i个单链表的结点数即可。
intoutdegree（adjlistadj,intv）
{intdegree=0;
edgenode*p;
p=adj[v].link;
while（p!
=NULL）
{degree++;
p=p->next;
}
returndegree;
}
voidprintout（adjlistadj,intn）
{inti,degree;
printf（"TheOutdegreeare:
\n"）;
for（i=0;i{degree=outdegree（adj,i）;
printf（"（%d,%d）",i,degree）;
}
}
求入度的思想：
计算出邻接表中结点i的结点数即可。
intindegree（adjlistadj,intn,intv）
{inti,j,degree=0;
edgenode*p;
for（i=0;i{p=adj[i].link;
while（p!
=NULL）
{if（p->adjvex==v）
degree++;
p=p->next;
}
}
returndegree;
}
voidprintin（adjlistadj,intn）
{inti,degree;
printf（"TheIndegreeare:
\n"）;
for（i=0;i{degree=Indegree（adj,n,i）;
printf（"（%d,%d）",i,degree）;
}
}
（2）求最大度的算法
voidmaxoutdegree（adjlistadj,intn）
{intmaxdegree=0,maxv=0,degree,i;
for（i=0;i{degree=outdegree（adj,i）;
if（degree>maxdegree）
{maxdegree=degree;
maxv=i;
}
}
printf（"maxoutdegree%d,maxvertex=%d",maxdegree,maxv）;
}
（3）求度为0的顶点数的算法
intoutzero（adjlistadj,intn）
{intnum=0,i;
for（i=0;i{if（outdegree（adj,i）==0）
num++;
}
returnnum;
}
模拟考题
1．已知如图所示的有向图，请给出该图的:
（1）每个顶点的入度和出度；
（2）逆邻接表。
解：
（1）
（2）
顶点
1
2
3
4
5
6
入度
3
2
1
1
2
2
出度
0
2
2
3
1
3
2．给定下列网G:
（1）写出网G以B为顶点的广度优先遍历的序列；
（2）画出网G的最小生成树。
解：
（1）以B为顶点的广度优先遍历的序列：
（2）最小生成树
F
B
ED
A
C
G
D
BAEFCGD
3．无向图G如图所示，
（1）试画出邻接矩阵；
（2）写出从A出发的深度优先遍历的序列。
D
C
AD
B
G
E
F
解：
（1）邻接矩阵
（2）从A出发的深度优先遍历的序列：
ABDCEGF（不唯一）
3．已知图G的邻接表如下，以顶点1为出发点，完成下列问题：
1
2
5
4
∧
2
3
1
∧
3
5
2
∧
4
1
5
∧
5
4
1
3
∧
（1）写出以顶点1为出发点的广度优先遍历序列；
（2）画出以顶点1为出发点的深度优先搜索得到的一棵二叉树。
解：
（1）广度优先遍历序列：
1，2，5，4，3
（2）深度优先搜索得到的一棵二叉树：
5．试填空完成深度优先搜索的递归函数。
#defineMAXVEX100//定义图的最大顶点数
structvertex
{intnum;//顶点编号
chardata;//顶点的信息
};
typedefstructgraph
{structvertexvexs[MAXVEX];//顶点集合
intedges[MAXVEX][MAXVEX];//边的集合
}sdjmax;
intvisited[MAXVEX];
voiddfs（adjlistadj,intv）//深度优先搜索的递归函数
{inti;
structedgenode*p;
for（i=1;i<=n;i++）
visited[i]=0;//给visited数组赋初值0
visited[v]=1;
cinv;//取v的边的表头指针
p=adj[v]->link;
while（p!
=NULL）
{if（visited[p->adjvex]==0）//从v的未访问过的邻接点出发进行深度优先搜索
dfs（adjlist,p->adjvex）;
p=p->next;//找v的下一个邻接点
}
}
升级会员 