第七章：图练习题
- 格式：pdf
- 大小：172.13 KB
- 文档页数：13
第七章：图练习题
第七章：图练习题
⼀、选择题1、⼀个有n个顶点的⽆向图最多有（）条边。
A、n
B、n(n-1)
C、n(n-1)/2
D、2n
2、具有6个顶点的⽆向图⾄少有（）条边才能保证是⼀个连通图。
A、5
B、6
C、7
D、8
3、具有n个顶点且每⼀对不同的顶点之间都有⼀条边的图被称为（）。
A、线性图
B、⽆向完全图
C、⽆向图
D、简单图
4、具有4个顶点的⽆向完全图有（）条边。
A、6
B、12
C、16
D、20
5、G是⼀个⾮连通⽆向图，共有28条边，则该图⾄少有（）个顶点
A、6
B、7
C、8
D、9
6、存储稀疏图的数据结构常⽤的是（）。
A、邻接矩阵
B、三元组
C、邻接表
D、⼗字链表
7、对⼀个具有n个顶点的图，采⽤邻接矩阵表⽰则该矩阵的⼤⼩为（）。
A、nB、(n-1)2
C、(n+1)2
D、n2
8、设连通图G的顶点数为n，则G的⽣成树的边数为（）。
A、n-1
B、n
C、2n
D、2n-1
9、n个顶点的⽆向图的邻接表中结点总数最多有（）个。
A、2n
B、n
C、n/2
D、n(n-1)
10、对于⼀个具有n个顶点和e条边的⽆向图，若采⽤邻接表表⽰，则表向量的⼤⼩为
（），所有顶点邻接表的结点总数为（）。A、n
B、n+1
C、n-1
D、2n
E、e/2
F、e
G、2e
H、n+e
11、在有向图的邻接表存储结构中，顶点v在表结点中出现的次数是（）。
A、顶点v的度
B、顶点v的出度
C、顶点v 的⼊度
D、依附于顶点v的边数
12、已知⼀个图，若从顶点a出发进⾏深度和⼴度优先搜索遍历，则可能得到的顶点序列分别为（）和（）
（1）A、abecdf B、acfebd C、acebfd D、acfdeb
（2）A、abcedf B、abcefd C、abedfc D、acfdeb
13、采⽤邻接表存储的图的深度和⼴度优先搜索遍历算法类似于⼆叉树的（）和（）。
A、中序遍历
B、先序遍历C、后序遍历
D、层次遍历
14、已知⼀有向图的邻接表存储结构如下图所⽰，分别根据图的深度和⼴度优先搜索遍历算法，从顶点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
15、已知有8个顶点为A，B，C，D，E，F，G，H的⽆向图，其邻接矩阵存储结构如下，由
E、A BEHFGDC
F、A BEHGFCD
16、已知⼀个图如下，在该图的最⼩⽣成树中各边上权值之和为（），在该图的最⼩⽣成树中，从v1到v6的路径为（）。
A、31
B、38
C、36
D、43
E、v1,v3,v6
F、v1,v4,v6
G、v1,v5,v4,v6
H、v1,v4,v3,v6
17、关键路径是事件结点⽹络中的（）。
A、从源点到汇点的最长路径
B、从源点到汇点的最短路径
C、最长的回路
D、最短的回路
18、正确的AOE⽹必须是（），AOE⽹中某边权值应当是（），权值为0的边表⽰（）。
（1）A、完全图 B、哈密尔顿图 C、⽆环图 D、强连通图
（2）A、实数 B、正整数 C、正数 D、⾮负数
（3）A、为决策⽽增加的活动 B、为计算⽅便⽽增加的活动 C、表⽰活动间的时间顺序关系 D、该活动为关键活动19、已知⼀个图如下，则由该图得到的⼀种拓扑序列为（）。
A、v1,v4,v6,v2,v5,v3
B、v1,v2,v3,v4,v5,v6
C、v1,v4,v2,v3,v6,v5D、v1,v2,v4,v6,v3,v5
20、下⾯结论中正确的是（）
A、在⽆向图中，边的条数是顶点度数之和。
B、在图结构中，顶点可以没有任何前驱和后继。
C、在n个顶点的⽆向图中，若边数⼤于n-1，则该图必定是连通图
D、图的邻接矩阵必定是对称矩阵。
21、下⾯结论中正确的是（）
A、若有向图的邻接矩阵中对⾓线以下元素均为0，则该图的拓扑排序序列必定存在。
B、⽹络的最⼩代价⽣成树是唯⼀的。
C、在拓扑排序序列中，任意两个相继顶点vi和vj都存在从vi到vj的路径。
D、在有向图中，从⼀个顶点到另⼀个顶点的最短路径是唯⼀的。
22、下⾯结论不正确的是（）。
A、⽆向图的连通分量是该图的极⼤连通⼦图。
B、有向图⽤邻接矩阵表⽰容易实现求顶点度数的操作。
C、⽆向图⽤邻接矩阵表⽰，图中的边数等于邻接矩阵元素之和的⼀半。
D、有向图的邻接矩阵必定不是对称矩阵。
23、下⾯结论中正确的是（）。
A、按深度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。
B、⼀个图按深度优先搜索遍历的结果是唯⼀的。
C、若有向图G中包含⼀个环，则G的顶点间不存在拓扑排序。
D、图的拓扑排序序列是唯⼀的。
24、下⾯结论中不正确的是（）。
A、按⼴度优先搜索遍历图时，与始点相邻的顶点先于不与始点相邻的顶点访问。
B、⼀个图按⼴度优先搜索遍历的结果是唯⼀的。
C、⽆向图的邻接表表⽰法中，表中结点的数⽬是图中边的条数的2倍。
D、图的多重邻接表表⽰法中，表中结点数⽬是图中边的条数。
⼆、填空题1、n个顶点的连通图⾄少有（）条边。
2、⼀个⽆向图有n个顶点和e条边，则所有顶点的度数之和为（）。
3、在图形结构中，每个结点的前驱结点和后继结点可以有（）。
4、若⽆向图G的顶点度数的最⼩值⼤于或等于（）时，G⾄少有⼀条回路。
5、设⽆向图G的顶点数为n，图G最少有（）边，最多有（）条边。若G为有向图，有n个顶点，则图G最少有（）条边，最多有（）条边。具有n个顶点的⽆向完全图，边的总数为（）条，⽽有n个顶点的有向完全图，边的总数为（）条。6、在⽆权图G的邻接矩阵A中，若(vi,vj)或属于G的边/弧的集合，则对应元素A[i][j]等于（），否则等于（）。
7、在⽆向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（）。8、已知⼀个图的邻接矩阵表⽰，计算第I个顶点的⼊度⽅法为（）
9、在⼀个图G的邻接表表⽰中，每个顶点的邻接表中所含的结点数，对于有向图⽽⾔等于该顶点的（），⽽对于⽆向图⽽⾔等于该顶点的（）。10、已知图G的邻接表如下，从顶点v1出发的深度优先搜索遍历序列为（），⼴度优先序列为（）。
11、n个顶点的弱连通有向图G最多有（）条弧，最少有（）条弧。
12、在n个顶点e条边的连通图中，连通分量个数为（）。
13、任何（）的有向图，其所有结点都可以排在⼀个拓扑序列中，拓扑排序的⽅法是先从图中选⼀个（）为0的结点且输出，然后从图中删除该结点及其（），反复执⾏，直到所有结点都输出为⽌。14、⼀个连通图的（）是⼀个极⼩连通⼦图。
15、在A OE⽹中，从源点到汇点各活动时间总和最长的路径为（）。
三、简答题1、对于⼀个具有n个顶点的连通⽆向图，如果它有且只有⼀个简单回路，此图有⼏条
边？⼀个具有n个顶点的弱连通图⾄少有⼏条边？2、已知某图的邻接表，如何建⽴该图的邻接矩阵？
3、有4个顶点A，B，C，D的⽆向连通图，按⼴度和深度搜索遍历结果都为ABCD，画
出所有可能的结构图？4、简述⽆向图和有向图有哪⼏种存储结构，并说明各种结构在图的不同操作中有什么优
越性？5、什么是A OE⽹的关键路径？
6、给出下图邻接矩阵、邻接表和邻接多重表存储结构。从顶点1出发进⾏⼴度个深度优先搜索遍历。
7、对下图，请给出（1）对应的邻接矩阵，并给出v1,v2,v3三个顶点的出度和⼊度；
（2）邻接表和逆邻接表表⽰；（3）强连通分量。
8、试列出图中全部可能的拓扑排序序列。答案：
三、简答题1、（1）n条边（2）n-1条边
2、根据邻接表中表向量的⼤⼩确定邻接矩阵的⾏列数；由第I个顶点指向的单链表中结点
j来确定邻接矩阵中第I⾏j列元素为1，其余为0。
3、略4、图的存储结构有邻接矩阵、邻接表、⼗字链表和邻接多重表。
借助于邻接矩阵容易判断任意两个顶点是否有边/弧相连，并容易求出顶点的度。对⽆向图，顶点vi的度是邻接矩阵中第I⾏或第j列的元素之和；对有向图，第I⾏的元素之和为顶点vi的出度，第j列的元素之和为顶点vj的⼊度。
在⽆向图的邻接表中，第I个链表中表结点个数恰好为顶点vi的度；⽽在有向图中，第I个链表中表结点个数只是顶点vi的出度。
利⽤⼗字链表容易求得顶点的出度和⼊度。
邻接多重表适合于对边进⾏操作，如在遍历时对边作记号或在拓扑排序中对边进⾏删除。5、在A OE⽹中完成⼯程的最短时间是从开始点到完成点的最长路径的长度，这条路径长度最长的路径叫关键路径。
第九章：查找复习题
⼀、选择题1、顺序查找⼀个共有n个元素的线性表，其时间复杂度为（），折半查找⼀个具有n个元素的有序表，其时间复杂度为（）。
A、O(n)
B、O(log2n)
C、O(n2)
D、O(nlog2n)
2、在对长度为n的顺序存储的有序表进⾏折半查找，对应的折半查找判定树的⾼度为（）。
A、n
B、[log2n]
C、[log2(n+1)]
D、「log2(n+1)
3、采⽤顺序查找⽅式查找长度为n的线性表时，平均查找长度为（）
A、n
B、n/2
C、(n+1)/2
D、(n-1)/2
4、采⽤折半查找⽅法检索长度为n的有序表，检索每个元素的平均⽐较次数（）对应判定树的⾼度（设⾼度⼤于等于2）。
A、⼩于
B、⼤于
C、等于
D、⼤于等于
5、已知有序表（13，18，24，35，47，50，62，83，90，115，134），当折半查找值为90的元素时，查找成功的⽐较次数为（）。A、1
B、2
C、3
D、4
6、对线性表进⾏折半查找时，要求线性表必须（）。
