2022年第七章知识点习题总结.docx

《2022年第七章知识点习题总结.docx》由会员分享，可在线阅读，更多相关《2022年第七章知识点习题总结.docx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学问点一名师精编优秀资料图的定义和术语一、挑选题1在一个图中,全部顶点的度数之和等于图的边数的 倍；D 4 A12 B1 C2 答案： C 2在一个有向图中,全部顶点的入度之和等于全部顶点的出度之和的 倍；A12 B1 C2 D 4 答案： B 3. 有 8 个结点的无向图最多有 条边；C56 D 112 A14 B28 答案： B 4有 8 个结点的无向连通图最少有 条边；C7 D 8 A5 B6 答案： C 5有 8 个结点的有向完全图有 条边；C56 D 112 A14 B28 答案： C 6. 强连通重量是（）的极大强连通子图；C.无向

2、图D.有向图A. 树B.图答案： D 7. 在一个图中,全部顶点的度数之和等于图的边数的 倍；D.4 A. 1/2 B.1 C.2 答案： C 8. 在一个有向图中,全部顶点的入度之和等于全部顶点的出度之和的 倍；A. 1/2 B.1 C.2 D.4 答案： B 9. 有 8 个结点的无向图最多有 条边；C.56 D.112 A. 14 B.28 答案： B名师归纳总结 - - - - - - -第 1 页,共 14 页精选学习资料 - - - - - - - - - 10. 无向图顶点名师精编优秀资料v 的度是关联于该顶点（）的数目；A. 顶点B.边C.序号D.下标答案： B 11. 有 8

3、 个结点的无向连通图最少有 条边；C.7 D.8 A. 5 B.6 答案： C 12. 有 8 个结点的有向完全图有 条边；C.56 D.112 A. 14 B.28 答案： C 13. 一个具有 n 个顶点 e 条边的图中,全部顶点的度数之和等于 ；A. n B.e C.2n D.2e 答案： C 14. 如图 G 中（）都没有方向,就称G 为无向图；D.每个顶点A. 每条边B.部分边C.一条边答案： A 15. 对于一个具有n 个顶点的无向图的边数最多有（）；D.2n A. n B.nn-1 C.nn-1/2 答案： C 16. 对于一个具有n 个顶点的有向图的边数最多有（）；D.2n A

4、. n B.nn-1 C.nn-1/2 答案： B 17. 具有 4 个顶点的无向完全图有（）条边；D.20 A. 6 B.12 C.16 答案： A 18. 在以下表示方法中, （）是有向图边的表示方法；D. A. （1,2）B.（1,2 C. C.1,2）D. 答案： A 名师归纳总结 - - - - - - -第 2 页,共 14 页精选学习资料 - - - - - - - - - 名师精编 优秀资料二、填空题1.有 n 条边的无向图邻接矩阵中,1 的个数是_；答案： 2n 2.如图 G 中每条边都 方向,就 G 为无向图；答案：没有 3.n 个顶点的完全无向图有 条边；答案： n （n

5、-1 ）/24.如图 G 中每条边都_方向,就 G 为有向图；5.在具有 n 个顶点的图的生成树中,含有 条边；答案： n-16.有向图的边也称为 _ ；答案： 弧三、简答题1 .画出 1 个顶点、 2 个顶点、 3 个顶点、 4 个顶点和 5 个顶点的无向完全图；试证明在n个顶点的无向完全图中,边的条数为nn- 1/2；答案：1 个顶点的 2 个顶点的无向完全图 无向完全图3 个顶点的 4 个顶点的无向完全图 无向完全图 5 个顶点的无向完全图【证明】在有 n 个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有 n- 1 条边与其他 n- 1 个顶点相连, 总计

6、n 个顶点有 nn- 1条边；但在无向图中,顶点 i 到顶点 j 与顶点 j 到顶点 i 是同一条边,所以总共有 nn- 1/2 条边；学问点二 图的储备结构一、挑选题名师归纳总结 1. 对于一个具有n 个顶点的无向图, 如采纳邻接矩阵表示,就该矩阵的大小是 （第 3 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - A. n B. n-1 2 名师精编优秀资料D. n2 C. n-1 答案： D 2. 对于一个具有 n 个顶点和 e 条边的无向图,如采纳邻接表表示,就表头向量的大 为 ; A. n B. n-1 2 C. n-1 D. n2 答案：

