图习题及参考.docx

第7章习题 一、单项选择题 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)/2 C.n(n+1)/2 D.n(n-1) 5. n个极点的连通图起码有（ ）条边。 A.n-1 B.n C.n+1 D.0 6. 在一个无向图中，全部极点的度数之和等于全部边数的 ( ) 倍。 A.3 B.2 C.1 D.1/2 7. 若采纳毗邻矩阵法储存一个 n个极点的无向图，则该毗邻矩阵是一个 ( )。 A. 上三角矩阵 B. 稀少矩阵 C.对角矩阵 D.对称矩阵 8. 图的深度优先搜寻近似于树的（ ）序次遍历。 A. 先根 B. 中根 C.后根 D.层次 9. 图的广度优先搜寻近似于树的（ ）序次遍历。 A. 先根 B. 中根 C.后根 D.层次 在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不可以在 图中构成（ ）。 A. 重边 B. 有向环 C.回路 D.权值重复的边 11. 在用Dijkstra 算法求解带权有向图的最短路径问题时， 要求图中每条边所带的权值一定是 （ ）。 A. 非零 B. 非整 C.非负 D.非正 12. 设G1=(V1,E1) 和G2=(V2,E2) 为两个图，假如 V1?V2 ，E1?E2，则称（ ）。 A.G1是G2的子图 B.G2是G1的子图 C.G 1 是G的连通重量 D.G 是G的连通重量 2 2 1 13. 有向图的一个极点的度为该极点的（ ）。 A. 入度 B.出度 C. 入度与出度之和 D.(入度﹢出度))／2 14. 一个连通图的生成树是包括图中全部极点的一个（ ）子图。 A. 极小 B. 连通 C.极小连通 D.无环 15. n(n＞1) 个极点的强连通图中起码含有（ ）条有向边。 A.n-1 B.n n(n-1)/2 D.n(n-1) 16. 在一个带权连通图 G中，权值最小的边必定包括在 G的（ ）生成树中。 A. 某个最小 B. 任何最小 C.广度优先 D.深度优先 17. 关于拥有e条边的无向图，它的毗邻表中有（ ）个结点。 A.e-1 B.e C.2(e-1) D.2e 18. 关于以下图的带权有向图，从极点 1到极点5的最短路径为（ ）。 ,4,5 B.1,2,3,5 C.1,4,3,5 D.1,2,4,3,5 1 6 4 9 2 3 1 5 2 8 3 5 19. 一个有n个极点和 n条边的无向图必定是（ ）。 A. 连通的 B. 不连通的 C.无环的 D.有环的 20. 关于有向图，其毗邻矩阵表示比毗邻表表示更易于（ ）。 A. 求一个极点的度 B.求一个极点的毗邻点 C.进行图的深度优先遍历 D.进行图的广度优先遍历 21. 与毗邻矩阵对比，毗邻表更合适于储存（ ）图。 A. 无向 B.连通 C.稀少 D.浓密图 22. 为了实现图的广度优先遍历， BFS算法使用的一个协助数据结构是（ ）。 A. 栈 B.行列 C.二叉树 D. 树 二、填空题 1. 用毗邻矩阵储存图，占用储存空间数与图中极点个数 ________关，与边数________关。 n(n﹥0)个极点的无向图最多有________条边，最罕有________条边。 3. n(n ﹥0) 个极点的连通无向图最罕有 ________条边。 0 1 0 4. 若3 个极点的图G的毗邻矩阵为1 0 0 ，则图G必定是________向图。 0 1 0 5. n(n ﹥0) 个极点的无向图中极点的度的最大值为________。 6. (n﹥0)个极点的连通无向图的生成树起码有 ________条边。 在使用Kruskal算法结构连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个 ________上，才有可能加入到生成树中。 求解带权连通图最小生成树的Prim算法合适于________图的情况，而Kruskal算法合适于________ 图的情况。 三、判断题 1.一个图的子图能够是空图，极点个数为0。 储存图的毗邻矩阵中，矩阵元素个数不只与图的极点个数有关，并且与图的边数也有关。 3. 对一个连通图进行一次深度优先搜寻（ depthfirstsearch ）能够遍访图中的全部极点。 4. 有n(n≥1)个极点的无向连通图最罕有 n-1条边。 5. 假如无向图中各个极点的度都大于 2，则该图中必有回路。 6. 假