数据结构第7章 图习题

《数据结构第7章 图习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章图一、单项选择题1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。A．l/2B．1C．2D．42．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。A．l/2B．1C．2D．43．一个具有n个顶点的无向图最多包含______条边。A．nB．n＋1C．n-1D．n(n-1)/24．一个具有n个顶点的无向完全图包含______条边。A．n(n-l)B．n(n+l)C．n(n-l)/2D．n(n-l)/25．一个具有n个顶点的有向完全图包含______条边。A．n(n-1)B．n(n+l)C．

2、n(n-l)/2D．n(n+l)/26．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。A．nB．n×nC．n-1D．(n-l)×(n-l)7．无向图的邻接矩阵是一个______。A．对称矩阵B．零矩阵C．上三角矩阵D．对角矩阵8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。A．nB．eC．2nD．2e9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。A．nB．eC．2nD．2e10．在有向图的邻接表中，每个

3、顶点邻接表链接着该顶点所有______邻接点。A．入边B．出边C．入边和出边D．不是入边也不是出边11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。A．入边B．出边C．入边和出边D．不是人边也不是出边12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。A．完全图B．连通图C．有回路D．一棵树13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。A．先序遍历B．中序遍历C．后序遍历D．按层遍历14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的__

4、____算法。A．先序遍历B．中序遍历C．后序遍历D．按层遍历15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。A．G肯定不是完全图B．G一定不是连通图C．G中一定有回路D．G有二个连通分量16．下列有关图遍历的说法不正确的是______。A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次17．下列说法中不正确的是______。A．无向图中的极大连通子图称为连通分量B．连通图的广度优

5、先搜索中一般要采用队列来暂存刚访问过的顶点C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D．有向图的遍历不可采用广度优先搜索方法18．一个有向图G的邻接表存储如下图7-1所示，现按深度优先搜索遍历，从顶点v1出发，所得到的顶点序列是______。A．v1，v2，v3，v4，v5B．v1，v2，v3，v5，v4C．v1，v2，v4，v5，v3D．v1，v2，v5，v3，v4234∧35∧5∧4∧v1v2v3v4∧v5图7-1一个有向图的邻接表19．对图7-2所示的无向图，从顶点1开始进行深度优先遍历，可得到顶点访问序列______。A

6、．1，2，4，3，5，7，6B．1，2，4，3，5，6，7C．1，2，4，5，6，3，7D．1，2，3，4，5，7，61654327图7-2一个无向图20．对图7-2所示的无向图，从顶点1开始进行广度优先遍历，可得到顶点访问序列______。A．1，3，2，4，5，6，7B．1，2，4，3，5，6，7C．1，2，3，4，5，7，6D．2，5，1，4，7，3，621．一个无向连通图的生成树是含有该连通图的全部顶点的______。A．极小连通子图B．极小子图C．极大连通子图D．极大子图22．设无向图G=(V,E)和G’=(V’,E’)，如果G’

7、为G的生成树，则下列说法中不正确的是______。A．G’为G的连通分量B．G’为G的无环子图C．G’为G的子图D．G’为G的极小连通子图且V’＝V23.任意一个无向连通图______最小生成树。A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在24．对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个________。A．由n-1条权值最小的边构成的子图。B．由n-1条权值之和最小的边构成的子图。C．由n-1条权值之和最小的边构成的连通子图。D．由n个顶点构成的边的权值之和最小的生成树。25．若一个有向图中的顶点不能排成一个

8、拓扑序列，则可断定该有向图_______。A．是个有根有向图B．是个强连通图C．含有多个入度为0的顶点D．含有顶点数目大于1的强连通分量26．判定一个有向图是否存在回路除了可以利