数据结构（图）的相关练习（四）附加答案_一个图的邻接矩阵中非0非∞的元素个数为奇数,则该图可能是

 

 

 

1.在一个无向图中，所有顶点的度之和等于边数的______ 倍。           

        A、1/2  

        B、1      

        C、2      

        D、4

答案：C

2.一个有n个顶点的无向图最多有______ 条边。          

        A、n     

        B、n(n-1)     

        C、n(n-1)/2  

        D、2n

答案：C

3.一个有n个顶点的有向图最多有______ 条边。          

        A、n     

        B、n(n-1)     

        C、n(n-1)/2  

        D、2n

答案：B

4.在一个具有n个顶点的无向连通图中至少有______ 条边。       

        A、n     

        B、n+l  

        C、n-1  

         D、n/2

答案：C

5.在一个具有n个顶点的有向图中，构成强连通图时至少有______ 条边。       

        A、n     

        B、n+l  

        C、n-1  

        D、n/2

答案：A

6.一个有n个顶点的无向图，其中边数大于n-1，则该图必是______。            

        A、完全图    

        B、连通图    

        C、非连通图

        D、以上都不对

答案：B

7.一个具有n（n≥1）个顶点的图，最多有    个连通分量。           

        A、0      

        B、1      

        C、n-1  

        D、n

答案：D

8.一个具有n（n≥1）个顶点的有向图，其强连通分量个数最少有______ 个。             

        A、0      

        B、1      

        C、n-1  

        D、n

答案：B

9.一个图的邻接矩阵是对称矩阵，则该图一定是______。            

        A、无向图    

        B、有向图    

        C、无向图或有向图    

        D、以上都不对

答案：C

10.一个图的邻接矩阵不是对称矩阵，则该图可能是______。       

        A、无向图    

        B、有向图    

        C、无向图或有向图    

        D、以上都不对

答案：B

11.一个图的邻接矩阵中非0非∞的元素个数为奇数，则该图可能是______。             

        A、有向图    

        B、无向图    

        C、无向图或有向图    

        D、以上都不对

答案：A

12.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是______。

        A、n     

        B、(n-1)2     

        C、n-1  

        D、n2

答案：D

13.对于一个具有n个顶点e条边的不带权无向图，若采用邻接矩阵表示，其中非零元素个数是______。           

        A、n     

        B、2n    

        C、e      

        D、2e

答案：D

14.用邻接表存储图所用的空间大小______。          

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

        B、只与图的边数有关 

        C、只与图的顶点数有关    

        D、与边数的平方有关

答案：A

15.在有向图的邻接表表示中，顶点v的边单链表中结点个数等于______。       

        A、顶点v的度    

        B、顶点v的出度 

        C、顶点v的入度 

        D、依附于顶点v的边数

答案：B

16.在有向图的邻接表表示中，顶点v在边单链表中出现的次数是______。       

        A、顶点v的度    

        B、顶点v的出度 

        C、顶点v的入度 

        D、依附于顶点v的边数

答案：C

17.如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点，则该图一定是______。        

        A、完全图    

        B、连通图    

        C、有回路    

        D、一棵树

答案：B

18.以下叙述中错误的是______。       

        A、图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次

        B、图的深度优先遍历适合无向图    

        C、图的深度优先遍历不适合有向图

        D、图的深度优先遍历是一个递归过程

答案：C

19.无向图G=(V，E)，其中V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，下面对该图进行深度优先遍历得到的顶点序列正确的是_____。

        

        A、 a，b，e，c，d，f                             

        B、 a，c，f，e，b，d      

        C、a，e，b，c，f，d                              

        D、a，e，d，f，c，b

答案：D

19.n个顶点的连通图的生成树有______ 条边。             

        A、n     

        B、n-1  

        C、n+1 

        D、不确定

答案：B

21.对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个______。             

        A、由n-1条权值最小的边构成的子图    

        B、由n-l条权值之和最小的边构成的子图     

        C、由n个顶点构成的极大连通子图

        D、由n个顶点构成的极小连通子图，且边的权值之和最小

答案：D

