Microsoft Word - 专升本练习5：图.doc

Size: px

Start display at page:

Download "Microsoft Word - 专升本练习5：图.doc"

中抵立阙
7 years ago
Views:

1 第五章图一选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e 3. 对一个具有 n 个顶点的图, 采用邻接矩阵表示, 则该矩阵的大小为 ( ) A. n B. n-1 C. n+1 D. n 2 4. n 个顶点的强连通图至少有 ( ) 条边 A. n B. n-1 C. n+1 D. n(n-1) 5. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 ( ) A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层遍历 6. 采用邻接表存储的图, 其广度优先遍历类似于二叉树的 ( ) A. 按层次遍历 B. 中序遍历 C. 后序遍历 D. 先序遍历 7. 一个图中包含有 k 个连通分量, 若按深度优先 (DFS) 搜索方法访问所有结点, 则必须调用 ( ) 次深度优先遍历算法 A. k B. 1 C. k-1 D. k+1 8. 设有无向图 G=(V, E) 和 G =(V, E ), 如是 G 是 G 的生成树, 则下面不正确的说法是 ( ) A. G 为 G 的连通分量 B. G 是 G 的无环子图 C. G 为 G 的子图 D. G 为 G 的极小连通子图且 V =V 9. 以下说法正确的是 ( ) A. 连通分量是无向图中的极小连通子图 B. 强连通分量是有向图中的极大强连通子图 C. 在一个有向图的拓扑序列中若顶点 a 在顶点 b 之前, 则图中必有一条弧 <a,b> D. 对有向图 G, 如果以任何一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点, 则该图一定是完全图 10. 下列说法中不正确的是 ( ) A. 无向图中的极大连通子图称为连通分量 B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C. 图的深度优先搜索中一般要采用栈为暂存刚访问过的顶点 D. 有向图的遍历不可采用广度优先搜索方法 11. 具有 n 个顶点的有向图最多有 ( ) 条边 A. n B. n(n-1) C. n(n+1) D. n 用相邻矩阵 A 表示图, 判定任意两个顶点 V i 和 V j 之间是否有长度为 m 的路径相连, 则只要检查 ( ) 的第 i 行和第 j 列的元素是否为零即可 A. ma B. A C. A m D. Am 下列说法中, 正确的有 ( ) A. 最小生成树也是哈夫曼树 B. 最小生成树惟一 C. 普里姆 (Prim) 最小生成树算法时间复杂度为 O(n 2 ) D. 克鲁斯卡尔 (Krukal) 最小生成树算法比普里姆算法更适合于边稠密的网 14. 在一个具有 n 个顶点的有向图中, 若所有顶点的出度之和为 s, 则所有顶点的入度之和为 ( ) - 1 -

2 A. s B. s-1 C. s+1 D. n 15. 在一个图中, 所有顶点的度数之和等于所有边数的 ( ) 倍 A. 1/2 B. 1 C. 2 D 在一个有向图中, 所有顶点的入度之和等于所有顶点的出度之和的 ( ) 倍 A. 1/2 B. 1 C. 2 D 一个有 n 个顶点的无向图最多有 ( ) 条边 A. n B. n(n-1) C. n(n-1)/2 D. 2n 18. 具有 4 个顶点的无向完全图有 ( ) 条边 A. 6 B. 12 C. 16 D 具有 6 个顶点的无向图至少应有 ( ) 条边才能确保是一个连通图 A. 5 B. 6 C. 7 D 在一个具有 n 个顶点的无向图中, 要连通全部顶点至少需要 ( ) 条边 A. n B. n+1 C. n-1 D. n/2 21. 对于一个具有 n 个顶点的无向图, 若采用邻接矩阵表示, 则该矩阵的大小是 ( ) A. n B. (n-1)*(n-1) C. n-1 D. n 对于一个具有 n 个顶点和 e 条边的无向图, 若采用邻接表表示, 则表头向量的大小为 ( 1 ); 所有邻接表中的结点总数是 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e 23. 对某个无向图的邻接矩阵来说,( ) A. 第 i 行上的非零元素个数和第 i 列的非零元素个数一定相等 B. 矩阵中的非零元素个数等于图中的边数 C. 第 i 行上, 第 i 列上非零元素总数等于顶点 vi 的度数 D. 矩阵中非全零行的行数等于图中的顶点数 24. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 ( ) A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 25. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 ( ) A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 26. 任何一个无向连通图的最小生成树 ( ) A. 有一棵或多棵 B. 只有一棵 C. 一定有多棵 D. 可能不存在 27. 以下说法中不正确的是 ( ) A. 无向图中的极大连通子图称为连通分量 B. 连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C. 图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D. 有向图的遍历不可采用广度优先搜索方法 28. 下面不正确的说法是 ( ) (1) 在 AOE 网中, 减小任一关键活动上的权值后, 整个工期也就相应减小 (2)AOE 网工程工期为关键活动上的权之和 (3) 在关键路径上的活动都是关键活动, 而关键活动也必须在关键路径上 A. (1) B. (2) C. (3) D. (1) ( 2) 29. 下面不正确的说法是 ( ) A. 关键活动不按期完成就会影响整个工程的完成时间 B. 任何一个关键活动提前完成, 将使整个工程提前完成 C. 所有关键活动都提前完成, 则整个工程提前完成 D. 某些关键活动若提前完成, 将使整个工程提前完成 - 2 -

