数据结构第7章 图习题
第7章图
一、单项选择题
1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。
A．l/2 B．1
C．2 D．4
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。
A．l/2 B．1
C．2 D．4
3．一个具有n个顶点的无向图最多包含______条边。
A．n B．n＋1
C．n-1 D．n(n-1)/2
4．一个具有n个顶点的无向完全图包含______条边。
A．n(n-l) B．n(n+l)
C．n(n-l)/2 D．n(n-l)/2
5．一个具有n个顶点的有向完全图包含______条边。
A．n(n-1) B．n(n+l)
C．n(n-l)/2 D．n(n+l)/2
6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。
A．n B．n×n
C．n-1 D．(n-l) ×(n-l)
7．无向图的邻接矩阵是一个______。
A．对称矩阵B．零矩阵
C．上三角矩阵D．对角矩阵
8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。
A．n B．e
C．2n D．2e
9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。
A．n B．e
C．2n D．2e
10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。
A．入边B．出边
C．入边和出边D．不是入边也不是出边
11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。
A．入边B．出边
C．入边和出边D．不是人边也不是出边
12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。
A．完全图B．连通图
C．有回路D．一棵树
13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。
A．先序遍历B．中序遍历
C．后序遍历 D．按层遍历
14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。
A．先序遍历B．中序遍历
C．后序遍历 D．按层遍历
15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。
A．G肯定不是完全图B．G一定不是连通图
C．G中一定有回路D．G有二个连通分量
16．下列有关图遍历的说法不正确的是______。
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
17．下列说法中不正确的是______。
A．无向图中的极大连通子图称为连通分量
B ．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C ．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D ．有向图的遍历不可采用广度优先搜索方法
18．一个有向图G 的邻接表存储如下图7-1所示，现按深度优先搜索遍历，从顶点v 1出发，所得到的顶点序列是______。
A ．v 1，v 2，v 3，v 4，v 5
B ．v 1，v 2，v 3，v 5，v 4
C ．v 1，v 2，v 4，v 5，v 3
D ．v 1，v 2，v 5，v 3，v 4
图7-1 一个有向图的邻接表
19．对图7-2所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问
序列______。
A ．1，2，4，3，
5，7，6 B ．1，2，4，3，5，6，7 C ．1，2，4，5，6，3，7 D ．1，2，3，4，5，7，6
图7-2 一个无向图
20．对图7-2所示的无向图，从顶点1开始进行广度优先遍历，可得到顶点访问
序列______。
A ．1，3，2，4，5，6，7
B ．1，2，4，3，5，6，7
C ．1，2，3，4，5，7，6
D ．2，5，1，4，7，3，6 21．一个无向连通图的生成树是含有该连通图的全部顶点的______。
A．极小连通子图B．极小子图
C．极大连通子图D．极大子图
22．设无向图G=(V, E) 和G’= (V’, E’)，如果G’为G的生成树，则下列说法中不正确的是______。
A．G’为G的连通分量B．G’为G的无环子图
C．G’为G的子图D．G’为G的极小连通子图且V’＝V 23.任意一个无向连通图______最小生成树。
A．只有一棵B．有一棵或多棵
C．一定有多棵D．可能不存在
24．对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个________。
A．由n-1条权值最小的边构成的子图。
B．由n-1条权值之和最小的边构成的子图。
C．由n-1条权值之和最小的边构成的连通子图。
D．由n个顶点构成的边的权值之和最小的生成树。
25．若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图_______。
A．是个有根有向图B．是个强连通图
C．含有多个入度为0的顶点D．含有顶点数目大于1的强连通分量26．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用____。
A．求关键路径的方法 B．求最短路径的Dijkstra算法
C．广度优先遍历算法 D．深度优先遍历算法
27．求最短路径的Dijkstra算法的时间复杂度为______。
A．O(n) B．O(n+e)
C．O(n2) D．O(ne)
28．求最短路径的Floyd算法的时间复杂度为______。
A．O(n) B．O(ne)
C．O(n2) D．O(n3)
29．关键路径是事件结点网络中______。
A．从源点到汇点的最长路径B．从源点到汇点的最短路径
C．最长的回路D．最短的回路
30．下面说法不正确的是______。
A．在AOE网中，减少任一关键活动的权值后，整个工期也就相应减少
B．AOE网工程工期为关键活动的权值和
C．在关键路径上的活动都是关键活动，而关键活动也必须在关键路径上D．A和B
31．下面说法不正确的是______。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，将使整个工程提前完成
C．所有关键活动都提前完成，则整个工程提前完成
D．某些关键活动若提前完成，将使整个工程提前完成
二、填空题
1．对于具有n个顶点的无向图G最多有_________条边。
2．对于具有n个顶点的强连通有向图G至少有_________条边。
3．对于具有n个顶点的有向图，每个顶点的度最大可达___________。
4．若无向图G的顶点度数最小值大于___________时，G至少有一条回路。5．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为___________，所有邻接表中的结点总数是__________。
6．已知一个有向图的邻接矩阵表示，删除所有从第i个结点出发的弧的方法是____________。
7．对于n个顶点的无向图，采用邻接矩阵表示，求图中边数的方法是__________，判断任意两个顶点i和j是否有边相连的方法是__________，求任意一个顶点的度的方法是___________。
8．对于n个顶点的有向图，采用邻接矩阵表示，求图中边数的方法是_________，判断任意两个顶点i和j是否有边相连的方法是__________，求任意一个顶点的度的方法是__________。
9．无向图的连通分量是指___________。
10．已知图G的邻接表如图7-3所示，从顶点v1出发的深度优先搜索序列为
________，从顶点1出发的广度优先搜索序列为_____________。
图7-3 图G的邻接表
11．n个顶点连通图的生成树一定有__________条边。
12．一个连通图的___________是一个极小连通子图。
13．Prim算法适用于求_________的网的最小生成树，Kruskal算法适用于求________的网的最小生成树。
14．在AOV图中，顶点表示________,有向边表示________。
15．可以进行拓扑排序的有向图一定是_________。
16．从源点到汇点长度最长的路径称为关键路径，该路径上的活动称为________。17．Dijkstra算法从源点到其它各顶点的路径长度按________次序依次产生，该算法在边上的权出现_________情况时，不能正确产生最短路径。
18．求从某源点到其余各项点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则在图的顶点数为40时，计算时间约为
_________ms。
三、判断题
1．具有n个顶点的无向图至多有n（n-1）条边。
2．有向图中各顶点的入度之和等于各顶点的出度之和。
3．邻接矩阵只储存了边的信息，没有存储顶点的信息。
4．对同一个有向图，只保存出边的邻接表中结点的数目总是和只保存入边的邻接表中结点的数目一样多。
5．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。
6．如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是有向完全图。
7．如果表示某个图的邻接矩阵不是对称矩阵，则该图一定是有向图。
8．连通分量是无向图的极小连通子图。
9．强连通分量是有向图的极大连通子图。
10．对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每一个顶点，则该图一定是完全图。
11．连通图的广度优先搜索中一般要采用队列来暂时刚访问过的顶点。
12．图的深度优先搜索中一般要采用栈来暂时刚访问过的顶点。
13．有向图的遍历不可采用广度优先搜索方法。
14．连通图的生成树包含了图中所有顶点。
15．设G为具有n个顶点的连通图，如果其中的某个子图有n个顶点，n-1条边，则该子图一定是G的生成树。
16．最小生成树是指边数最小的生成树。
17．从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。18．只要无向网中没有权值相同的边，其最小生成树就是惟一的。
19．只要无向网中有权值相同的边，其最小生成树就可能不是惟一的。
20．有环图也能进行拓扑排序。
21．拓扑排序算法仅适用于有向无环图。
22．任何有向无环图的结点都可以排成拓扑排序，而且拓扑序列不惟一。23．关键路径是由权值最大的边构成的。
24．在AOE网中，减小任一关键活动上的权值后，整个工期也就相应减小。25．在AOE网中工程工期为关键活动上权值之和。
26．在关键路径的活动都是关键活动，而关键活动未必在关键路径上。
27．关键活动不按期完成就会影响整个工程的完成时间。
28．所有关键活动都提前完成，则整个工程将提前完成。
29．某些关键活动若提前完成，将可能使整个工程提前完成。
30．求单源最短路径的狄克斯特拉算法不适用于有回路的有向网。
四、简答题
1．图G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？2．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是
否有关？
3．对于稠密图和稀疏图，就存储而言，采用邻接矩阵和邻接表哪个更好些？4．请回答下列关于图的一些问题：
（1）有n个顶点的有向强连通图最多有多少条边？最少有多少条边？
（2）表示一个有1000个顶点，1000条边的有向图的邻接矩阵有多少个矩阵元素？是否为稀疏矩阵？
（3）对于一个有向图，不用拓扑排序，如何判断图是否存在环？
5．对n个顶点的无向图和有向图，采用邻接表表示时，如何判别下列有关问题？（1）图中有多少条边？
（2）任意两个顶点i和j是否有边相连？
（3）任意一个顶点的度是多少？
6．给出如图7-4所示的无向图G的邻接矩阵和邻接表两种存储结构。并在给定的邻接表基础上，指出从顶点1出发的深度优先遍历和广度优先遍历序列。
图7-4 一个无向图
7．对于图7-5所示的有向图，试给出：
（1）邻接矩阵。（2）邻接表（3）强连通分量
（4）对照邻接表，给出从顶点1出发的深度优先遍历序列。
（5）对照邻接表，给出从顶点3出发的深度优先遍历序列。
图7-5 一个有向图
8．什么样的图其最小生成树是惟一的？
9．已知带权连通图G(V ,E)邻接表如图7-6所示，请画出该图，并分别以深度优
先和广度优先遍历该图，写出遍历中结点的序列，并画出该图的一棵最小生成树，其中表结点的3个域各为： 1. 2. 3 4. 5
图7-6 连通图的邻接表
10．已知世界6大城市为：北京（B ）纽约（N ）巴黎（P ）伦敦（L ）东京（T ）
墨西哥城（M ）试用由表1给出的交通网确定最小生成树，并说明所使用的方法及其时间复杂度。
11．对于图7-7所示的带权有向图，采用狄克斯特拉算法求从顶点1到其它顶点
的最短路径，要求给出求解过程。
图7-7 一个有向图图7-8一个有向图
12．设图7-8中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪个村庄能使个村庄总体交通代价最小。
13．表2所示给出了某工程各工序之间的优先关系和各工序所需的时间。
表2 某工程各工序关系表
工序代号A B C D E F G H I J K L M N 所需时间15 10 50 8 15 40 300 15 120 60 15 30 20 40 先驱工作- - A,B B C,D B E G,I E I F,I H,J,K L G 完成如下各小题：
（1）画出相应的AOE网
（2）列出事件的最早发生时间，最迟发生时间。
（3）找出关键路径并指明完成该工程所需的最短时间。
14．如图7-9所示的AOE网，求：
（1）每项活动a i最早开始时间e(a i)和最迟开始时间l(a i)。
（2）完成此工程最少需要多少天（设边上权值为天数）。
（3）哪些是关键活动
（4）是否存在某项活动，当其提高速度后能使整个工程缩短工期？
五、算法设计题
1．假设图G采用邻接表存储，分别设计实现以下要求的算法：（1）求出图G中每个顶点的入度。
（2）求出图G中每个顶点的出度
（3）求出图G中出度最大的一个顶点，输出该顶点的编号。
（4）计算图G中出度为0的顶点数。
（5）判断图G中是否存在边
2．假设图G采用邻接矩阵存储，分别设计实现以下要求的算法：（1）求出图G中每个顶点的入度。
（2）求出图G中每个顶点的出度
（3）求出图G中出度最大的一个顶点，输出该顶点的编号。
（4）计算图G中出度为0的顶点数。
（5）判断图G中是否存在边
3．设计一个将邻接表转换为邻接矩阵的算法。
4．一个连通图采用邻接表作为存储机构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。
5．设计一个算法，求不带权无向连通图G中距离顶点v的最远顶点。
6．设计一个算法，判断无向图G是否是一棵树，若是树，返回1；否则返回0。7．假设图采用邻接表存储，分别写出基于DFS和BPS遍历的算法来判别顶点i 和顶点j（i!=j）之间是否有路径。
8．假设图G采用邻接表存储，设计一个算法，判断无向图G是否连通，若连通则返回1；否则返回0。
9．假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的长度为1的所有简单路径。
10．假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。
11．假设图G采用邻接表存储，设计一个算法，从如图7-10所示的无向图G中找出满足如下条件的一条路径：
（1）给定起点vi和终点vj。
（2）给定一组必经点{7,9}，即输出的路径必须包含这些顶点。
（3）给定一组必避点{1,6}，即输出的路径不能包含这些顶点。
图7-10
12．假设图G采用邻接矩阵存储，采用遍历方法实际一个有向图的根的算法。
若有向图中存在一个顶点v，从v可以通过路径达达图中其它所有顶点，则称v为该有向图的根。
13．假设图G采用邻接矩阵存储，设计一个算法判断在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方法输出该回路（找到一条即可）。
14．采用堆排序来实现Kruskal算法，并说明时间复杂度O(elog2e)的理由。15．如图7-11是一个城市连接图，图中权值表示两城市之间的里程（单位为100km），现要设计一条铁路贯通所有城市（即从一个任一城市可以到达其他城市）。设计一个算法，求出最小代价。假设每1km的铁路造价为1000万元。
图7-11 城市连通图
16．利用狄克斯特拉算法，设计一个可产生从指定顶点出发的最小生成树的算法。17．设计一个算法求图的中心点。设v是有向图G的一个顶点，把v的偏心度定义为：MAX{从w到v的最短距离|wV(G)}如果v是有向图G中具有最小偏心度的顶点，则称顶点v是G的中心点。
18．假设图G采用邻接矩阵存储，采用弗洛伊德算法设计一个求有向图的根的算法。若有向图中存在一个顶点v，从v可以通过路径到达图中其他所有顶点，则称v为该有向图的根。
19．设计一个算法，判断有向图是否存在回路。
20．对于一个使用邻接表存储的带权有向图G。试利用深度优先搜索方法，对该图中所有顶点进行逆向拓扑排序。若邻接表的数据类型定义为AGraph，则算法的首部为：void dfs_topsort(AGraph *G) 若拓扑排序成功，表示图中不存在环；否则表示图中存在环。在这个算法中嵌套一个递归深度优先搜索算
法为：Dfs(AGaph G , int v)在遍历图的同时进行逆序拓扑排序，其中，v 是顶点编号。
（1）给出该图的邻接表定义
（2）定义在算法中使用的全局辅助数组
（3）写出逆向拓扑排序的算法。
21．假设AOE网以邻接表方式存储，设计一个算法求该AOE网的所有关键活动。
《数据结构》习题汇编07 第七章 图 试题
第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。
数据结构第七章图
数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题：
数据结构第7章 图习题
第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。
A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量
数据结构第七章图练习及答案
1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧
关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）
数据结构第七章图练习及答案
数据结构第七章图练习及答案 1( 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2(写出求以下AOE网的关键路径的过程。要求:给出每一个事件和每一个活动的最早开始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 (1)在AOV网中，选一个没有前驱的结点且输出;(2)删除该顶点和以它为尾的弧;(3)重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】(1)0132465 (2)0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 (1)求事件的最早发生时间ve(j), 最晚发生时间vl(j); (2)最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0); (3)计算e(i),l(i):设ai由弧
(4)找出e(i)-l(i)=0的活动既是关键活动。 【答案】 关键路径为:a0->a4->a6->a9 7.1 选择题 1(对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复 杂度为( B ) A) O(n) B) O(n+e) C) O(n*n) D) O(n*n*n) 2(设无向图的顶点个数为n，则该图最多有( B )条边。 A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)n2 3(连通分量指的是( B ) A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 4(n个结点的完全有向图含有边的数目( D ) A)n*n B)n(n+1) C)n/2 D)n*(n-1) 5(关键路径是( A ) A) AOE网中从源点到汇点的最长路径
数据结构第7章 图习题
习题7 图 单项选择题 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
数据结构第七章图练习及答案
一、选择题 1、有6个结点的有向完全图有（）条弧。 A、36 B、28 C、30 D、15 2、用邻接表表示图进行广度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 3、用邻接表表示图进行深度优先遍历时，通常采用（）来实现算法。 A、栈 B、队列 C、树 D、图 4、任何一个无向连通图的最小生成树（） A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在5、在一个图中，所有顶点的度数之和等于所有边数和的（）倍。 A、B、1C、2D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、B、1C、2D、4 7、一个有n个顶点的无向图最多有（）条边。 A、n B、n(n-1) C、n(n-1)/2 D、2n 8、具有5个顶点的无向完全图有（）条边。 A、6 B、8 C、10 D、20 9、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 A、n B、n+1 C、n-1 D、n/2 10、对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A、(n+1)*(n-1)B、(n-1)*(n-1)C、n D、n*n
11、对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），所有邻接表中的结点总数是（） (1)A、n B、n+1C、n-1D、n+e (2)A、e/2B、e C、2eD、n+e 12、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 13、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（） A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历 14、判定一个有向图是否存在回路，除了利用拓扑排序方法外，还可以利用（）A、求关键路径的方法B、求最短路径的方法 C、宽度优先遍历算法 D、深度优先遍历算法 15、关键路径是AOE网中的（） A、从源点到汇点的最长路径 B、从源点到汇点的最短路径 C、最短的回路 D、活动的最早开始时间与最迟发生时间相等 二、填空题 1、有向图G用邻接矩阵存储，则其第i行的所有元素之和等于顶点i的（出度）。 2、设有一稀罕图G，则G采用（邻接表）存储较省空间。 3、设有一粘稠图G，则G采用（邻接矩阵）存储较省空间。 4、图的邻接表存储结构只适用于（）图。 5、已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的边的方法是（访问矩阵第I行）。
数据结构第7章 图习题
习题7 图 7.1 单项选择题 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 C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点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 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。