一、单选题C01、在一个图中,所有顶点的度数之和等于图的边数的 倍。A. 1/2 B)1 C)2 D)4 B. 02、在一个有向图[1]中,所有顶点的入度[2]之和等于所有顶点的出度[3]之和的 倍。 C. 1/2 B)1 C)2 D)4 D. 03、有8个结点[4]的无向图[5]最多有 条边。 E. 14 F. 28 C)56 D)112 G. 04、有8个结点的无向连通图[6]最少有 条边。56 C)7 D)805、有8个结点的有向完全图[7]有 条边。14 B)28 C)56 D)11206、用邻接表[8]表示图进行广度优先遍历时,通常是采用 来实现算法的。栈队列树图07、用邻接表表示图进行深度优先遍历时,通常是采用 来实现算法的。栈队列树图08、一个含n个顶点和e条弧的有向图以邻接矩阵[9]表示法[10]为存储结构,则计算该有向图中某个顶点出度的时间复杂度为 。O(n)O(e) C)O(n+e) D)O(n2)09、已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是 。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 00 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 210、已知图的邻接矩阵同上题,根据算法,则从顶点0出发,按广度优先遍历的结点序列是 。0 2 4 3 6 5 10 1 2 3 4 6 50 4 2 3 1 5 6 D)0 1 3 4 2 5 611、已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是 。}/for}/else_path_DFS解2:(以上算法似乎有问题:如果不存在路径,则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。)[MAXSIZE]; /指示顶点是否在当前路径上int level=1;/递归进行的层数_path_DFS(ALGraph G,int i,int j)/深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0(if(i==j) return 1; /i就是jlse{[i]=1;vertices[i].firstarc;p;p=p->nextarc,level--){ level++;djvex;[k]exist_path(k,j)) return 1;/i下游的顶点到j有路径)/for}/elseif (level==1) return 0;_path_DFSsquare 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 00 1 3 20 2 3 10 3 2 10 1 2 312、已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是 。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 00 3 2 10 1 2 30 1 3 20 3 1 213、图的深度优先遍历类似于二叉树的 。先序遍历中序遍历后序遍历 D)层次遍历14、图的广度优先遍历类似于二叉树的 。先序遍历 B)中序遍历 C)后序遍历 D)层次遍历15、任何一个无向连通图的最小生成树 。只有一棵一棵或多棵一定有多棵可能不存在16、对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为 ,所有边链表中边结点的总数为 。n、2en、e C)n、n+e D)2n、2e17、判断有向图是否存在回路,可以利用___算法。最短路径的Dijkstra拓扑排序广度优先遍历18、若用邻接矩阵表示一个有向图,则其中每一列包含的“1”的个数为 。图中每个顶点的入度图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目19、求最短路径的ijkstra算法的时间复杂度是___。O(n) B)O(n+e) C)O(n2) D)O(n*e)20、设图G采用邻接表存储,则拓扑排序算法的时间复杂度为 。O(n)O(n+e)O(n2) D)O(n*e)21、带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中 。第i行非∞的元素之和第i列非∞的元素之和第i行非∞且非0的元素个数第i列非∞且非0的元素个数22、一个有n个顶点的无向图最多有 条边。nn(n-1)n(n-1)/2 D)2n23、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是 。n(n-1)2n-1n224、对某个无向图的邻接矩阵来说, 。第i行上的非零元素个数和第i列的非零元素个数一定相等矩阵中的非零元素个数等于图中的边数第i行上,第i列上非零元素总数等于顶点vi的度数矩阵中非全零行的行数等于图中的顶点数25、已知图的表示如下,若从顶点a出发按深度搜索法进行遍历,则可能得到的一种顶点序列为 。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 0abecdf B)acfebd C)aebcfd D)aedfcb26、已知图的表示如上题,若从顶点a出发按广度搜索法进行遍历,则可能得到的一种顶点序列为 。abcedfabcefd C)aebcfd D)acfdeb27、有向图的邻接表存储结构如下图所示,则根据有向图的深度遍历算法,从顶点v1出发得到的顶点序列是 。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 0v1,v2,v3,v5,v4 B)v1,v2,v3,v4,v5 C)v1,v3,v4,v5,v2 D)v1,v4,v3,v5,v228、有向图的邻接表存储结构如上题所示,则根据有向图的广度遍历算法,从顶点v1出发得到的顶点序列是 。v1,v2,v3,v4,v5v1,v3,v2,v4,v5v1,v2,v3,v5,v4v1,v4,v3,v5,v229、一个图中有n个顶点且包含k个连通分量,若按深度优先搜索方法访问所有结点,则必须调用 次深度优先遍历算法。k1n-k D)n30、以下不正确的说法是 。无向图中的极大连通子图称为连通分量连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点有向图的遍历不可采用广度优先搜索方法31、图中有关路径的定义是___。由顶点和相邻顶点序偶构成的边所形成的序列由不同顶点所形成的序列由不同边所形成的序列上述定义都不是32、设无向图的顶点个数为n,则该图最多有___条边。n-1n(n-1)/2n(n+1)/2n33、一个n 个顶点的连通无向图,其边的个数至少为___。n-1 B)n C)n+1 D)nlogn34、要连通具有n 个顶点的有向图,至少需要___条边。n-l B)n C)n+l D)2n35、在一个无向图中,所有顶点的度数之和等于所有边数___倍。1/22 C)1 D)436、在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的___倍。1/2214*((A+B)/A),至少需要顶点的数目为___。568938、用DFS 遍历一个无环有向图,并在DFS 算法退栈返回时打印相应的顶点,则输出的顶点序列是___。逆拓扑有序 B)拓扑有序 C)无序的 D)原顺序39、下列___的邻接矩阵是对称矩阵。有向图 B)无向图 C)AOV网 D)AOE网BD40、从邻接阵矩square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 0 可以看出,该图共有 ① 个顶点;如果是有向图该图共有 ② 条弧;如果是无向图,则共有 ③ 条边。9361以上答案均不正确5432以上答案均不正确5 B)4 C)3 D)2 E)以上答案均不正确41、当一个有N 个顶点的图用邻接矩阵A 表示时,顶点Vi 的度是___。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 042、下列说法不正确的是___。图的遍历是从给定的源点出发每一个顶点仅被访问一次图的深度遍历不适用于有向图遍历的基本算法有两种:深度遍历和广度遍历 D)图的深度遍历是一个递归过程,其中:V=(a,b,c,d,e,f),E=((a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)),对该图进行深度优先遍历,得到的顶点序列正确的是___。abecdfacfebdaebcfd D)aedfcb44、如图所示,在5个序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”,符合深度优先遍历的序列有___个。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 054 C)3 D)2C45、图中给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先遍历得到的序列是 ① ,进行广度优先遍历得到的顶点序列是 ② 。square 1 1 1 1 0 1-|||-1 0 square 1 square 0 1-|||-1 0 square 0 1 0 0-|||-1 1 square square 1 1 square -|||-1 0 1 1 square 1 0-|||-square 0 square 1 1 square 1-|||-1 1 square 0 square 1 01354267134765215342761247653以上答案均不正确1534267 B)1726453 C)l354276 D)1247653 E)以上答案均不正确46、在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为___。O(n)O(n+e) C)O(n2) D)O(n3)ABA47、下面是求连通网的最小生成树的prim算法:集合VT,ET分别放顶点和边,初始为 ① ,下面步骤重复n-1次: ② ; ③ ;最后: ④ 。VT,ET 为空VT为所有顶点,ET为空VT为网中任意一点,ET为空VT为空,ET为网中所有边选i属于VT,j不属于VT,且(i,j)上的权最小选i属于VT,j不属于VT,且(i,j)上的权最大选i不属于VT,j不属于VT,且(i,j)上的权最小选i不属于VT,j不属于VT,且(i,j)上的权最大顶点i加入VT,(i,j)加入ET顶点j加入VT,(i,j)加入ET顶点j加入VT,(i,j)从ET中删去顶点i,j加入VT,(i,j)加入ETET中为最小生成树不在ET中的边构成最小生成树ET 中有n-1条边时为生成树,否则无解ET中无回路时,为生成树,否则无解48、下面不正确的是___。ijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义;ijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3);(图用邻接矩阵表示)loyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。①②③①①③②③49、已知有向图G=(V,E),其中V=(V1,V2,V3,V4,V5,V6,V7),E=(, , , , , , , , ),则G的拓扑序列是___。V1,V3,V4,V6,V2,V5,V7V1,V3,V2,V6,V4,V5,V7V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V750、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是___。G中有弧G中有一条从Vi到Vj的路径G中没有弧G 中有一条从Vj到Vi的路径51、关键路径是事件结点网络中___。从源点到汇点的最长路径从源点到汇点的最短路径 C)最长回路 D)最短回路52、下面关于求关键路径的说法不正确的是___。求关键路径是以拓扑排序为基础的一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差关键活动一定位于关键路径上53、下列关于AOE网的叙述中,不正确的是___。关键活动不按期完成就会影响整个工程的完成时间任何一个关键活动提前完成,那么整个工程将会提前完成所有的关键活动提前完成,那么整个工程将会提前完成某些关键活动提前完成,那么整个工程将会提前完成

