图
一、选择题
1、n个结点的完全有向图含有边的数目（）。
A．n*n
B．n（n＋1）
C．n/2
D．n*（n－1）
D
在有向图中，如果任意两个顶点之间都存在边，则称为有向完全图。顶点个数为n的无向图，最多有Cn2＝n（n－1）/2条边。如是有向图，需要在无向图的最多边的基础上乘以2，则为n（n－1）。
2、用有向无环图描述表达式（A＋B）*（（A＋B）//A），至少需要顶点的数目为（）。
A．5
B．6
C．8
D．9
A
一共5个结点{*，/，＋，A，B}，6条边{*，/，*，＋，/，＋，＋，A，＋，B，/，A}。
3、下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每个顶点仅被访问一次
B．遍历的基本方法有两种：深度遍历和广度遍历
C．图的深度遍历不适用于有向图
D．图的深度遍历是一个递归过程
C
图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。
4、无向图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．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
D
图的深度优先遍历过程是：从图中某个初始顸点v出发，首先访问初始顶点v，然后选择一个与顶点v相邻且没被访问过的顶点u为初始顶点。再从u出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。
根据E＝{（a，b），（a，e），（a，c），（b，e），（c，f），（f，d），（e，d）}可知各顶点之间的邻接关系。依据上面的原则遍历，得出遍历顺序a，e，d，f，c，b。
5、已知有向图G＝（V，E），其中V＝{V1，V2，V3，V4，V5，V6，V7}，E＝｛V1，V2，V1，V3，V1，V4，V2，V5，V3，V5，V3，V6，V4，V6，V5，V7，V6，V7｝，G的拓扑序列是（）。
A．V1，V3，V4，V6，V2，V5，V7
B．V1，V3，V2，V6，V4，V5，V7
C．V1，V3，V5，V2，V6，V7
D．V1、V2，V5，V3，V4，V6，V7
A
设G＝（V，E）是一个具有n个顶点的有向图，V中顶点序列v1，v2，…，vn，能被称为拓扑序列的条件：若vi，vj是图中的边（即从顶点vi到vj有一条路径），则在序列中顶点vi必须排在顶点vj之前。根据上面拓扑序列的定义，就可以得出G的拓扑序列是V1，V3，V4，V5，V2，V5，V7。
6、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A．O（n）
B．O（n＋e）
C．O（n*n）
D．O（n*n*n）
B
由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为O（n＋e）。
7、下列关于AOE网的叙述中，不正确的是（）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动提前完成，那么整个工程将会提前完成
D．某些关键活动若提前完成，那么整个工程将会提前完成
B
关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
二、判断题
1有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）
×
有向图顶点V的出度等于其邻接矩阵第V行中的1的个数，而有向图中V的度等于其邻接矩阵中边表出现的V的个数。
2连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）
√
由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
3无环有向图才能进行拓扑排序。（）
√
在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。
4若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）
√
因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。
5当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）
×
当改变任意关键路径上的关键活动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
三、填空题
...
如果把生活比喻为创作的意境，那么阅读就像阳光。——池莉