《数据结构》习题汇编07 第七章 图 试题

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

1、第七章图试题一、单项选择题1.在无向图中定义顶点的度为与它相关联的（）的数目。A.顶点B.边C.权D.权值2.在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（）。A.顶点序列B.边序列C.权值总和D.边的条数3.图的简单路径是指（）不重复的路径。A.权值B.顶点C.边D.边与顶点均4.设无向图的顶点个数为n，则该图最多有（）条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)5.n个顶点的连通图至少有（）条边。A.n-1B.nC.n+1D.06.在一个无向图中，所有顶点的度数之和等于所有边数的()倍。A.3B.2C.1D.1/27.若采用

2、邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵8.图的深度优先搜索类似于树的（）次序遍历。A.先根B.中根C.后根D.层次9.图的广度优先搜索类似于树的（）次序遍历。A.先根B.中根C.后根D.层次10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A.位向量B.堆C.并查集D.生成树顶点集合11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）。A.重边B.有向环C.

3、回路D.权值重复的边12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（）。A.非零B.非整C.非负D.非正13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少有（）子女。24A.1B.2C.3D.01.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)2.设有向图有n个顶点和e条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为（）。A.O(nlog2e)B.O(n+

4、e)C.O(ne)D.O(n2)16.设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1ÍV2，E1ÍE2，则称（）。A.G1是G2的子图B.G2是G1的子图C.G1是G2的连通分量D.G2是G1的连通分量17.有向图的一个顶点的度为该顶点的（）。A.入度B.出度C.入度与出度之和D.(入度﹢出度))／218.一个连通图的生成树是包含图中所有顶点的一个（）子图。A.极小B.连通C.极小连通D.无环19.n(n＞1)个顶点的强连通图中至少含有（）条有向边。A.n-1B.nn(n-1)/2D.n(n-1)20.在一个带权连通图G中，权值最小的边一定包含在G的（）生

5、成树中。A.某个最小B.任何最小C.广度优先D.深度优先21.对于具有e条边的无向图，它的邻接表中有（）个边结点。A.e-1B.eC.2(e-1)D.2e22.对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）。A.1,4,5B.1,2,3,5C.1,4,3,5D.1,2,4,3,51261381955412323.具有n个顶点的有向无环图最多可包含（）条有向边。A.n-1B.nC.n(n-1)/2D.n(n-1)24.一个有n个顶点和n条边的无向图一定是（）。A.连通的B.不连通的C.无环的D.有环的25.在n个顶点的有向无环图的邻接矩阵中至少有（）个零元素。A

6、.nB.n(n-1)/2C.n(n+1)/2D.n(n-1)2416.对于有向图，其邻接矩阵表示比邻接表表示更易于（）。A.求一个顶点的度B.求一个顶点的邻接点C.进行图的深度优先遍历D.进行图的广度优先遍历17.在一个有向图的邻接矩阵表示中，删除一条边需要耗费的时间是（）。A.O(1)B.O(i)C.O(j)D.O(i+j)18.与邻接矩阵相比，邻接表更适合于存储（）图。A.无向B.连通C.稀疏D.稠密图19.设一个有n个顶点和e条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（）。A.O(n)B.O(e)C.O(n+e)D.O(n2)20

7、.为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（）。A.栈B.队列C.二叉树D.树参考答案：1.B2.A3.B4.B5.A6.B7.D8.A9.D10.C11.C12.C13.B14.B15.D16.A17.C18.C19.B20.A21.D22.D23.C24.D25.C26.A27.A28.C29.A30.B二、填空题1.图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷________集合。2.用邻接矩阵存储图，占用存储空间数与图中顶点个数________关，与边数________关。3.n(