第七章知识点习题总结.docx
- 文档编号:1577252
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:20
- 大小:49.87KB
第七章知识点习题总结.docx
《第七章知识点习题总结.docx》由会员分享,可在线阅读,更多相关《第七章知识点习题总结.docx(20页珍藏版)》请在冰点文库上搜索。
第七章知识点习题总结
知识点一图的定义和术语
一、选择题
1.在一个图中,所有顶点的度数之和等于图的边数的()倍。
A.1/2B.1C.2D.4
答案:
C
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。
A.1/2B.1C.2D.4
答案:
B
3.有8个结点的无向图最多有()条边。
A.14B.28C.56D.112
答案:
B
4.有8个结点的无向连通图最少有()条边。
A.5B.6C.7D.8
答案:
C
5.有8个结点的有向完全图有()条边。
A.14B.28C.56D.112
答案:
C
6.强连通分量是()的极大强连通子图。
A.树B.图C.无向图D.有向图
答案:
D
7.在一个图中,所有顶点的度数之和等于图的边数的()倍。
A.1/2B.1C.2D.4
答案:
C
8.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的()倍。
A.1/2B.1C.2D.4
答案:
B
9.有8个结点的无向图最多有()条边。
A.14B.28C.56D.112
答案:
B
10.无向图顶点v的度是关联于该顶点()的数目。
A.顶点B.边C.序号D.下标
答案:
B
11.有8个结点的无向连通图最少有()条边。
A.5B.6C.7D.8
答案:
C
12.有8个结点的有向完全图有()条边。
A.14B.28C.56D.112
答案:
C
13.一个具有n个顶点e条边的图中,所有顶点的度数之和等于()。
A.nB.eC.2nD.2e
答案:
C
14.若图G中()都没有方向,则称G为无向图。
A.每条边B.部分边C.一条边D.每个顶点
答案:
A
15.对于一个具有n个顶点的无向图的边数最多有()。
A.nB.n(n-1)C.n(n-1)/2D.2n
答案:
C
16.对于一个具有n个顶点的有向图的边数最多有()。
A.nB.n(n-1)C.n(n-1)/2D.2n
答案:
B
17.具有4个顶点的无向完全图有()条边。
A.6B.12C.16D.20
答案:
A
18.在下列表示方法中,()是有向图边的表示方法。
A.(1,2)B.(1,2>C.<1,2)D.<1,2>
答案:
D
19.在下列表示方法中,()是有无向图边的表示方法。
A.(1,2)B.(1,2>C.<1,2)D.<1,2>
答案:
A
二、填空题
1.有n条边的无向图邻接矩阵中,1的个数是_____。
答案:
2n
2.若图G中每条边都方向,则G为无向图。
答案:
没有
3.n个顶点的完全无向图有条边。
答案:
n(n-1)/2
4.若图G中每条边都_____方向,则G为有向图。
答案:
有
5.在具有n个顶点的图的生成树中,含有条边。
答案:
n-1
6.有向图的边也称为____。
答案:
弧
三、简答题
1.画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。
试证明在n个顶点的无向完全图中,边的条数为n(n-1)/2。
答案:
2个顶点的
无向完全图
1个顶点的
无向完全图
5个顶点的
无向完全图
4个顶点的
无向完全图
3个顶点的
无向完全图
【证明】
在有n个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有n-1条边与其他n-1个顶点相连,总计n个顶点有n(n-1)条边。
但在无向图中,顶点i到顶点j与顶点j到顶点i是同一条边,所以总共有n(n-1)/2条边。
知识点二图的存储结构
一、选择题
1.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是().
A.nB.(n-1)2C.n-1D.n2
答案:
D
2.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大
为();
A.nB.(n-1)2C.n-1D.n2
答案:
A
3.有n个顶点的无向图的邻接矩阵是用()数组存储。
A.一维B.n行n列C.任意行n列D.n行任意列
答案:
B
4.n个顶点的无向图采用邻接矩阵存储方法,该邻接矩阵是一个()。
A.一般矩阵B.对称矩阵C.对角矩阵D.稀疏矩阵
答案:
B
5.有n个顶点的有向图的邻接矩阵是用()数组存储。
A.一维B.n行n列C.任意行n列D.n行任意列
答案:
B
6.有n个条边的无向图的邻接矩阵(表)存储法中,链表中结点的个数是()个。
A.n/2B.nC.2nD.n*n
答案:
C
7.有n个条边的有向图的邻接矩阵(表)存储法中,链表中结点的个数是()个。
A.n/2B.nC.2nD.n*n
答案:
B
8.下面关于图的存储结构的叙述中正确的是()。
A.用邻接矩阵存储图,占用空间大小只与图中顶点数有关,而与边数无关
B.用邻接矩阵存储图,占用空间大小只与图中边数有关,而与顶点数无关
C.用邻接表存储图,占用空间大小只与图中顶点数有关,而与边数无关
D.用邻接表存储图,占用空间大小只与图中边数有关,而与顶点数无关
答案:
A
9.在图的表示法中,表示形式唯一的是()。
A.邻接矩阵表示法B.邻接表表示法
C.逆邻接表表示法D.邻接表和逆邻接表表示法
答案:
A
二、填空题
1.图有等存储结构。
答案:
邻接矩阵,邻接表
2.有向图G用邻接表矩阵存储,其第i行的所有元素之和等于顶点i的。
答案:
出度
4.n个顶点e条边的图若采用邻接矩阵存储,则空间复杂度为_________。
答案:
5.n个顶点e条边的图若采用邻接表存储,则空间复杂度为__________。
答案:
O(n+e)
6.设有一稀疏图C,则C采用_存储较省空间。
答案:
邻接矩阵
7.设有一稠密图G,则G采用存储较省空间。
答案:
邻接表
8.图的逆邻接表存储结构只适用于图。
答案:
有向
9.已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的边的方法是
答案:
把第i行全部置零
10.图有:
__和邻接表等存储结构。
答案:
邻接矩阵
11.n个顶点e条边的图若采用邻接矩阵存储,则空间复杂度为:
。
答案:
O(n2)
12.n个顶点e条边的图若采用邻接表阵存储,则空间复杂度为:
。
答案:
O(n+e)
13.图的邻接矩阵表示法是表示______之间相邻关系的矩阵。
答案:
顶点
14.对n个顶点,e条弧的有向图,其邻接表表示中,需要个结点。
答案:
n+e
15.对n个顶点,e条边的无向图,其邻接表表示中,需要个结点。
答案:
n+2e
16.有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的______。
答案:
出度
17.设有一稀疏图G,则G采用_____存储比较节省空间。
答案:
邻接表
18.图的逆邻接表存储结构只适用于______图。
答案:
有向
19.设有一稠密图G,则G采用_____存储比较节省空间。
答案:
邻接矩阵
20.一个图的表示法是唯一的。
答案:
邻接矩阵
21..有向图的邻接表表示适于求顶点的。
答案:
出度
22..有向图的邻接矩阵表示中,第i列上非0元素的个数为顶点Vi的。
答案:
入度
三、简答题
1.下列函数是在有向图的邻接表中删除一条边的算法,请补充算法。
Voiddeledge(ALGraph*G,ihti,intj)
{EdgeNode*p,*q;
p=G->adjlistIii.firstedge;
if(_______
(1)_______){G->adjlist[i].firstedge=p->next;free(p);}
else{while(p->next->adjvex!
=j&&p->next)
__________________________
(2)________;
if(_________(3)____){q=p->next;_______(4)_______;free(q);}
}
)
答案:
(1)p->adjvex==j
(2)p=p->next
(3)p->next!
=null
(4)p->next=q->next
2.用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?
与边的条数是否相关?
答案:
用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。
矩阵中非零元素的个数与边的条数有关。
知识点三图的遍历
一、选择题
1.用邻接表表示图进行广度优先遍历时,通常采用()来实现算法的。
A.栈B.队列C.树D.图
答案:
B
2.用邻接表表示图进行深度优先遍历时,通常采用()来实现算法的。
A.栈B。
队列C.树D.图
答案:
A
3.已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是()
A.0243156B.0136542
C.0423165D.0361542
答案:
C
4.已知图的邻接矩阵同上题8,根据算法,则从顶点0出发按深度优先遍历的结点序列是()。
A.0243156B.0135642C.0423165D.0134256
答案:
D
5.已知图的邻接矩阵同上题8,根据算法思想,则从顶点0出发按广度优先遍历的结点序列是()
A.0243165B.0136425C.0423156D.0134256
答案:
B
6.已知图的邻接矩阵同上题8,根据算法,则从顶点0出发按广度优先遍历的结点序列是( )
A.0243165B.0135642C.0123465D.0123456
答案:
C
7.深度优先遍历类似于二叉树的()。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
答案:
A
8.广度优先遍历类似于二叉树的()。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
答案:
D
9.已知一个有向图如右图所示,则从顶点a出发,进行深度优先遍历,不可能得到序列为()。
A.a,d,b,e,f,cB.a,d,c,e,f,b
C.a,d,c,b,f,eD.a,d,e,f,c,b
答案:
A
10.深度优先遍历类似于二叉树的()。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
答案:
A
11.广度优先遍历类似于二叉树的()。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
答案:
D
D12.如下图所示,从顶点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
答案:
D
13.按广度优先进行遍历,则可能得到的一种顶点序列为()。
A.a,b,e,c,d,fB.a,b,e,c,f,d
C.a,e,b,c,f,dD.a,e,d,f,c,b
答案:
B
14.深度优先遍历类似于二叉树的()。
A.前序遍历B.中序遍历C.后序遍历D.层次遍历
答案:
A
15.广度优先遍历类似于二叉树的()。
A.前序遍历B.中序遍历C.后序遍历D.层次遍历
答案:
D
B41:
用邻接表表示图进行广度优先遍历时,通常采用()来实现算法的。
A.栈B.队列C.树D.图
答案:
B
16.用邻接表表示图进行深度优先遍历时,通常采用()来实现算法的。
A.栈B.队列C.树D.图
答案:
A
二、填空题
1.图的深度优先遍历序列_____唯一的。
答案:
不是
2.n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为。
答案:
3.n个顶点e条边的图采用邻接表存储,深度优先遍历算法的时间复杂度为____。
答案:
O(n+e)
4.n个顶点e条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为。
答案:
5.n个顶点e条边的图采用邻接表存储,广度优先遍历算法的时间复杂度为。
答案:
O(n+e)
6.n个顶点e条边的图若采用邻接矩阵存储,深度优先遍历算法的时间复杂度为。
答案:
O(n2)
7.图的遍历有:
深度优先搜和__等方法。
答案:
广度优先搜
8..n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为。
答案:
O(n2)
9..图的深度优先搜索类似于树的遍历。
答案:
前序
10.图的广度优先搜索类似于树的遍历。
答案:
层次
11.图的深度优先遍历序列________唯一的。
答案:
不是
三、简答题
1.完成下列深度优先遍历算法。
voidDFS(ALGraphwG,inti)
{EdgeNode*p;
printf("DFSvextex%cIn",G->adjlist[ii.vextex);
visited[i]=TRUE;
________
(1)________;
while(p)
{if(_______
(2)________)DFS(G,p->adjvex);
_________(3)____;
}
答案:
(1)p=G->adjlist[i].firstdege
(2)!
visited[p->adjvex]
(3)p=p->next
知识点四连通图的最小生成树
一、选择题
1.任何一个无向连通图的最小生成树()。
A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在
答案:
A
2.任何一个连通图的生成树()。
A.可能不存在B.只有一棵C.有一棵或多棵D.一定有多棵
答案:
C
3.生成树的构造方法只有()。
A.深度优先B.深度优先和广度优先C.无前驱的顶点优D.无后继的顶点优先
答案:
B
4.任何一个无向连通图的最小生成树()。
A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在
答案:
A
5.最小生成树的构造可使用()算法。
A.prim算法B.卡尔算法C.哈夫曼算法D.迪杰斯特拉算法
答案:
A
二、填空题
1.图的BFS生成树的树高比DFS生成树的树高____。
答案:
小或相等
2.用Prim算法求具有n个顶点e条边的图的最小生成树的时间复杂度为____。
答案:
O(
)
3.用Kruskal算法求具有n个顶点e条边的图的最小生成树的时间复杂度为____。
答案:
4.若要求一个稀疏图C的最小生成树,最好用____算法来求解。
答案:
Kruskal算法
5.若要求一个稠密图G的最小生成树,最好用____算法来求解。
答案:
Prim算法
6.一个图的生成树的顶点是图的_____顶点。
答案:
全部
知识点五两点之间最短路径问题
一、填空题
1.用迪杰斯特拉(Dijstra)算法求n个顶点e条边的图中的某一顶点到其余各顶点间的最短路径的时间复杂度为____。
答案:
2.用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度____的次序来得到最短路径的。
答案:
递增
二、简答题
1.求给定如下所示的有向图中顶点1到其余各顶点的最短路径及路径长度。
解答:
最短路径及路径长度为:
1
3:
8
1
3
2:
11
1
4:
12
1
3
5:
13
1
3
6:
14
1
3
5
7:
16
1
3
6
8:
16
1
3
6
8
10:
18
1
3
6
8
9:
22。
知识点六拓扑排序
一、填空题
1.拓扑排序算法是通过重复选择具有__个前趋顶点的过程来完成的。
答案:
零
2.拓扑排序输出的顶点数小于有向图的顶点数,则该图一定存在__。
答案:
环
3.对n个顶点e条边的图进行拓扑排序,算法的时间复杂度为____。
答案:
O(n+e)
二、简答题
1.图G=(V,E),V={0,1,2,3,4,5},E={<0,1>,<0,2>,<1,4>,<2,5>,<5,4>,<4,3>,<5,3>}。
写出图G中顶点的所有拓扑排序。
答案:
拓扑排序为:
012543
021543
025143。
知识点七关键路径
1.试对右图所示的AOE网络,解答下列问题。
(1)这个工程最早可能在什么时间结束。
(2)求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]。
(3)求每个活动的最早开始时间e()和最迟开始时间l()。
(4)确定哪些活动是关键活动。
画出由所有关键活动构成的图,指出哪些活动加速
可使整个工程提前完成。
答案:
按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。
然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l,根据l-e=0?
来确定关键活动,从而确定关键路径。
1
2
3
4
5
6
Ve
0
19
15
29
38
43
Vl
0
19
15
37
38
43
<1,2>
<1,3>
<3,2>
<2,4>
<2,5>
<3,5>
<4,6>
<5,6>
e
0
0
15
19
19
15
29
38
l
17
0
15
27
19
27
37
38
l-e
17
0
0
8
0
12
8
0
此工程最早完成时间为43。
关键路径为<1,3><3,2><2,5><5,6>
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第七 知识点 习题 总结
![提示](https://static.bingdoc.com/images/bang_tan.gif)