《2022年第七章知识点习题总结 .pdf》由会员分享，可在线阅读，更多相关《2022年第七章知识点习题总结 .pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、名师精编优秀资料知识点一图的定义和术语一、选择题1在一个图中，所有顶点的度数之和等于图的边数的( )倍。A12 B1 C2 D 4 答案： C 2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。A12 B1 C2 D 4 答案： B 3. 有 8 个结点的无向图最多有( )条边。A14 B28 C56 D 112 答案： B 4有 8 个结点的无向连通图最少有( )条边。A5 B6 C7 D 8 答案： C 5有 8 个结点的有向完全图有( )条边。A14 B28 C56 D 112 答案： C 6. 强连通分量是（）的极大强连通子图。A. 树B.图C.无向图D.有向图答案
2、： D 7. 在一个图中，所有顶点的度数之和等于图的边数的( )倍。A. 1/2 B.1 C.2 D.4 答案： C 8. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。A. 1/2 B.1 C.2 D.4 答案： B 9. 有 8 个结点的无向图最多有( )条边。A. 14 B.28 C.56 D.112 答案： B精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 14 页名师精编优秀资料10. 无向图顶点v 的度是关联于该顶点（）的数目。A. 顶点B.边C.序号D.下标答案： B 11. 有 8 个结点的无向连通
3、图最少有( )条边。A. 5 B.6 C.7 D.8 答案： C 12. 有 8 个结点的有向完全图有( )条边。A. 14 B.28 C.56 D.112 答案： C 13. 一个具有n 个顶点 e 条边的图中，所有顶点的度数之和等于( )。A. n B.e C.2n D.2e 答案： C 14. 若图 G 中（）都没有方向，则称G 为无向图。A. 每条边B.部分边C.一条边D.每个顶点答案： A 15. 对于一个具有n 个顶点的无向图的边数最多有（） 。A. n B.n(n-1) C.n(n-1)/2 D.2n 答案： C 16. 对于一个具有n 个顶点的有向图的边数最多有（） 。A. n
4、 B.n(n-1) C.n(n-1)/2 D.2n 答案： B 17. 具有 4 个顶点的无向完全图有（）条边。A. 6 B.12 C.16 D.20 答案： A 18. 在下列表示方法中， （）是有向图边的表示方法。A. （1，2）B.（1，2 C.1，2）D. 答案： D 19. 在下列表示方法中， （）是有无向图边的表示方法。A. （1，2）B.（1，2 C.1，2）D. 答案： A 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 14 页名师精编优秀资料二、填空题1.有 n 条边的无向图邻接矩阵中，1 的个数是_。答案：2n2.
5、若图 G 中每条边都方向，则 G 为无向图。答案：没有3.n 个顶点的完全无向图有条边。答案： n （n-1）/24.若图 G 中每条边都_方向，则G 为有向图。答案：有5.在具有 n 个顶点的图的生成树中，含有条边。答案：n-16.有向图的边也称为_ 。答案：弧三、简答题1 .画出 1 个顶点、 2 个顶点、 3 个顶点、 4 个顶点和5 个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n- 1)/2。答案：【证明】在有 n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n- 1 条边与其他n- 1 个顶点相连， 总计 n 个顶点有n(n-
6、1)条边。 但在无向图中，顶点 i 到顶点 j 与顶点 j 到顶点 i 是同一条边，所以总共有n(n- 1)/2条边。知识点二图的存储结构一、选择题1. 对于一个具有n 个顶点的无向图， 若采用邻接矩阵表示，则该矩阵的大小是（1 个顶点的无向完全图2 个顶点的无向完全图3 个顶点的无向完全图4 个顶点的无向完全图5 个顶点的无向完全图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 14 页名师精编优秀资料A. n B. (n-1) 2 C. n-1 D. n2 答案： D 2. 对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示
7、，则表头向量的大为( ); A. n B. (n-1) 2 C. n-1 D. 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/2 B.n C.2n D
8、.n*n 答案： C 7. 有 n 个条边的有向图的邻接矩阵（表）存储法中，链表中结点的个数是（）个。A. n/2 B.n C.2n D.n*n 答案： B 8. 下面关于图的存储结构的叙述中正确的是（） 。A. 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B. 用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C. 用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关D. 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关答案： A9. 在图的表示法中，表示形式唯一的是（） 。A. 邻接矩阵表示法B.邻接表表示法C.逆邻接表表示法D.邻接表和逆
9、邻接表表示法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 14 页名师精编优秀资料答案： A 二、填空题1. 图有等存储结构。答案：邻接矩阵,邻接表2有向图 G 用邻接表矩阵存储，其第i 行的所有元素之和等于顶点i 的。答案：出度4n 个顶点 e 条边的图若采用邻接矩阵存储，则空间复杂度为_。答案：5n 个顶点 e 条边的图若采用邻接表存储，则空间复杂度为_。答案： O(n+e) 6. 设有一稀疏图C，则 C采用 _ 存储较省空间。答案：邻接矩阵7. 设有一稠密图G，则 G 采用存储较省空间。答案：邻接表8. 图的逆邻接表存储结构只适
10、用于图。答案：有向9. 已知一个图的邻接矩阵表示，删除所有从第i 个顶点出发的边的方法是答案：把第i 行全部置零10. 图有：_ _ 和邻接表等存储结构。答案：邻接矩阵11. n 个顶点 e 条边的图若采用邻接矩阵存储，则空间复杂度为：。答案：O （n2）12. n 个顶点 e 条边的图若采用邻接表阵存储，则空间复杂度为：。答案：O （n+e）13 .图的邻接矩阵表示法是表示_之间相邻关系的矩阵。答案：顶点14. 对 n 个顶点， e 条弧的有向图，其邻接表表示中，需要个结点。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 14 页名师
11、精编优秀资料答案：n+e15. 对 n 个顶点， e 条边的无向图，其邻接表表示中，需要个结点。答案：n+2e16. 有向图 G 用邻接矩阵存储，其第i 行的所有元素之和等于顶点i 的 _。答案：出度17. 设有一稀疏图G，则 G 采用_存储比较节省空间。答案：邻接表18. 图的逆邻接表存储结构只适用于_图。答案：有向19. 设有一稠密图G，则 G 采用_存储比较节省空间。答案：邻接矩阵20. 一个图的表示法是唯一的。答案：邻接矩阵21. .有向图的邻接表表示适于求顶点的。答案：出度22. .有向图的邻接矩阵表示中，第i 列上非 0 元素的个数为顶点Vi 的。答案：入度三、简答题1.下列函数是
12、在有向图的邻接表中删除一条边的算法，请补充算法。Void deledge (ALGraph * G, iht i, int j ) EdgeNode * p, * q; p = G - adjlist Iii . firstedge; if(_(1)_) G-adjlisti.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 精选学习资料 - - - - -
13、 - - - - 名师归纳总结 - - - - - - -第 6 页，共 14 页名师精编优秀资料（ 3）p-next!=null （ 4）p-next=q-next 2. 用邻接矩阵表示图时， 矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？答案：用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。知识点三图的遍历一、选择题1用邻接表表示图进行广度优先遍历时，通常采用( )来实现算法的。A. 栈B队列C树D图答案： B 2用邻接表表示图进行深度优先遍历时，通常采用( )来实现算法的。A栈B。队列C树D图答案： A 3已知图的邻接矩阵，根
14、据算法思想， 则从顶点 0 出发按深度优先遍历的结点序列是( ) A0 2 4 3 1 5 6 B 0 1 3 6 5 4 2 C0 4 2 3 1 6 5 D0 3 6 1 5 4 2 答案： C 4已知图的邻接矩阵同上题8，根据算法，则从顶点0 出发按深度优先遍历的结点序列是( )。A0 2 4 3 1 5 6 B0 1 3 5 6 4 2 C0 4 2 3 1 6 5 D0 1 3 4 2 5 6 答案： D 5已知图的邻接矩阵同上题8，根据算法思想，则从顶点0 出发按广度优先遍历的结点序列是（）0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1
15、0 0 1 1 0 1 0 1 1 0 1 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 14 页名师精编优秀资料A. 0 2 4 3 1 6 5 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 答案： B 6已知图的邻接矩阵同上题8，根据算法，则从顶点0 出发按广度优先遍历的结点序列是（）A. 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6 答案： C 7深度优先遍历类似于二叉树的( )。A先序
16、遍历B中序遍历C后序遍历D层次遍历答案： A 8广度优先遍历类似于二叉树的( )。A先序遍历B中序遍历C后序遍历D层次遍历答案： 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.深度优先遍历类似于二叉树的( )。A. 先序遍历B.中序遍历C.后序遍历D.层次遍历答案： A 11.广度优先遍历类似于二叉树的( )。A. 先序遍历B.中序遍历C.后序遍历D.层次遍历答案： D D12.如下图所示， 从顶点 a出发，按
17、深度优先进行遍历，则可能得到的一种顶点序列为（） 。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 答案： D 13.按广度优先进行遍历，则可能得到的一种顶点序列为（） 。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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 14 页名师精编优秀资料答案： B 14.深度优先遍历类似于二叉树的( )。A. 前序遍历B.中序遍历C. 后序遍历D.层次遍历答案
18、： A 15.广度优先遍历类似于二叉树的( )。A. 前序遍历B.中序遍历C.后序遍历D.层次遍历答案： D B 41:用邻接表表示图进行广度优先遍历时，通常采用( )来实现算法的。A. 栈B.队列C.树D.图答案： B 16.用邻接表表示图进行深度优先遍历时，通常采用( )来实现算法的。A. 栈B.队列C.树D.图答案： A 二、填空题1. 图的深度优先遍历序列_ _唯一的。答案：不是2. n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为。答案：3. n 个顶点 e 条边的图采用邻接表存储，深度优先遍历算法的时间复杂度为_。答案： O(n+e) 4. n 个顶点 e
19、条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为。答案：5. n 个顶点 e 条边的图采用邻接表存储，广度优先遍历算法的时间复杂度为。答案： O(n+e) 6. n个顶点 e 条边的图若采用邻接矩阵存储，深度优先遍历算法的时间复杂度为。答案：O （n2）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 14 页名师精编优秀资料7. 图的遍历有：深度优先搜和_等方法。答案：广度优先搜8. .n 个顶点 e 条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为。答案：O （n2）9. .图的深度优先搜索类似于树的遍历。答案：前序1
20、0. 图的广度优先搜索类似于树的遍历。答案：层次11. 图的深度优先遍历序列_唯一的。答案：不是三、简答题1完成下列深度优先遍历算法。void DFS(ALGraph 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)_) DFS(G,p - adjvex); _(3)_; 答案： （1）p=G-adjlisti.firstdege （2）!visitedp-adjvex （3）p=p-next 知识点四
21、连通图的最小生成树一、选择题1任何一个无向连通图的最小生成树( )。A只有一棵B一棵或多棵C一定有多棵D可能不存在答案： A 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 14 页名师精编优秀资料2. 任何一个连通图的生成树( )。A. 可能不存在B.只有一棵C.有一棵或多棵D.一定有多棵答案： C 3. 生成树的构造方法只有（） 。A. 深度优先B.深度优先和广度优先C.无前驱的顶点优D.无后继的顶点优先答案： B 4. 任何一个无向连通图的最小生成树( )。A. 只有一棵B.一棵或多棵C. 一定有多棵D.可能不存在答案： A 5
22、. 最小生成树的构造可使用（）算法。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. 一个图的生成树的顶点是图的_ _顶
23、点。答案：全部精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 14 页名师精编优秀资料知识点五两点之间最短路径问题一、填空题1. 用迪杰斯特拉 (Dijstra)算法求 n 个顶点 e 条边的图中的某一顶点到其余各顶点间的最短路径的时间复杂度为_ _。答案：2. 用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度_的次序来得到最短路径的。答案：递增二、简答题1求给定如下所示的有向图中顶点1 到其余各顶点的最短路径及路径长度。解答：最短路径及路径长度为：13：8 132：11 14：12 135：13 136：14
24、 1357：16 1368：16 136810：18 13689：22。知识点六拓扑排序9 2 7 5 3 8 1 10 6 4 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 14 页名师精编优秀资料一、填空题1. 拓扑排序算法是通过重复选择具有_个前趋顶点的过程来完成的。答案：零2. 拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在_。答案：环3. 对 n 个顶点 e 条边的图进行拓扑排序，算法的时间复杂度为_。答案： O(n+e ) 二、简答题1. 图 G=(V，E)，V=0，1，2， 3，4，5，E=，。写出图G 中顶点
25、的所有拓扑排序。答案：拓扑排序为：0 1 2 5 4 3 0 2 1 5 4 3 0 2 5 1 4 3。知识点七关键路径1. 试对右图所示的AOE网络，解答下列问题。(1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间Vei和最迟开始时间Vli。(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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 14 页名师精编优秀资料 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。关键路径为 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 14 页