7、A 3. 有 n 个顶点的无向图的邻接矩阵是用（）数组储备；D.n 行任意列A. 一维B.n 行 n 列C.任意行 n 列答案： B 4.n 个顶点的无向图采纳邻接矩阵储备方法,该邻接矩阵是一个（）；A. 一般矩阵B.对称矩阵C.对角矩阵D.稀疏矩阵答案： B 5. 有 n 个顶点的有向图的邻接矩阵是用（）数组储备；D.n 行任意列A. 一维B.n 行 n 列C.任意行 n 列答案： B 6. 有 n 个条边的无向图的邻接矩阵（表）储备法中,链表中结点的个数是（D.n*n ）个；A. n/2 B.n C.2n 答案： C 7. 有 n 个条边的有向图的邻接矩阵（表）储备法中,链表中结点的个数是

8、（D.n*n ）个；A. n/2 B.n C.2n 答案： B 8. 下面关于图的储备结构的表达中正确选项（）；A. 用邻接矩阵储备图,占用空间大小只与图中顶点数有关,而与边数无关B. 用邻接矩阵储备图,占用空间大小只与图中边数有关,而与顶点数无关 C. 用邻接表储备图,占用空间大小只与图中顶点数有关,而与边数无关 D. 用邻接表储备图,占用空间大小只与图中边数有关,而与顶点数无关 答案： A名师归纳总结 9. 在图的表示法中,表示形式唯独的是（）；第 4 页,共 14 页A. 邻接矩阵表示法B.邻接表表示法C.逆邻接表表示法D.邻接表和逆邻接表表示法- - - - - - -精选学习资料 -

9、 - - - - - - - - 名师精编 优秀资料答案： A 二、填空题1. 图有等储备结构；i 行的全部元素之和等于顶点答案：邻接矩阵,邻接表2有向图 G 用邻接表矩阵储备,其第i 的；答案：出度4n 个顶点 e 条边的图如采纳邻接矩阵储备,就空间复杂度为 _；答案：5n 个顶点 e 条边的图如采纳邻接表储备,就空间复杂度为 _；答案： On+e 6. 设有一稀疏图C,就 C采纳 _ 储备较省空间；答案： 邻接矩阵7. 设有一稠密图G,就 G 采纳储备较省空间；答案：邻接表8. 图的逆邻接表储备结构只适用于 图；答案：有向9. 已知一个图的邻接矩阵表示,删除全部从第i 个顶点动身的边的方法

10、是 答案：把第 i 行全部置零10. 图有：_ _ 和邻接表等储备结构；答案： 邻接矩阵11. n 个顶点 e 条边的图如采纳邻接矩阵储备,就空间复杂度为：；答案： O（n2）12. n 个顶点 e 条边的图如采纳邻接表阵储备,就空间复杂度为：；O（n+e）答案：13 .图的邻接矩阵表示法是表示_之间相邻关系的矩阵；名师归纳总结 14. 对 n 个顶点, e 条弧的有向图,其邻接表表示中,需要个结点；第 5 页,共 14 页- - - - - - -精选学习资料 - - - - - - - - - 名师精编 优秀资料答案： n+e 15. 对 n 个顶点, e 条边的无向图,其邻接表表示中,需

11、要 个结点；答案： n+2e16. 有向图 G 用邻接矩阵储备,其第i 行的全部元素之和等于顶点i 的 _；答案：出度 17. 设有一稀疏图 G,就 G 采纳 _储备比较节约空间；答案： 邻接表 18. 图的逆邻接表储备结构只适用于 _图；答案：有向19. 设有一稠密图G,就 G 采纳_储备比较节约空间；答案： 邻接矩阵 20. 一个图的 表示法是唯独的；答案： 邻接矩阵 21. .有向图的邻接表表示适于求顶点的；答案： 出度22. .有向图的邻接矩阵表示中,第i 列上非 0 元素的个数为顶点Vi 的；答案：入度 三、简答题1.以下函数是在有向图的邻接表中删除一条边的算法,请补充算法；Void

12、 deledge ALGraph * G, iht i, int j EdgeNode * p, * q; p = G - adjlist Iii . firstedge; if_1_ G-adjlisti.firstedge=p-next;freep; else while p -next -adjvex. = j & p -next _2_; if_3_q=p -next;_4_;freeq; 答案：（ 1）p-adjvex=j （ 2）p=p-next 名师归纳总结 - - - - - - -第 6 页,共 14 页精选学习资料 - - - - - - - - - 名师精编 优秀资料（

