第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）是否存在某项活动，当其提高速度后能使整个工程缩短工期
图7-9
五、算法设计题
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网的所有关键活动。
7.1 选择题 1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为() A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n) 【答案】B 2. 设无向图的顶点个数为n,则该图最多有()条边。 A) n-1B)n(n-1)/2C)n(n+1)/2 【答案】B 3. 连通分量指的是() A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 【答案】B 4. n 个结点的完全有向图含有边的数目() A) n*n B) n(n+1) C) n/2 【答案】D 5. 关键路径是() A) AOE网中从源点到汇点的最长路径 B) AOE网中从源点到汇点的最短路径 C) AOV网中从源点到汇点的最长路径D) n2
D) n* (n-1) D) AOV网中从源点到汇点的最短路径 【答案】 A 6．有向图中一个顶点的度是该顶点的() A)入度B)出度C)入度与出度之和D)(入度+出度)12 【答案】C 7．有e 条边的无向图，若用邻接表存储，表中有()边结点。 A) e B) 2eC) e-1D) 2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】 A 10．存储无向图的邻接矩阵一定是一个() A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的()倍 A) B) 1C) 2D) 4 答案】B 12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为(
、单项选择题 1．在一个无向图 G 中，所有顶点的度数之和等于所有边数之和的 _________ 倍 A ．l/2 B ．1 D ．4 2．在一个有向图中， 所有顶点的入度之和等于所有顶点的出度之和的 ________倍 A ．l/2 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> 点邻接表中的结点总数为_________ 。 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. 下列说法中不正确的是 第7章 《图》习题参考答案 一、单选题（每题1分，共16分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A ．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。 A ．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。 A ．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。 A ．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。 A ．栈 B. 队列 C. 树 D. 图 （ ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是 （ D ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是 A ． 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 2 34 6 5 （ D ）10. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是 （ A ）11. 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是 A ．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 ??? ? ?? ? ? ? ? ? ???????????0100011101100001011010110011001000110010011011110A ．0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3 习题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 图一个无向图 11．已知一有向图的邻接表存储结构如图所示。 一、选择题 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、1/2 B、1 C、2 D、4 6、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A、1/2 B、1 C、2 D、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+1 C、n-1 D、n+e (2)A、e/2 B、e C、2e D、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 行）。 6、图的深度优先遍历序列（不是）唯一的。 7、n个顶点e条边的图，若用邻接表存储，深度优先遍历算法的时间复杂度为（n+e）。 第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．连通图的深度优先搜索是一个递归过程 第七章图习题 1 单项选择题 1、图中有关路径的定义是（）。 A、由顶点和相邻顶点序偶构成的边所形成的序列 B、由不同顶点所形成的序列 C、由不同边所形成的序列 D、上述定义都不对 2、设无向图的顶点个数为n，则该图最多有（）条边。 A、n– 1 B、n (n– 1)/2 C、n (n+1)/2 D、n2 3、一个n个顶点的连通无向图，其边的个数至少为（）。 A、n– 1 B、n C、n+1 D、n log n 4、下面结构中最适于表示稀疏无向图的是（）。 A、邻接矩阵 B、逆邻接表 C、邻接多重表 D、十字链表 5、下列哪一种图的邻接矩阵是对称矩阵？（） A、有向图 B、无向图 C、AOV网 D、AOE网 6、当一个有N个顶点的图用邻接矩阵A表示时，顶点V i的度是（）。 A、第j列所有元素之和 B、第i行所有元素之和 C、不确定 D、第j列所有元素之和+第i行所有元素之和 7、下面哪一方法可以判断出一个有向图是否有环（回路）（）。 A、深度优先遍历 B、拓扑排序 C、求最短路径 D、求关键路径 8、在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。 A、O(n) B、O(n+e) C、O(n2) D、O(n3) 9、求解最短路径的Floyd算法的时间复杂度为( )。 A、O(n) B、O(n+e) C、O(n2) D、O(n3) 10、已知有向图G=(V, E)，其中V={v1, v2, v3, v4, v5, v6, v7}，E={ 习题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所示。 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（） A）O(n)B）O(n+e)C）O(n*n)D）O(n*n*n) 【答案】B 2．设无向图的顶点个数为n，则该图最多有（）条边。 A）n-1B）n(n-1)/2C）n(n+1)/2 【答案】B 3．连通分量指的是（） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 【答案】B 4．n个结点的完全有向图含有边的数目（） A）n*n B）n（n+1）C）n/2 【答案】D 5．关键路径是（） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径D）n2 D）n*（n-1） D）AOV网中从源点到汇点的最短路径 【答案】A 6．有向图中一个顶点的度是该顶点的（） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 【答案】C 7．有e条边的无向图，若用邻接表存储，表中有（）边结点。A）e B）2eC）e-1D）2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为（） A）栈B）队列C）二叉树D）树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为（）A）栈B）队列C）二叉树D）树 【答案】A 10．存储无向图的邻接矩阵一定是一个（） A）上三角矩阵B）稀疏矩阵C）对称矩阵D）对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的（）倍A）B）1C）2D）4 【答案】B 第七章图 一、选择题 1、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。 A. n B. n2 C. n-1 D. (n-1)2 2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。 A. 完全图 B. 连通图 C. 有回路 D. 一棵树 3、关键路径是事件结点网络中（）。 A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 4、下面（）可以判断出一个有向图中是否有环（回路）。 A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 5、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。 A. 第i行非无穷的元素之和 B. 第i列非无穷的元素个数之和 C. 第i行非无穷且非0的元素个数 D. 第i行与第i列非无穷且非0的元素之和 6、采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。 A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 7、无向图的邻接矩阵是一个（）。 A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵 8、当利用大小为N的数组存储循环队列时，该队列的最大长度是（）。 A. N-2 B. N-1 C. N D. N+1 9、邻接表是图的一种（）。 A. 顺序存储结构 B.链式存储结构 C. 索引存储结构 D. 散列存储结构 10、下面有向图所示的拓扑排序的结果序列是（）。 A. 125634 B. 516234 C. 123456 D. 521643 11、在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 12、在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点。 习题七图 一、单项选择题 1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（） A．G’为G的子图 B．G’为G的连通分量 C．G’为G的极小连通子图且V’=V D．G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树（） A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 3．以下说法正确的是（） A．连通分量是无向图中的极小连通子图。 B．强连通分量是有向图中的极大强连通子图。 C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧数据结构 第7章习题答案
数据结构第7章图习题
数据结构第七章图练习及答案
数据结构第7章图习题
数据结构第7章图习题
数据结构第7章 图习题
数据结构章节练习题 - 答案第7章 图
数据结构第07章 图习题
第七章图习题_数据结构
相关主题
文本预览