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

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

1、第七章图试题单项选择题在无向图中定义顶点的度为与它相关联的（）的数目。A.顶点B・边C・权D.权值在无向图中定义顶点q与VjZ间的路径为从X到达勺的一个（）0A.顶点序列B.边序列C.权值总和D.边的条数图的简单路径是指（A.权值）不重复的路径。B•顶点C.边D.边与顶点均设无向图的顶点个数为m则该图最多有（A.n-1B.n(n-1)/2)条边。C.n(n+l)/2D.n(n-l)n个顶点的连通图至少有（）条边。A.n-1C•n+1D.0在一个无向图中，所有顶点的度数之和等于所有边数的（A.3B.2C.1)倍。D.1/2若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（A.上三

2、角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵图的深度优先搜索类似于树的（）次序遍历。A.先根B.中根C•后根D.层次图的广度优先搜索类似于树的（A.先根B.屮根）次序遍历。C・后根D.层次）辅助结构,在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（判断一条边的两个端点是否在同一个连通分量上。A.位向量B.堆C.并查集D.生成树顶点集合在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能在图中构成（）。A.重边B.有向环C.回路D.权值重复的边在用Dijkstra算法求解带权有向图的最短路径问题吋，要求图中每条边所带的权值必须是

3、（）。A.非零B.非整C.非负D.非正在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少A.1B・2C・3D.0e条边，采用邻接表作为其存储表示,在进行拓扑排序时,总的计算时间为()oA.0(nlog2e)B.0(n+e)C.0(ne)设有向图有n个顶点和D.O(n2)设有向图有n个顶点和e条边,采用邻接矩阵作为其存储表示，在进行拓扑排序时,总的计算时间为)oA.0(nlog2e)B.0(n+e)C.0(ne)D.0(n2)设G1=(VI,El)和G2=(V2,E2)A.G1是G2的子图C.G1是G2的连通分量为两个图，如果VIcV2,ElcE2,则称

4、（B.G2是G1的子图D.G2是G1的连通分量）。B.出度D.（入度+出度））/2A.n-1n(n-1)/2D•n(n-1)在一个带权连通图G屮，权值最小的边一定包含在G的（）生成树屮。A.某个最小B.任何最小C.广度优先D•深度优先有向图的一个顶点的度为该顶点的（A・入度C.入度与出度之和一个连通图的生成树是包含图中所有顶点的一个（）子图。A.极小B.连通C.极小连通D.无环n（n>l）个顶点的强连通图中至少含有（）条有向边。对于具有e条边的无向图，它的邻接表屮有（）个边结点。A.e-1B.eC.2（e-1）D.2e对于如图所示的带权有向图，从顶点1到顶点5的最短路径为（）oA.1,4,

5、5B.1,2,3,5C.1,4,3,5D.1,2,4,3,5具有n个顶点的有向无环图最多可包含（）条有向边。A.n-1C.n(n-1)/2一个有n个顶点和n条边的无向图一定是（）。A.连通的B・不连通的C.无环的D.有环的A.nB.n(n-1)/2C.n(n+1)/2D.n(n-l)26•对于有向图，其邻接矩阵表示比邻接表表示更易于()。A.求一个顶点的度B.求一个顶点的邻接点C.进行图的深度优先遍历D.进行图的广度优先遍历27•在一个有向图的邻接矩阵表示中,删除一条边vj>^要耗费的时间是(A.0(1)B.0(i)c.0(j)D.0(i+j)28•与邻接矩阵相比，邻接表更适合于存储()图

6、。A.无向B•连通C•稀疏D.稠密图29•设一个有n个顶点和e条边的有向图采用邻接矩阵表示，耍计算某个顶点的出度所耗费的时间是()oA.0(n)B.0(e)C.0(n+e)D.0(n2)30•为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是()。A.栈B.队列C・二叉树D・树参考答案：1.B2.A3.B4.B5•A6.B7.D8.A9.D10.C:Ll.C12・C13.B14.B15・D16.A17.C18.C19.B20.A21.D22.D23.C24.D25.C26.A27.A28.C29.A30.B二.填空题1.图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有

7、穷集合。2.用邻接矩阵存储图，占用存储空间数与图中顶点个数关，与边数关。3.n(n>0)个顶点的无向图最多有条边，最少有条边。4.n(n>0)个顶点的连通无向图最少有条边。0101005.若3个顶点的图G的邻接矩阵为L°1°」，则图G—定是向图。6.n(n>0)个顶点的连通无向图各顶点的度之和最少为o7.设图G=(V,E),V={VO,VI,V2,V3},E={(VO,VI)z(V0zV2),(VO,V3),(VI,V3