13、3）p-next.=null （ 4）p-next=q-next 2. 用邻接矩阵表示图时, 矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？答案：用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,中非零元素的个数与边的条数有关；学问点三 图的遍历一、挑选题与边的条数无关；矩阵1用邻接表表示图进行广度优先遍历时,通常采纳 来实现算法的；A. 栈B队列C树D图答案： B 2用邻接表表示图进行深度优先遍历时,通常采纳 来实现算法的；A栈B；队列C树D图答案： A 3已知图的邻接矩阵,依据算法思想, 就从顶点 0 动身按深度优先遍历的结点序列是 0 1 1 1 1 0 1 1 0 0 1 0

14、0 1 A0 2 4 3 1 5 6 B 0 1 3 6 5 4 2 1 0 0 0 1 0 0 C0 4 2 3 1 6 5 D0 3 6 1 5 4 2 1 1 0 0 1 1 0 1 0 1 1 0 1 0 答案： C 4已知图的邻接矩阵同上题8,依据算法,就从顶点0 动身按深度优先遍历的结点序列是 ；B0 1 3 5 6 4 2 C0 4 2 3 1 6 5 D0 1 3 4 2 5 6 A0 2 4 3 1 5 6 答案： D 名师归纳总结 5已知图的邻接矩阵同上题8,依据算法思想,就从顶点0 动身按广度优先遍历的结点序第 7 页,共 14 页列是（）- - - - - - -精选学

15、习资料 - - - - - - - - - A. 0 2 4 3 1 6 5 名师精编优秀资料D. 0 1 3 4 2 5 6 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 答案： B 6已知图的邻接矩阵同上题8,依据算法,就从顶点0 动身按广度优先遍历的结点序列是（）B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6 A. 0 2 4 3 1 6 5 答案： C 7深度优先遍历类似于二叉树的 ；C后序遍历D层次遍历A先序遍历B中序遍历答案： A 8广度优先遍历类似于二叉树的 ；C后序遍历D层次遍历A先序遍历B中序遍历答案

16、： D 9. 已知一个有向图如右图所示,就从顶点（）；a 动身,进行深度优先遍历,不行能得到序列为A. a,d,b,e,f,c B.a,d,c,e,f,b C.a,d,c, b,f,e D.a,d,e,f, c,b 答案： A 10.深度优先遍历类似于二叉树的 ；C.后序遍历D.层次遍历A. 先序遍历B.中序遍历答案： A 11.广度优先遍历类似于二叉树的 ；C.后序遍历D.层次遍历A. 先序遍历B.中序遍历答案： D D12.如下图所示, 从顶点 a 动身,按深度优先进行遍历, 就可能得到的一种顶点序列为（）；A. a,b,e,c, d,f B.a, c,f,e,b,d C.a,e,b,c,

17、f,d D.a,e,d,f,c, b 答案： D 名师归纳总结 13.按广度优先进行遍历,就可能得到的一种顶点序列为（）；第 8 页,共 14 页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 - - - - - - -精选学习资料 - - - - - - - - - 名师精编 优秀资料答案： B 14.深度优先遍历类似于二叉树的 ；C.后序遍历D.层次遍历A. 前序遍历B.中序遍历答案： A 15.广度优先遍历类似于二叉树的 ；C.后序遍历D.层次遍历A. 前序遍历B.中序遍历答案： D B 41:用邻接表表示图进行广度优

18、先遍历时,通常采纳 来实现算法的；A. 栈B.队列C.树D.图答案： B 16.用邻接表表示图进行深度优先遍历时,通常采纳 来实现算法的；A. 栈B.队列C.树D.图答案： A 二、填空题1. 图的深度优先遍历序列_ _唯独的；答案：不是2. n 个顶点 e 条边的图采纳邻接矩阵储备,深度优先遍历算法的时间复杂度为；答案：3. n 个顶点 e 条边的图采纳邻接表储备,深度优先遍历算法的时间复杂度为 _；答案： On+e 4. n 个顶点 e 条边的图采纳邻接矩阵储备,广度优先遍历算法的时间复杂度为；答案：5. n 个顶点 e 条边的图采纳邻接表储备,广度优先遍历算法的时间复杂度为；答案： On

