A.n B.n(n-1) C. n(n+1) D.n^2
解析：对于有n个顶点的有向图，边数最多的情况是：任意一个点到其他n-1个点都有一条有向边，即最多有n(n-1)条边。换个角度，因为有向图的边有方向之分，最多的变数即从n个顶点中选取2个顶点的有序排列，结果为n(n-1)
A.n B.2(n-1) C.n/2 D.n^2
解析：n个顶点的连通图至少需要n-1条边，由于无向图的每条边同时关联两个顶点，所以邻接矩阵中每条边都存储两次，即矩阵中至少有2(n-1)个非零元素
A.7 B.8 C.9 D.10
解析：根据无向图是具有n(n-1)/2条边的特点，可得8个顶点的连通无向图最多有8*7/2=28条边，再添加一个点构成非连通图无向图
1.Dijkstra算法中弧上权值不能为负的原因是负数再实际应用中无意义
2.利用Dijkstra算法求每对顶点之间的最短路径算法的时间复杂度为O(n^3)(图用邻接矩阵表示)
3.Floyd求每对顶点之间的最短路径算法中允许弧上的权值为负数，但不能有权值和为负数的回路
A.1、2、3 B.1 C.1、3 D.2、3
解析：1.Dijkstra算法是按路径长度递增的次序求解最短路径的，每次选取路径最短的顶点后，需要对尚未求得最短路径的其他顶点依次进行更新，如果权值为负数，更新之后某个顶点的路径可能比之前已求得的路径短，出现矛盾。所以Dijkstra算法中弧上权值不能为负的原因是本身的适用条件不允许权值为负数。23正确
A.第i行非无穷的元素之和
B.第i列非无穷的元素之和
C.第i行非无穷且非0的元素之和
D.第i列非无穷且非0的元素之和
解析：顶点Vi的出度是第i行非无穷且非0的元素之和，顶点Vi的入度是第i列非无穷且非0的元素之和
A.1 B.n-1 C.n D.2n
解析：n个顶点构成的环有n条边，去掉任意一条便是一棵生成树
A.都相等 B.都不相等 C.不一定都相等 D.都大于0
解析：BFS从起点开始逐层向外层扩展遍历的顶点，无法考虑边的权值，只适合求权值相等的图的单源点最短路径问题
A.O(n) B.O(e) C.O(n+e) D.O(n*e)
解析：删除与某个顶点v相关的所有边时，首先需要删除以v为头结点的单链表（删除顶点v的出边），最多有n-1个结点，时间复杂度为O(n)，其次扫描所有边表的结点，删除顶点v的入边，时间复杂度为O(e)，总时间复杂度为O(n+e)
A.只要无向连通图中没有权值相同的边，则其最小生成树唯一
B.只要无向图中有权值相同的边，则其最小生成树一定不唯一
C.从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树
D.设连通图G含有n个顶点，则含有n个顶点、n-1条边的子图一定是G的生成树
解析：当无权值相同的边全部包含于最小生成树中时，则最小生成树唯一，B错误；选取n-1条权值最小的边可能会构成回路，C错误；含有n个顶点、n-1条边的子图可能会构成回路，也可能不连通，D错误
1.所有顶点的度之和为偶数
2.边数大于顶点个数减1
3.至少有一个顶点的度为1
A.只有1 B.只有2 C.1和2 D.1和3
解析：1.无向连通图所有顶点度数之和是边的两倍，所以1正确；无向连通图对应的生成树也是无向连通图，此时边数等于顶点个数减1，所以2错误；3的话，如果图中只包含一个连接所以顶点的环，图的边数等于顶点个数，每个顶点的度都是2，也错了
A.n B.e C.2e D.ne
解析：在邻接表中，对图中每个顶点Vi建立一个单链表，把Vi相邻接的顶点放在这个链表中，链表中的每一个结点代表一条弧，题中e条弧，故弧结点有e个
A.最小 B.唯一 C.广度优先 D.深度优先
解析：设N=(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值的边，其中u∈U，v∈V-U，则存在一棵包含边(u,v)的最小生成树。由于各边权值各不相同，所以最小生成树唯一，因此权值最小的边一定包含在G的最下生成树中
A.6 B.15 C.16 D.21
解析：要保证任意变动图G的边，图G始终保持连通状态，考虑极端情况，图G的6个顶点构成完全连通子图G1，则跟第3题一样计算，G1有6*5/2=15条边，再加一条边，第7个顶点与G1构成连通图，所以边至少要16条，再少就不合适了
A.4 B.3 C.2 D.1
解析：如下图所示，按照拓扑排序的步骤画出排序序列
A.存在，且唯一 B.存在，且不唯一 C.存在，可能不唯一 D.无法确定是否存在
解析：对角线以下的元素均为零，表明只有顶点Vi到顶点Vj(i<j)可能有边，而顶点Vj到顶点Vi一定没边。简单来说，该图一定没有回路，所以可以产生拓扑序列，但拓扑序列不一定唯一
1.最小生成树的代价之和唯一
2.权值最小的边一定会出现在所有的最小生成树中
3.用普里姆(prim)算法从不同顶点开始得到的最小生成树一定相同
4.使用普里姆和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同
A.仅1 B.仅2 C.仅1，3 D.仅2，4
解析：1正确；2错误：如果权值最小的边有多条但产生回路，那么需要去掉某些权值最小的边来避免回路；3错误：当产生多条权值相同的边时，用prim算法从不同顶点开始得到的最小生成树不一样相同；4错误：在构造最小生成树时，prim算法通过不断归并点，Kruskal算法通过不断归并边完成，二者构造的最小生成树可能相同，也可能不同
A.c和e B.d和c C.f和d D.f和h
解析：这题需要求出所有关键路径之后再进行比较选项，ABD中虽然是关键活动，但不能包含所有的，只有C是三条关键路径都涉及到的
A.2 B.3 C.4 D.5
解析：画出该有向图，如下图所示。从顶点V0开始对图进行深度优先遍历，共有5中可能的不同遍历序列：V0,V1,V3,V2、V0,V2,V1,V3、V0,V2,V3,V1、V0,V3,V2,V1、V0,V3,V1,V2
A.O(n) B.O(n+e) C.O(n^2) D.O(n*e)
解析：采用邻接表实现拓扑排序时，要通过建立入度数组来计算各顶点的入度。对于有n个顶点和e条边的有向图而言，建立入度数组的复杂度为O(e)，建立零入度顶点栈的时间复杂度为O(n)。在拓扑排序过程中，若有向无环图，则每个顶点进一次栈，出一次栈，入度减1的操作在循环中执行e次，所以，总的时间复杂度为O(n+e)
A.10 B.11 C. 13 D. 15
解析：由于无向图各顶点度数的总和为边数的2倍，题目有写无向图G有16条边，所以各顶点度数的总和为32。又因为度为4的顶点个数为3，度为3的顶点个数为4，则其他顶点的度数为32-4*3-3*4=8，又因为其他顶点的度均小于3，求顶点个数最少的情况，设其度均为2，则度为2的顶点个数为8/2=4，因此图G所含的顶点个数至少是11个
(x+y)*((x+y)/x)，需要的顶点个数至少是（A）A.5 B.6 C.8 D.9
解析：将中缀表达式转换为二叉树，再将二叉树去重转换为有向无环图，如下图所示
A.拓扑有序序列 B.逆拓扑有序序列 C.广度优先搜索序列 D.深度优先搜索序列
解析：拓扑序列将AOV网中所有顶点排成一个线性序列，该序列满足：若在AOV网中由顶点Vi到顶点Vj有一条路径，则在该线性序列中的顶点Vi必定在顶点Vj之前。递归方式实现的DFS算法，在遍历过程中，先访问的点压到栈底，搜索路径是从最后一个被访问的顶点开始输出，最后一个输出的顶点是第一个被访问的顶点，所以输出的顶点序列是G的逆拓扑有序序列
A.关键路径是从源点到汇点边数最多的一条路径
B.关键路径是从源点到汇点路径长度最长的路径
C.增加任一关键活动的时间不会延长工程的工期
D.缩短任一关键活动的时间将会缩短工程的工期
解析：在AOE网中，从源点到汇点的带权路径长度最长的路径称为关键路径。任一活动持续时间的改变都可能引起关键路径的改变，会影响工程的工期
这章的主要内容是学会prim算法、Kruskal算法、Dijkstra算法、AOV网、AOE网、DFS遍历算法、BFS遍历算法