一、单选题

C01、在一个图中,所有顶点的度数之和等于图的边数的 倍。

A. 1/2 B)1 C)2 D)4
B. 02、在一个有向图^[1]中,所有顶点的入度^[2]之和等于所有顶点的出度^[3]之和的 倍。
C. 1/2 B)1 C)2 D)4
D. 03、有8个结点^[4]的无向图^[5]最多有 条边。
E. 14
F. 28 C)56 D)112
G. 04、有8个结点的无向连通图^[6]最少有 条边。
5
6 C)7 D)8
05、有8个结点的有向完全图^[7]有 条边。
14 B)28 C)56 D)112
06、用邻接表^[8]表示图进行广度优先遍历时,通常是采用 来实现算法的。
栈
队列
树
图
07、用邻接表表示图进行深度优先遍历时,通常是采用 来实现算法的。
栈
队列
树
图
08、一个含n个顶点和e条弧的有向图以邻接矩阵^[9]表示法^[10]为存储结构,则计算该有向图中某个顶点出度的时间复杂度为 。
O(n)
O(e) C)O(n+e) D)O(n2)
09、已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是 。

0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2
10、已知图的邻接矩阵同上题,根据算法,则从顶点0出发,按广度优先遍历的结点序列是 。
0 2 4 3 6 5 1
0 1 2 3 4 6 5
0 4 2 3 1 5 6 D)0 1 3 4 2 5 6
11、已知图的邻接表如下所示,根据算法,则从顶点0出发按深度优先遍历的结点序列是 。
}//for
}//else
_path_DFS
解2:(以上算法似乎有问题:如果不存在路径,则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。)
[MAXSIZE]; //指示顶点是否在当前路径上
int level=1;//递归进行的层数
_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j
是否有路径,是则返回1,否则返回0
{
if(i==j) return 1; //i就是j
lse
{
[i]=1;
vertices[i].firstarc;p;p=p->nextarc,level--)
{ level++;
djvex;
[k]exist_path(k,j)) return 1;//i下游的顶点到j有路径
}//for
}//else
if (level==1) return 0;
_path_DFS