3 二填空题 1. 假定一个无向图有 n 个顶点 e 条边, 则在邻接矩阵表示中, 求任意顶点度数的时间复杂度为在用邻接表表示中, 访问图中一个顶点的所有邻接点的时间复杂度为 2. 对于含有 n 个顶点 e 条边的无向连通图, 利用普里姆算法生成最小生成树的时间复杂度为, 利用克鲁斯卡算法生成最小生成树的时间复杂度为, 在具有 n 个顶点的图的生成树中, 含有条边 3. 对于邻接矩阵表示的图进行深度或广度优先搜索遍历时的时间复杂度为, 对于邻接表表示的图进行深度和广度优先遍历时的时间复杂度为, 图的深度优先搜索遍历的空间复杂度均为 4. 在一图 G 的邻接表表示中, 每个顶点的邻接表中所含的结点数, 对于有向图而言等于该顶点的 ; 而对于无向图而言等于该顶点的 5. 设邻接表法表示的图 G 有 n 个顶点和 e 条边, 进行深度优先搜索遍历的时间复杂度至多为, 进行广度优先搜索遍因的时间复杂度至多为 ; 当 G 是非孤立顶点的连通图时有 2e n, 故可以推得深度优先搜索遍历的时间复杂度为 ; 广度优先搜索遍历的时间复杂度 6. 一个无向图有 n 个顶点和 e 条边, 则所有顶点的度的和为 7. 若无向图 G 的边数大于或等于时,G 至少有一条回路 8. 如果含 n 个顶点的图形成一个环, 则它有棵生成树 9. G 是一个非连通无向图, 共有 28 条边, 则该图至少个顶点 10. 具有 10 个顶点的无向图, 边的总数最多为 11. 在有 n 个顶点的有向图中, 每个顶点的度最大可达 12. Prim( 普里姆 ) 算法适用于求的网的最小生成树 ;kruskal( 克鲁斯卡尔 ) 算法适用于求的网的最小生成树 13. 顶点活动网 (AOV 网 ) 是有向图 14. 有向图的极大强连通子图称为 15. 在一个具有 n 个顶点的无向完全图中, 包含有条边 ; 在一个具有 n 个顶点的有向完全图中, 包含有条边 16. 根据图的存储结构进行某种次序的遍历, 得到的顶点序列是的 17. 对含有 n 个顶点 e 条边的无向连通图, 利用普里姆算法生成最小生成树的时间复杂度为, 利用克鲁斯卡尔算法生成最小生成树的时间复杂度为 18. 连通分量是无向图中的连通子图 - 3 -

4 19. 源点到汇点长度最长的路径称关键路径, 该路径上的活动称 20. 一个有向图, 若一顶点的入度为 k 1, 出度为 k 2, 则对应逆邻接表中该顶点的单链表中的结点数为个, 对应邻接表中该单链表中结点数为 21. 连通图的是一极小连通子图 22. 在 n 个顶点的无向图中, 若边数 >n-1, 则该图必是连通图此断言是的 23. 在无向图 G 的邻接矩阵 A 中, 若 A[i][j] 等于 1, 则 A[j][i] 等于 24. 一个图的表示法是惟一的, 而表示法是不惟一的 25. 在有 n 个顶点的有向图中, 每个顶点的度最大可达 26. 已知一个图的邻接矩阵表示, 计算第 i 个结点的入度的方法是 27. 已知一个图的邻接矩阵表示, 删除所有从第 i 个结点出发的边的方法是 28. 图的深度优先搜索序列和广度优先搜索序列不是惟一的此断言是的 29. 如果含 n 个顶点的图形成一个环, 则它有棵生成树 30. 对 n 个顶点的连通图来说, 它的生成树一定有条边 31. 用邻接矩阵 A 表示图, 判定任意两个结点 v i 和 v j 之间是否有长度为 m 的路径相连, 则只需要检查 A m 的第 i 行第 j 列的元素是否为 0 即可此断言是的三判断题 1. 有 n 个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半 ( ) 2. 若连通图上各权值均不相同, 则该图的最小生成树是惟一的 ( ) 3. 无向图的邻接矩阵一定是对称矩阵, 且有向图的邻接矩阵一定是非对称矩阵 ( ) 4. 用邻接矩阵存储一个图时, 所占的存储空间大小只与图中结点的个数有关, 而与图的边数无关 ( ) 5. 邻接表只能用于存储有向图, 而邻接矩阵则可存储有向图和无向图 ( ) 6. 无向图的邻接矩阵是对称的, 因此可只存储邻接矩阵的下 ( 或上 ) 三角阵 ( ) 7. 连通分量是无向图中的极小连通子图 ( ) 8. 强连通分量有向图中的极大强连通子图 ( ) 9. 如果连通网中存在相同权值的边, 则最小生成树不惟一 ( ) 10. 用邻接矩阵表示图时, 矩阵元素的个数与边的条数有关 ( ) 11. 用 n 个结点的无向图中, 若边数 >n-1, 则该图必是连通图 ( ) 12. 已知一个有向图的邻接矩阵 A n n, 其顶点 v i 的入度为 [ j, i] ( ) 13. 已知一个有向图的邻接矩阵 A n n, 其顶点 v i 的出度为 [ j, i] ( ) 14. 用邻接矩阵 A 表示图, 判定任意两个结点 v i 和 v j 之间是否有长度为 m 的路径相连, 则只要检查 A m 的第 i 行和第 j 列的元素是否为 0 即可 ( ) 15. 一个图的广度优先搜索树是惟一的 ( ) n j= 1 n j= 1-4 -

5 16. 图的深度优先搜索序列和广度优先搜索序列不是惟一的 ( ) - 5 -

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 七 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 7 章图 7.1 图的定义和术语 7.2 图的抽象数据类型 7.3 图的存储结构 7.5 最短路径 7.6 最小生成树 2 图的遍历 (graph traversal)