客观题测试-第6章图

第1关：图-客观题测试 （一）

1、无向图中一个顶点的度是指图中（）。

A、通过该顶点的简单路径数

B、与该顶点相邻接的顶点数

C、与该顶点连通的顶点数

D、通过该顶点的回路数

2、以下说法正确的是（）。

A、连通分量是无向图中的极小连通子图

B、强连通分量是有向图中的极大强连通子图

C、在一个有向图的拓扑序列中若顶点a在顶点b之前，则图中必有一条弧

D、对有向图G，如果以任一顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图

解：对于D，完全图是指任何两个顶点之间都存在一条边的图。而在你描述的情况下，虽然从任意一个顶点出发可以访问到图中的所有顶点，但是这并不意味着图中所有的顶点之间都有边相连。

因此，即使从任意一个顶点出发可以访问到所有顶点，但该图仍然可能是非完全图。要判断一个图是否是完全图，需要检查图中任意两个顶点之间是否存在一条边

3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A、1/2

B、1

C、2

D、4

4、在一个无向图中，所有顶点的度数之和等于所有边数（）倍。

A、1/2

B、1

C、2

D、4

5、一个具有n个顶点的有向图最多有（）条边。

A、n (n-1)/2

B、n(n-1)

C、n(n+1)/2

D、

 

6、设无向图的顶点个数为n，则该图最多有（）条边。

A、n-1

B、n(n-1)/2

C、n(n+1)/2

D、

 

7、一个n个顶点的连通无向图，其边的个数至少为（）。

A、n-1

B、n

C、n+1

D、nlog n

8、已知无向图G含有16条边，其中度为4的顶点个数为3，度为3的顶点个数为4，其他顶点的度均小于3.图G所含的顶点个数至少是（）。

A、10

B、11

C、13

D、15

解：16条边，有32个度，32 = 4 * 3 + 3 * 4 + n2 * 2 + n1* 1 + n0，最少，让n2

最多，为4，4 + 4 + 3 = 11

9、下列关于邻接矩阵表示法的优缺点，不正确的是（）。

A、便于判断两个顶点之间是否有边

B、便于计算各个顶点的度

C、不便于增加和删除顶点

D、便于统计边的数目 

解：c会影响矩阵大小，d要知道是有向图还是无向图

10、用邻接表存储图所用的空间大小（）。

A、与图的顶点数和边数都有关

B、只与图的边数有关

C、只与图的顶点数有关

D、与边数的平方有关

解：有向图：n+e，无向图：n+2e

第2关：图-客观题测试 （二）

1、对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（）。

A、n

B、

C、n-1

D、(n-1)^2

2、无向图的邻接矩阵是一个（）。

A、对称矩阵

B、零矩阵

C、上三角矩阵

D、对角矩阵

3、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A、第i行非无穷的元素之和

B、第i列非无穷的元素个数之和

C、第i行非无穷且非0的元素个数

D、第i行与第i列非无穷且非0的元素之和

4、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。

A、将邻接矩阵的第i行删除

B、将邻接矩阵的第i行元素全部置为0

C、将邻接矩阵的第i列删除

D、将邻接矩阵的第i列元素全部置为0

5、若邻接表中有奇数个表结点，则一定（）。

A、图中有奇数个顶点

B、图中有偶数个顶点

C、图为无向图

D、图为有向图

6、假设无向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（）。

A、n

B、e

C、2e

D、n*e

7、下列关于图遍历的说法不正确的是（）。

A、连通图的深度优先搜索是一个递归过程

B、图的广度优先搜索中邻接点的寻找具有“先进先出”的特征

C、非连通图不能用深度优先搜索法

D、图的遍历要求每一顶点仅被访问一次

解：

[1]连通图
任意两个顶点都有路径相通的无向图。
[2]深度优先搜索
从图中某一指定顶点v出发,先访问v,接着选择一个与顶点v相邻且没有访问过的顶点w,再从w出发采用同样的方式访问w的未被访问过的相邻点,直到图中与顶点v相连的所有顶点都被访问为止。
[3]图的遍历
从图中某一顶点出发，按某种方式访问图中所有顶点，使每一顶点仅被访问一次。

8、图的DFS生成树的树高比BFS生成树的树高（）。

A、小

B、相等

C、大或相等

D、小或相等

9、采用邻接表存储的图，其深度优先遍历类似于二叉树的（）。

A、中序遍历

B、先序遍历

C、后序遍历

D、按层次遍历

10、

采用邻接矩阵表示图的深度优先搜索遍历，

下列代码补充完整应选择（） 。

A、

B、

C、

D、

第3关：图-客观题测试 （三） 

1、用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。

A、栈

B、队列

C、树

D、图

解：深度优先用栈（回溯，后进先出），广度优先用队列

2、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。

A、完全图

B、连通图

C、有回路

D、一棵树

3、已知一个有向图的邻接表存储结构如图所示，

根据深度优先遍历算法，从顶点v0出发，所得到的顶点序列是（）。

A、v0,v2,v3,v1

B、v0,v1,v3,v2

C、v0,v1,v2,v3

D、v0,v2,v1,v2

4、对有n个节点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。

A、O(n)

B、O(e)

C、O(n+e)

D、O(n*e)

5、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）。

A、先序遍历

B、中序遍历

C、后序遍历

D、按层次遍历

6、用邻接表表示图进行广度优先遍历时，通常是采用 （）来实现算法的。

A、栈

B、队列

C、树

D、图

7、用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树（）。

A、相同

B、不相同

C、可能相同，可能不相同

D、无法比较

8、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（）。

A、O(n)

B、O(n+e)

C、

D、

 

9、

对于下列的网，

使用Prim算法由顶点A出发，求最小生成树，吸取的第三条边是（）。