0 1 3 2
0 2 3 1
0 3 2 1
0 1 2 3
12、已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是 。

0 3 2 1
0 1 2 3
0 1 3 2
0 3 1 2
13、图的深度优先遍历类似于二叉树的 。
先序遍历
中序遍历
后序遍历 D)层次遍历
14、图的广度优先遍历类似于二叉树的 。
先序遍历 B)中序遍历 C)后序遍历 D)层次遍历
15、任何一个无向连通图的最小生成树 。
只有一棵
一棵或多棵
一定有多棵
可能不存在
16、对于一个具有n个结点和e条边的无向图,若采用邻接表表示,则顶点表的大小为 ,所有边链表中边结点的总数为 。
n、2e
n、e C)n、n+e D)2n、2e
17、判断有向图是否存在回路,可以利用___算法。

最短路径的Dijkstra
拓扑排序
广度优先遍历
18、若用邻接矩阵表示一个有向图,则其中每一列包含的“1”的个数为 。
图中每个顶点的入度
图中每个顶点的出度 C)图中弧的条数 D)图中连通分量的数目
19、求最短路径的
ijkstra算法的时间复杂度是___。
O(n) B)O(n+e) C)O(n2) D)O(n*e)
20、设图G采用邻接表存储,则拓扑排序算法的时间复杂度为 。
O(n)
O(n+e)
O(n2) D)O(n*e)
21、带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中 。
第i行非∞的元素之和
第i列非∞的元素之和
第i行非∞且非0的元素个数
第i列非∞且非0的元素个数
22、一个有n个顶点的无向图最多有 条边。
n
n(n-1)
n(n-1)/2 D)2n
23、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是 。
n
(n-1)2
n-1
n2
24、对某个无向图的邻接矩阵来说, 。
第i行上的非零元素个数和第i列的非零元素个数一定相等
矩阵中的非零元素个数等于图中的边数
第i行上,第i列上非零元素总数等于顶点vi的度数
矩阵中非全零行的行数等于图中的顶点数
25、已知图的表示如下,若从顶点a出发按深度搜索法进行遍历,则可能得到的一种顶点序列为 。

abecdf B)acfebd C)aebcfd D)aedfcb
26、已知图的表示如上题,若从顶点a出发按广度搜索法进行遍历,则可能得到的一种顶点序列为 。
abcedf
abcefd C)aebcfd D)acfdeb
27、有向图的邻接表存储结构如下图所示,则根据有向图的深度遍历算法,从顶点v1出发得到的顶点序列是 。

