单项选择题
1．在一个图中，所有顶点的度数之和等于所有边数的____倍。
A. 1/2        B. 1      C. 2      D. 4
2．任何一个无向连通图的最小生成树    。
A.只有一棵        B.有一棵或多棵        C.一定有多棵        D.可能不存在
3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。
A. 1/2        B. 1      C. 2      D. 4
4．一个有n个顶点的无向图最多有____条边。先序中序后序遍历二叉树
A. n          B. n(n-1)      C. n(n-1)/2      D. 2n
5．具有4个顶点的无向完全图有____条边。
A. 6      B. 12    C. 16      D. 20
6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5    B. 6    C. 7      D. 8
7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。
A. n    B. n+1    C. n-1    D. n/2
8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。
A. n    B. (n-1)2      C. n-1    D. n2
9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。
① A. n    B. n+1    C. n-1    D. n+e
② A. e/2    B. e            D. n+e 
10．已知一个图如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到
的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列
为__②__。
① A. a,b,e,c,d,f      B. e,c,f,e,b,d        C. a,e,b,c,f,d        D. a,e,d,f,c,b
② A. a,b,c,e,d,f      B. a,b,c,e,f,d        C. a,e,b,c,f,d        D. a,c,f,d,e,b
   
11．已知一有向图的邻接表存储结构如图所示。
⑴ 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A. v1,v2,v3,v5,v4        B. v1,v2,v3,v4,v5
C. v1,v3,v4,v5,v2        D. v1,v4,v3,v5,v2
⑵ 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A. v1,v2,v3,v4,v5        B. v1,v3,v2,v4,v5
C. v1,v2,v3,v5,v4        D. v1,v4,v3,v5,v2
12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。
A. 先序遍历      B. 中序遍历      C. 后序遍历    D. 按层遍历
13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。
A. 先序遍历      B. 中序遍历      C. 后序遍历    D. 按层遍历
14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。
A. 求关键路径的方法              B. 求最短路径的Dijkstra方法
C. 宽度优先遍历算法              D. 深度优先遍历算法
15．关键路径是事件结点网络中  。
A.从源点到汇点的最长路径        B.从源点到汇点的最短路径
C.最长的回路                    D.最短的回路
16．下面不正确的说法是    。
    （1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小；
    （2）AOE网工程工期为关键活动上的权之和；
    （3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
A.（1）            B.（2）            C.（3）            D.（1）、（2）
17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是   。
A.逆拓朴有序的        B.拓朴有序的            C.无序的
18．在图所示的拓朴排列的结果序列为    。
                B.516234                           
图有向图
19．一个有n个顶点的无向连通图，它所包含的连通分量个数为  。
            B.1                        +1
20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为    。
            2                    +k2
21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为    。
            2                    +k2
  填空题（将正确的答案填在相应饿空中）
1．n个顶点的连通图至少____条边。
2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。
3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。
4．已知图G的邻接表如图所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。
          图  图G的邻接表
5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。
6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。
7．如果含n个顶点的图形成一个环，则它有      棵生成树。
8．一个非连通无向图，共有28条边，则该图至少有    个顶点。
9．遍历图的过程实质上是        。BFS遍历图的时间复杂度为      ，DFS遍历图的时间复杂度为      ，两者不同之处在于      ，反映在数据结构上的差别是    。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。