19、+e 6. n 个顶点 e 条边的图如采纳邻接矩阵储备,深度优先遍历算法的时间复杂度为；答案： O（n2）名师归纳总结 - - - - - - -第 9 页,共 14 页精选学习资料 - - - - - - - - - 名师精编 优秀资料7. 图的遍历有：深度优先搜和 _等方法；答案： 广度优先搜 8. .n 个顶点 e 条边的图采纳邻接矩阵储备,深度优先遍历算法的时间复杂度为；答案： O（n2）9. .图的深度优先搜寻类似于树的 遍历；答案： 前序 10. 图的广度优先搜寻类似于树的 遍历；答案： 层次 11. 图的深度优先遍历序列 _唯独的；答案：不是 三、简答题1完成以下深度优先遍历算法

20、；void DFSALGraph w G, int i EdgeNode *p; print f DFS vextex % c In, G - adj list ii. vextex; visited i = TRUE; _1_; while p if_2_ DFSG,p - adjvex; _3_; 答案：（1）p=G-adjlisti.firstdege （2）.visitedp-adjvex （3）p=p-next 学问点四 连通图的最小生成树一、挑选题1任何一个无向连通图的最小生成树 ；C肯定有多棵D可能不存在A只有一棵B一棵或多棵答案： A 名师归纳总结 - - - - - - -第

21、 10 页,共 14 页精选学习资料 - - - - - - - - - 2. 任何一个连通图的生成树 ；名师精编优秀资料A. 可能不存在B.只有一棵C.有一棵或多棵D.肯定有多棵答案： C 3. 生成树的构造方法只有（）；C.无前驱的顶点优D.无后继的顶点优先A. 深度优先B.深度优先和广度优先答案： B 4. 任何一个无向连通图的最小生成树 ；C.肯定有多棵D.可能不存在A. 只有一棵B.一棵或多棵答案： A 5. 最小生成树的构造可使用（）算法；D.迪杰斯特拉算法A. prim 算法B.卡尔算法C.哈夫曼算法答案： A 二、填空题1. 图的 BFS生成树的树高比 DFS生成树的树高 _；

22、答案：小或相等2. 用 Prim 算法求具有n 个顶点 e 条边的图的最小生成树的时间复杂度为_； 3. 用 Kruskal 算法求具有n 个顶点 e 条边的图的最小生成树的时间复杂度为答案： O _ _；答案：4. 如要求一个稀疏图C的最小生成树,最好用_算法来求解；答案： Kruskal 算法5. 如要求一个稠密图G 的最小生成树,最好用_算法来求解；答案： Prim 算法6. 一个图的生成树的顶点是图的 _ _顶点；答案：全部名师归纳总结 - - - - - - -第 11 页,共 14 页2 精选学习资料 - - - - - - - - - 7 名师精编优秀资料5 1 3 8 10 6

23、 4 两点之间最短路径问题9 学问点五一、填空题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；学问点六 拓扑排序名

24、师归纳总结 - - - - - - -第 12 页,共 14 页精选学习资料 - - - - - - - - - 名师精编 优秀资料一、填空题1. 拓扑排序算法是通过重复挑选具有_个前趋顶点的过程来完成的；2. 拓扑排序输出的顶点数小于有向图的顶点数,就该图肯定存在 _；答案：环3. 对 n 个顶点 e 条边的图进行拓扑排序,算法的时间复杂度为 _；答案： On+e 二、简答题1. 图 G=V,E,V=0,1,2, 3,4,5,E=,；写出图 G 中顶点的全部拓扑排序；答案：拓扑排序为：0 1 2 5 4 3 0 2 1 5 4 3 0 2 5 1 4 3；学问点七 关键路径1. 试对右图所示

25、的AOE网络,解答以下问题；1 这个工程最早可能在什么时间终止；2 求每个大事的最早开头时间Vei和最迟开头时间Vli；3 求每个活动的最早开头时间e 和最迟开头时间l ；4 确定哪些活动是关键活动；画出由全部关键活动构成的图,指出哪些活动加速可使整个工程提前完成；答案：按拓扑有序的次序运算各个顶点的最早可能开头时间 Ve 和最迟答应开头时间 Vl；然后再运算各个活动的最早可能开头时间 e 和最迟答应开头时间 l,依据 l - e = 0. 来确定关键活动,从而确定关键路径；1 2 3 4 5 6 0 19 15 29 38 43 Ve 0 19 15 37 38 43 Vl 名师归纳总结 - - - - - - -第 13 页,共 14 页精选学习资料 - - - - - - - - - 名师精编优秀资料 1, 3 3, 2 2, 4 2, 5 3, 5 4, 6 5, 6 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；关键路径为 名师归纳总结 - - - - - - -第 14 页,共 14 页