v1,v2,v3,v5,v4 B)v1,v2,v3,v4,v5 C)v1,v3,v4,v5,v2 D)v1,v4,v3,v5,v2
28、有向图的邻接表存储结构如上题所示,则根据有向图的广度遍历算法,从顶点v1出发得到的顶点序列是 。
v1,v2,v3,v4,v5
v1,v3,v2,v4,v5
v1,v2,v3,v5,v4
v1,v4,v3,v5,v2
29、一个图中有n个顶点且包含k个连通分量,若按深度优先搜索方法访问所有结点,则必须调用 次深度优先遍历算法。
k
1
n-k D)n
30、以下不正确的说法是 。
无向图中的极大连通子图称为连通分量
连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
有向图的遍历不可采用广度优先搜索方法
31、图中有关路径的定义是___。
由顶点和相邻顶点序偶构成的边所形成的序列
由不同顶点所形成的序列
由不同边所形成的序列
上述定义都不是
32、设无向图的顶点个数为n,则该图最多有___条边。
n-1
n(n-1)/2
n(n+1)/2
n
33、一个n 个顶点的连通无向图,其边的个数至少为___。
n-1 B)n C)n+1 D)nlogn
34、要连通具有n 个顶点的有向图,至少需要___条边。
n-l B)n C)n+l D)2n
35、在一个无向图中,所有顶点的度数之和等于所有边数___倍。
1/2
2 C)1 D)4
36、在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的___倍。
1/2
2
1
4

*((A+B)/A),至少需要顶点的数目为___。
5
6
8
9
38、用DFS 遍历一个无环有向图,并在DFS 算法退栈返回时打印相应的顶点,则输出的顶点序列是___。
逆拓扑有序 B)拓扑有序 C)无序的 D)原顺序
39、下列___的邻接矩阵是对称矩阵。
有向图 B)无向图 C)AOV网 D)AOE网
BD40、从邻接阵矩 可以看出,该图共有 ① 个顶点;如果是有向图该图共有 ② 条弧;如果是无向图,则共有 ③ 条边。
9
3
6
1
以上答案均不正确
5
4
3
2
以上答案均不正确
5 B)4 C)3 D)2 E)以上答案均不正确
41、当一个有N 个顶点的图用邻接矩阵A 表示时,顶点Vi 的度是___。

42、下列说法不正确的是___。
图的遍历是从给定的源点出发每一个顶点仅被访问一次
图的深度遍历不适用于有向图
遍历的基本算法有两种:深度遍历和广度遍历 D)图的深度遍历是一个递归过程

,其中:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是___。
abecdf
acfebd
aebcfd D)aedfcb
44、如图所示,在5个序列“aebdfc、acfdeb、aedfcb、aefdcb、aefdbc”,符合深度优先遍历的序列有___个。

5
4 C)3 D)2
C45、图中给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先遍历得到的序列是 ① ,进行广度优先遍历得到的顶点序列是 ② 。

1354267
1347652
1534276
1247653
以上答案均不正确
1534267 B)1726453 C)l354276 D)1247653 E)以上答案均不正确
46、在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为___。
O(n)
O(n+e) C)O(n2) D)O(n3)
ABA47、下面是求连通网的最小生成树的prim算法:集合VT,ET分别放顶点和边,初始为 ① ,下面步骤重复n-1次: ② ; ③ ;最后: ④ 。
VT,ET 为空
VT为所有顶点,ET为空
VT为网中任意一点,ET为空
VT为空,ET为网中所有边
选i属于VT,j不属于VT,且(i,j)上的权最小
选i属于VT,j不属于VT,且(i,j)上的权最大
选i不属于VT,j不属于VT,且(i,j)上的权最小
选i不属于VT,j不属于VT,且(i,j)上的权最大
顶点i加入VT,(i,j)加入ET
顶点j加入VT,(i,j)加入ET
顶点j加入VT,(i,j)从ET中删去
顶点i,j加入VT,(i,j)加入ET
ET中为最小生成树
不在ET中的边构成最小生成树
ET 中有n-1条边时为生成树,否则无解
ET中无回路时,为生成树,否则无解
48、下面不正确的是___。
ijkstra最短路径算法中弧上权不能为负的原因是在实际应用中无意义;
ijkstra求每一对不同顶点之间的最短路径的算法时间是O(n3);(图用邻接矩阵表示)
loyd求每对不同顶点对的算法中允许弧上的权为负,但不能有权和为负的回路。
①②③
①
①③
②③
49、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={, , , , , , , , },则G的拓扑序列是___。
V1,V3,V4,V6,V2,V5,V7
V1,V3,V2,V6,V4,V5,V7
V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V7
50、在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是___。
G中有弧
G中有一条从Vi到Vj的路径
G中没有弧
G 中有一条从Vj到Vi的路径
51、关键路径是事件结点网络中___。
从源点到汇点的最长路径
从源点到汇点的最短路径 C)最长回路 D)最短回路
52、下面关于求关键路径的说法不正确的是___。
求关键路径是以拓扑排序为基础的
一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
关键活动一定位于关键路径上
53、下列关于AOE网的叙述中,不正确的是___。
关键活动不按期完成就会影响整个工程的完成时间
任何一个关键活动提前完成,那么整个工程将会提前完成
所有的关键活动提前完成,那么整个工程将会提前完成
某些关键活动提前完成,那么整个工程将会提前完成