22.用Prim算法求一个连通的带权图的最小生成树，在算法执行的某时刻，已选取的顶点集合U＝{1，2，3}，已选取的边的集合TE＝{(1，2)，(2，3)}，要选取下一条权值最小的边，应当从______ 组边中选取。          

        A、{(1，4)，(3，4)，(3，5)，(2，5)}

        B、{(4，5)，(1，3)，(3，5)}      

        C、{(1，2)，(2，3)，(3，5)}      

        D、{(3，4)，(3，5)，(4，5)，(1，4)}

答案：A

23.用Prim算法求一个连通的带权图的最小生成树，在算法执行的某时刻，已选取的顶点集合U＝{1，2，3}，边的集合TE＝{(1，2)，(2，3)}，要选取下一条权值最小的边，不可能从______ 组中选取。      

        A、{(1，4)，(3，4)，(3，5)，(2，5)}

        B、{(1，5)，(2，4)，(3，5)}      

        C、{(1，2)，(2，3)，(3，1)}      

        D、{(1，4)，(3，5)，(2，5)，(3，4)}

答案：C

24.用Kruskal算法求一个连通的带权图的最小生成树，在算法执行的某时刻，已选取的边集合TE＝{(1，2)，(2，3)，(3，5)}，要选取下一条权值最小的边，不可能选取的边是______。

        A、(1，3)   

        B、(2，4)     

        C、(3，6)     

        D、(1，4)

答案：A

25.对某个带权连通图构造最小生成树，以下说法中正确的是______。

Ⅰ.该图的所有最小生成树的总代价一定是唯一的

Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ.用普里姆（Prim）算法从不同顶点开始构造的所有最小生成树一定相同

Ⅳ.使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同          

        A、仅Ⅰ

        B、仅Ⅱ 

        C、仅Ⅰ、Ⅲ

        D、仅Ⅱ、Ⅳ

答案：A

26.n个顶点e条边的带权有向图采用邻接矩阵存储，求最短路径的Dijkstra算法的时间复杂度为______。           

        A、O(n) 

        B、O(n+e)    

        C、O(n2)      

        D、O(ne)

答案：C

27.Dijkstra算法是______ 方法求出图中从某顶点到其余顶点的最短路径的。             

        A、按长度递减的顺序

        B、按长度递增的顺序 

        C、通过深度优先遍历

        D、通过广度优先遍历

答案：B

28.用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻，S={0，2，3，4}，下一步选取的目标顶点可能是______。             

        A、顶点2     

        B、顶点3     

        C、顶点4     

        D、顶点7

答案：D

29.用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某时刻，S={0，2，3，4}，则以后可能修改最短路径是______。        

        A、从顶点0到顶点2的最短路径    

        B、从顶点0到顶点3的最短路径    

        C、从顶点0到顶点4的最短路径    

        D、从顶点0到顶点1的最短路径

答案：D

30.有一个顶点编号为0～4的带权有向图G，现用Floyd算法求任意两个顶点之间的最短路径，在算法执行的某时刻，已考虑了0～2的顶点，现考虑顶点3，则以下叙述中正确的是______。                 

        A、只可能修改从顶点0～2到顶点3的最短路径   

        B、只可能修改从顶点3到顶点0～2的最短路径      

        C、只可能修改从顶点0～2到顶点4的最短路径  

        D、所有其他两个顶点之间的路径都可能被修改

答案：D

31.在有向图G的拓扑序列中，若顶点i在顶点j之前，则以下情况不可能出现的是______。        

        A、G中有边<i，j>

        B、G中有一条从顶点i到顶点j的路径    

        C、G中没有边<i，j>

          D、G中有一条从顶点j到顶点i的路径

答案：D

32.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是______。        

        A、存在，且唯一

        B、存在、且不唯一      

        C、存在，可能不唯一

        D、无法确定是否存在

答案：C

33.若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图______。             

        A、是个有根有向图    

        B、是个强连通图 

        C、含有多个入度为0的顶点    

        D、含有顶点数目大于1的强连通分量

答案：D

34.以下关于图拓扑排序的叙述中正确的是______。

Ⅰ.任何无环的有向图，其顶点都可以排在一个拓扑序列中。

Ⅱ.若n个顶点的有向图有唯一的拓扑序列，则其边数必为n-1。

Ⅲ.在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条边<a，b>           

        A、仅Ⅰ

        B、仅Ⅰ、Ⅲ 

        C、仅Ⅱ、Ⅲ

         D、Ⅰ、Ⅱ和Ⅲ

答案：A

