1/67.1 选择题1. 对于一个具有 n 个顶点和 e 条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为()A) O(n)B)O(n+e)C)O(n*n)D)O(n*n*n)【答案】B2. 设无向图的顶点个数为 n,则该图最多有()条边。A) n-1B)n(n-1)/2C)n(n+1)/2【答案】B3．连通分量指的是()A) 无向图中的极小连通子图B) 无向图中的极大连通子图C) 有向图中的极小连通子图D) 有向图中的极大连通子图【答案】B4．n 个结点的完全有向图含有边的数目()A)n*nB)n(n+1)C)n/2【答案】D5．关键路径是()A) AOE 网中从源点到汇点的最长路径B) AOE 网中从源点到汇点的最短路径C) AOV 网中从源点到汇点的最长路径 D)n22/6D)n*(n-1)D) AOV 网中从源点到汇点的最短路径【答案】A6．有向图中一个顶点的度是该顶点的()A)入度 B)出度 C)入度与出度之和 D)(入度+出度)/2【答案】C7. 有 e 条边的无向图，若用邻接表存储，表中有()边结点。A)eB)2eC)e-1D)2(e-1)【答案】B8. 实现图的广度优先搜索算法需使用的辅助数据结构为()A)栈 B)队列 C)二叉树 D)树【答案】B9. 实现图的非递归深度优先搜索算法需使用的辅助数据结构为()A)栈 B)队列 C)二叉树 D)树【答案】A10. 存储无向图的邻接矩阵一定是一个()A)上三角矩阵 B)稀疏矩阵 C)对称矩阵 D)对角矩阵【答案】C11. 在一个有向图中所有顶点的入度之和等于出度之和的()倍A)B)1C)2D)4答案】B3/612. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为(A)O(n)B)O(n+e)C)O(n2)D)0(n3))【答案】B13. 下列关于 AOE 网的叙述中，不正确的是()A)关键活动不按期完成就会影响整个工程的完成时间B)任何一个关键活动提前完成，那么整个工程将会提前完成C)所有的关键活动提前完成，那么整个工程将会提前完成D)某些关键活动提前完成，那么整个工程将会提前完成【答案】B14. 具有 10 个顶点的无向图至少有多少条边才能保证连通()A)9B)10C)11D)12【答案】A15. 在含 n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为()A)eB)2eC)n2-eD)n2-2e【答案】D7.2 填空题1._______________________________________________________无向图中所有顶点的度数之和等于所有边数的倍。【答案】22._______________________________________________具有 n 个顶点的无向完全图中包含有条边，具有 n 个顶点的有向完全图中包含有条边。【答案】(1)n(n-1)/2(2)n(n-1)4/63. 一个具有 n 个顶点的无向图中...
