《《第八章试题》》由会员分享，可在线阅读，更多相关《《第八章试题》（24页珍藏版）》请在金锄头文库上搜索。
1、书据结构课程（本科）第八章试题一、单项选择题1. 在无向图中定义顶点的度为与它相关联的（ ）的数目。A. 顶点B. 边C. 权D. 权值2. 在无向图中定义顶点 vi与vj之间的路径为从vi到达vj的一个（ ）。A. 顶点序列B. 边序列C. 权值总和D. 边的条数3. 图的简单路径是指（ ）不重复的路径。A. 权值B. 顶点C. 边D. 边与顶点均4. 设无向图的顶点个数为n，则该图最多有（ ）条边。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1) 5. n个顶点的连通图至少有（ ）条边。A. n-1 B. nC. n+1D. 06. 在一个无向图中，所有顶点的
2、度数之和等于所有边数的 ( ) 倍。A. 3B. 2C. 1D. 1/27. 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵8. 图的深度优先搜索类似于树的（ ）次序遍历。A. 先根B. 中根C. 后根D. 层次9. 图的广度优先搜索类似于树的（ ）次序遍历。A. 先根B. 中根C. 后根D. 层次10. 在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（ ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A. 位向量B. 堆C. 并查集D. 生成树顶点集合11. 在用Kruskal
3、算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（ ）。A. 重边B. 有向环C. 回路D. 权值重复的边12. 在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（ ）。A. 非零B. 非整C. 非负D. 非正13. 在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少有（ ）子女。A. 1B. 2C. 3D. 014. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2
4、)15. 设有向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。A. O(nlog2e)B. O(n+e)C. O(ne)D. O(n2)16. 设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1 V2，E1 E2，则称（ ）。 A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量17. 有向图的一个顶点的度为该顶点的（ ）。 A. 入度 B. 出度C. 入度与出度之和 D. (入度出度)218. 一个连通图的生成树是包含图中所有顶点的一个（ ）子图。 A. 极小B. 连通C
5、. 极小连通D. 无环19. n (n1) 个顶点的强连通图中至少含有（ ）条有向边。 A. n-1 B. nn(n-1)/2D. n(n-1)20. 在一个带权连通图G中，权值最小的边一定包含在G的（ ）生成树中。 A. 某个最小B. 任何最小C. 广度优先D.深度优先21. 对于具有e条边的无向图，它的邻接表中有（ ）个边结点。 A. e-1B. e C. 2(e-1) D. 2e22. 对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（ ）。 A.1, 4, 5B. 1, 2, 3, 5C. 1, 4, 3, 5D. 1, 2, 4, 3, 51261381955412323. 具
6、有n个顶点的有向无环图最多可包含（ ）条有向边。 A. n-1B. n C. n(n-1)/2 D.n(n-1)24. 一个有n个顶点和n条边的无向图一定是（ ）。 A. 连通的 B. 不连通的 C. 无环的 D. 有环的25. 在n个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。 A. nB. n(n-1)/2 C. n(n+1)/2D. n(n-1)26. 对于有向图，其邻接矩阵表示比邻接表表示更易于（ ）。 A. 求一个顶点的度 B. 求一个顶点的邻接点 C. 进行图的深度优先遍历 D. 进行图的广度优先遍历27. 在一个有向图的邻接矩阵表示中，删除一条边需要耗费的时间是（ ）。 A
7、. O(1) B. O(i) C. O(j) D. O(i+j)28. 与邻接矩阵相比，邻接表更适合于存储（ ）图。 A. 无向B.连通C.稀疏 D. 稠密图29. 设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（ ）。 A. O(n) B. O(e) C. O(n+e) D. O(n2)30. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（ ）。 A. 栈 B. 队列C. 二叉树 D. 树参考答案：1. B2. A3. B4. B5. A 6. B7. D8. A9. D10. C11.C12. C13. B14. B15. D16. A
8、17. C18. C 19. B 20. A21. D 22. D 23. C24. D 25. C26. A 27. A 28. C 29. A 30. B 二、填空题1. 图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷_集合。2. 用邻接矩阵存储图，占用存储空间数与图中顶点个数_关，与边数_关。3. n (n0) 个顶点的无向图最多有_条边，最少有_条边。4. n (n0) 个顶点的连通无向图最少有_条边。5. 若3个顶点的图G的邻接矩阵为，则图G一定是_向图。6. n (n0) 个顶点的连通无向图各顶点的度之和最少为_。7. 设图G = (V, E)，V = V0, V1
9、, V2, V3, E = (V0, V1), (V0, V2), (V0, V3), (V1, V3)，则从顶点V0开始的图G的不同深度优先序列有_种，例如_。8. 设图G = (V, E)，V = P, Q, R, S, T, E = , , , ，从顶点P出发，对图G进行广度优先搜索所得的所有序列为_和_。9. n (n0) 个顶点的无向图中顶点的度的最大值为_。10. 在重连通图中每个顶点的度至少为_。11. 在非重连通图中进行深度优先搜索，则深度优先生成树的根为关节点的充要条件是它至少有_个子女。12. (n0) 个顶点的连通无向图的生成树至少有_条边。13. 101个顶点的连通网络
10、N有100条边，其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各10条，则网络N的最小生成树各边的权值之和为_。14. 在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个_上，才有可能加入到生成树中。15. 深度优先生成树的高度比广度优先生成树的高度_。16. 求解带权连通图最小生成树的Prim算法适合于_图的情形，而Kruskal算法适合于_图的情形。17. 求解最短路径的Dijkstra算法适用于各边上的权值_的情形。若设图的顶点数为n，则该算法的时间复杂度为_。18. 若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的
11、所有顶点按其先后次序重新编号，则在相应的邻接矩阵中所有_元素将集中到对角线以上。参考答案：1. 非空2. 有, 无3. n(n-1)/2, 04. n-15. 有 6. 2(n-1)7. 4，V0V1V3V2（或V0V2V1V3, V0V2V3V1, V0V3V1V2）8. PQRST和PRQTS9. n-110. 211. 212. n-1 13. 55014. 连通分量15. 高16. 稠密，稀疏17. 非负，O(n2)18. 非零（或值为1的）三、判断题1. 一个图的子图可以是空图，顶点个数为0。2. 存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。3. 一
12、个有1000个顶点和1000条边的有向图的邻接矩阵是一个稀疏矩阵。4. 对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。5. 有n (n1) 个顶点的无向连通图最少有n-1条边。6. 有n (n1) 个顶点的有向强连通图最少有n条边。7. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以因为某种需要改变顶点的编号。8. 如果无向图中各个顶点的度都大于2，则该图中必有回路。9. 如果有向图中各个顶点的度都大于2，则该图中必有回路。10. 图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求解。11. 图的广度优先搜索（breadth first search）算法不是递归算法。12. 有n个顶点、e条边的带权有向图的最小生成树一般由n个顶点和n-1条边组成。13. 对于一个边上权值任意的带权有向图，使用Dijkstr