35.用非递归深度优先遍历一个有向无环图G的时，在退栈返回时输出该顶点，则输出的顶点序列是______。           

        A、一个拓扑序列

        B、无序的      

        C、逆拓扑序列    

        D、按顶点编号次序

答案：C

36.关键路径是事件结点网络中______。          

        A、从源点到汇点的最长路径      

        B、从源点到汇点的最短路径    

        C、最长的回路    

        D、最短的回路

答案：A

37.一个表示工程的AOE网中的关键路径______。        

        A、必须是唯一的  

        B、可以有多条    

        C、可以没有

        D、以上都不对

答案：B

38.以下对于AOE网的叙述中，错误的是______。         

        A、在AOE网中可能存在多条关键路径   

        B、关键活动不按期完成就会影响整个工程的完成时间 

        C、任何一个关键活动提前完成，整个工程也将提前完成    

        D、所有关键活动都提前完成，整个工程也将提前完成

答案：C

39.在用Prim和Kruskal算法构造最小生成树时，前者更适合于  ①  ，后者更适合于  ②  。             

A、有向图     B、无向图     C、稀疏图     D、稠密图

答案 :C D

40.一个无向连通图的生成树是含有该连通图的全部顶点的（ ）。

        A. 极小连通子图

        B. 极小子图

        C. 极大连通子图

        D. 极大子图

答案：A

41.连通图的生成树包含了图中所有顶点。(√）

42.一个连通图的生成树是唯一的。（×）

43.对n个顶点的连通图G来说，如果其中的某个子图有n个顶点、n-1条边，则该子图一定是G的生成树。（×）

44.对于无向图生成树，从同一顶点出发所得到的生成树一定是相同的。（×）

45.对于无向图生成树，其深度优先生成树和广度优先生成树一定不相同。（×）

46.如果具有n个顶点的图恰好是一个环，则它有（ ）棵生成树。

        A. n-1

        B. n

        C. n+1

        D. 2n

答案：D（如果图恰好是一个环，对于图中每个顶点，都有顺时针和逆时针方向两棵生成树，总计2n棵生成树。）

47.若一个具有n个顶点和e条边的无向图是一个森林（n>e），则该森林必有（ ）棵树。

        A. e

        B. n

        C. n-e

        D. 1

答案：C（设该森林有m棵树，结点个数分别为n1、n2、…、nm，则总顶点数n=n1+n2+…+nm，第i棵树的边数=ni-1，总边数=(n1-1)+(n2-1)+…+(nm-1)=n-m=e，所以m=n-e。）

48.图的遍历就是访问图中所有顶点。（×）

49.任何一个图，一旦指定源点，其深度优先遍历序列是唯一的。（×）

50.图的深度优先遍历算法仅对无向图适用。（×）

51.有向图的遍历不可采用广度优先遍历方法。（×）

52.图的深度优先遍历算法和广度优先遍历算法是两种不同的算法，所以任何图的这两种遍历序列是不可能相同的。（×）

53.图的遍历是指（ ）。

        A. 访问图的所有顶点

        B. 以某种次序访问图的所有顶点

        C. 从一个顶点出发访问图中所有顶点且每个顶点只能访问一次

        D. 从一个顶点出发访问图中所有顶点但每个顶点可以访问多次

答案：C

54.以下（ ）方法可用于求无向图的连通分量。

        A. 遍历

        B. 拓扑排序

        C. Dijkstra算法

        D. Prim算法

答案：A(从图中某个顶点出发进行遍历，可将与该顶点相连通的所有顶点全部访问，也就找到了该顶点所在的连通分量。)

55.采用邻接表存储的图的深度优先遍历算法类似于二叉树的______ （ ）算法。

        A. 先序遍历

        B. 中序遍历

        C. 后序遍历

        D. 层次遍历

答案:A(当图变为二叉树时，深度优先遍历过程是访问起点（类似于访问根结点），访问起点的相邻点，再访问起点的相邻点的相邻点（类似于访问左子树），…，回溯回来时再访问起点的下一个相邻点（类似于访问右子树）)。

仅用于学习，不用于其他用途

数据结构相关知识点及相关练习题(1)_卓卓卓-CSDN博客

数据结构的相关练习（2）附加答案_卓卓卓-CSDN博客

数据结构的相关练习（3）附加答案_卓卓卓-CSDN博客