A、（A，D）

B、（D，E）

C、（C，E）

D、（B，C）

10、以下叙述中，正确的是（）。

A、最小生成树的代价不唯一。

B、从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。

C、只要无向连通图中没有权值相同的边，则其最小生成树唯一。

D、设连通图G含有n个顶点，则含有n个顶点、n-1条边的子图一定是G的生成树。

 解：选项a，最小生成树的代价是唯一的，因为最小生成树是所有生成树中权值最小的。但是，最小生成树的树形并不唯一，因为可能存在多条权值相同的边。

第4关：图-客观题测试 （四）

1、已知无向图G如下所示，

使用克鲁斯卡尔算法求G的最小生成树，加入到最小生成树中的第三条边是（）。

A、(c, e)

B、(b, e)

C、(a, e)

D、（b,f）

解：不能闭环

2、(1).求从指定源点到其余各顶点的迪杰斯特拉（Dijkstra）最短路径算法中弧上权不能为负的原因是在实际应用中无意义；(2). 利用Dijkstra求每一对不同顶点之间的最短路径的算法时间是

；（图用邻接矩阵表示）；(3). Floyd求每对不同顶点对的算法中允许弧上的权为负，但不能有权和为负的回路。上面不正确的是（）。

A、(1),(2),(3)

B、(1)

C、(1),(3)

D、(2),(3)

解：在迪杰斯特拉算法中，弧上权不能为负的原因是为了保证算法的正确性。如果弧上权可以为负，那么在某些情况下，根据负权重的边的选择可能会导致找到的路径不是最短的。例如，如果存在一条从A到B的路，其权值为-10，而另一条从A到C的路，其权值为3，那么算法可能会优先选择从A到B的路，因为它的权值更小。但是，实际上，从A到C的路才是最短的路径。
因此，为了保证迪杰斯特拉算法的正确性，我们通常要求弧上的权值不能为负。如果在实际应用中确实存在负权重的边，那么可以考虑使用其他算法，如贝尔曼-福特（Bellman-Ford）算法或弗洛伊德-沃沙尔（Floyd-Warshall）算法等。6                                                                                                 

3、使用迪杰斯特拉（Dijkstra）算法求下图

中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（）。

A、5，2，3，4，6

B、5，2，3，6，4

C、5，2，4，3，6

D、5，2，6，3，4

4、求解最短路径的Floyd算法的时间复杂度为（）。

A、O（n）

B、O（n+c）

C、O（n+2c）

D、

 

5、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。

A、G中有弧，Vj＞

B、G中有一条从Vi到Vj的路径

C、G中没有弧Vi,Vj＞

D、G中有一条从Vj到Vi的路径

解：拓扑序列为有向无环图 

6、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，

,G的拓扑序列是（）。

A、

B、

C、

D、

 

 

7、下列选项中，

不是如下有向图的拓扑序列的是（）。

A、1，5，2，3，6，4

B、5，1，2，6，3，4

C、5，1，2，3，6，4

D、5，2，1，6，3，4

8、下面（）可以判断出一个有向图中是否有环（回路）。

A、广度优先遍历

B、拓扑排序

C、求最短路径

D、求关键路径

9、若使用AOE网估算工程进度，则下列叙述中正确的是（）。

A、关键路径是从原点到汇点边数最多的一条路径

B、关键路径是从原点到汇点路径长度最长的路径

C、增加任一关键活动的时间不会延长工程的工期

D、缩短任一关键活动的时间将会缩短工程的工期

10、

下图

所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是（）。

A、3和7

B、12和12

C、12和14                                                                                                          

D、15和15

第5关：图-客观题测试 （五）

1、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。

A、对

B、错

2、有e条边的无向图，在邻接表中有e个结点。

A、对

B、错

解：无向图一条边一条边对应两个结点 

3、邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。

A、对

B、错

解：邻接矩阵确实可以用于存储带权的有向图和无向图。对于带权图，邻接矩阵中的每个元素表示两个节点之间的边的权值。对于有向图，邻接矩阵的第i行第j列的元素表示从节点i到节点j的边的权值；对于无向图，邻接矩阵的第i行第j列的元素表示从节点i到节点j以及从节点j到节点i的边的权值之和。因此，邻接矩阵可以用于存储带权的有向图和无向图。 

4、一个有向图的邻接表和逆邻接表中结点的个数一定相等。

A、对

B、错

5、连通图上各边权值均不相同，则该图的最小生成树是唯一的。

A、对

B、错

6、在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。

A、对

B、错

解：

7、图的深度优先搜索序列和广度优先搜索序列不是惟一的。

A、对

B、错

8、关键路径是AOE网中从源点到终点的最短路径。

A、对

B、错

9、在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。

A、对

B、错

10、需要借助于一个队列来实现DFS算法。

A、对

B、错

解：栈 

第6关：图-客观题测试 （六） 

1、稠密图G采用邻接表存储较省空间。

A、对

B、错

2、若要求一个稠密图G的最小生成树，最好用克鲁斯卡尔算法来求解。

A、对

B、错

解：Prime，稀疏图 用克鲁斯卡尔

3、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。

A、对

B、错

4、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。

A、对

B、错

5、普里姆算法又称为“加点法”

A、对

B、错

6、有向图能进行拓扑排序。

A、对

B、错

解：有向无环图 

7、一个图的广度优先搜索树是惟一的。

A、对

B、错

8、构成最小生成树的边的权值都是最小的。

A、对

B、错

9、迪杰斯特拉算法的主循环共进行n 次，每次执行的时间是O(n)，所以算法的时间复杂度是O(n)。

A、对

B、错

10、不同的最小生成树算法最后得到的生成树不一定相同的.

A、对

B、错