1.2对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先搜索遍历，其算法时间复杂度是（C） A O(n) B O(e) C O(n+e) D O(n*e)
2.下列哪一种图的邻接矩阵是对称矩阵（B） A 有向图 B 无向图 C AOV网 D AOE 网
3.用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为 （A） A 5 B 6 C 8 D 9
4.如果从无向图的任一顶点出发，进行一次深度优先搜索即可访问所有的顶点，则该图一定是 （B） A 完全图 B 连通图 C 有回路 D 一棵树
5.图的深度优先遍历算法类似于二叉树的什么算法（A） A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历
6.若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图（D） A 含有多个出度为0的顶点 B 是个强连通图 C 含有多个入度为0的顶点 D 含有顶点数目大于1的强连通分量
7.下列关于图的叙述中，正确的是哪几项 1回路是简单路径 2存储稀疏图，用邻接矩阵比邻接表更省空间 3若有向图中存在拓扑序列，则该图不存在回路 （C） A 仅1 B 仅 1,2 C 仅 3 D 仅 1,3
8.在有向图G 的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是 （D） A G中有边 B G中有一条从Vi到Vj的路径 C G中没有边 D G中有一条Vj到Vi的路径
9.关键路径是事件结点图中 （A） A 从源点到汇点的最长路径 B 从源点到汇点的最短路径 C 最长回路 D 最短回路
10.下列关于AOE网的叙述中，不正确的是 （B） A 关键活动延期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动提前完成，那么整个工程将会提前完成 D 某些关键活动提前完成，那么整个工程可能提前完成
11.带权有向图G用邻域矩阵A存储，则顶点i的入度等于A中的 （D） A 第i行非∞的元素之和 B 第i列非∞的元素之和 C 第i行非∞且非零元素个数 D 第i列非∞且非零的元素个数
12.下列说法不正确的是 （B） A 图的遍历是从给定的源点出发，每一个顶点仅被访问一次。 B 图的深度优先遍历不适用于有向图。 C 遍历的基本算法有两种：深度优先搜索遍历和广度优先搜索遍历。 D 图的深度遍历是一个递归的过程。
13.无向图G=（V，E），其中V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},以顶点a为源，对该图进行深度优先遍历，得到的顶点序列正确的是 （D） 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
14.求解最短路径的弗洛伊德算法的时间复杂度为（D） A O（n） B O（n+e） C O（n^2） D O（n^3）
15.已知有向图G =（V，E），其中V={V1，V2，V3，V4，V5，V6，V7}，E={,},G的拓扑序列是 （A） A V1，V3，V4，V6，V2，V5，V7 B V1，V3，V2，V6，V4，V5，V7 C V1，V3，V4，V5，V2，V6，V7 D V1，V2，V5，V3，V4，V6，V7
二、判断题1.（F）用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是拓扑有序的。
2.（F）对图进行广度优先搜索遍历类似于二叉树的先序遍历算法。
3.（F）若一个有向图的邻接矩阵中，主对角线以下的元素均为零，则该图的拓扑有序序列一定不存在。
4.（T）当各边上的权值均相等时，BFS算法可以用来解决单源最短路径问题。
5.（T）对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是n^2。
6.（F）一个有向无环图的拓扑排序序列是唯一的。
7.（F）要连通具有n个顶点的有向图，至少需要n+1条边。
8.（T）含有n个顶点的连通无向图，其边的个数至少为n-1。
9.（T）深度优先遍历可以判断出一个有向图是否有环。
10.（T）在一个无向图中，所有顶点的度数之和等于所有边数的2 倍；在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的1倍。
