《数据结构章节练习题及答案6.docx》由会员分享，可在线阅读，更多相关《数据结构章节练习题及答案6.docx（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 .请简述图的结构特性。图G由顶点(图中通常将结点称为顶点)的非空有限集合V和 边的集合E组成,记为G=(V, E)。每一个顶点偶对就是图中的一条边, 所以，E用于表示V上的连接关系。在一个图中，至少要包含一个顶 点，但可以没有任何边。2 .请解释有向图、无向图、弧、弧尾、弧头、顶点的度、顶点的入度、顶点的出度、路径、路径长度、的入度、顶点的出度、路径、路径长度、的入度、顶点的出度、路径、路径长度、路、简单路、连通图、单向连通图、强连通图、子图、连通分量、强连通分量、权、带权图、 生成树、最小生成树等基本术语的含义。有向图、弧、弧尾和弧头：假设E(G)中的顶点偶对是有序的，那么 这些有序偶对
2、就形成了有向边，此时图G称为有向图。其中，有向 边也简称为弧。在有向图G中，对于一条从顶点增到顶点看的弧， 记为Vi, Vj并有Vi, vjE(G),称Vi为弧尾，Vj为弧头。无向图：假设E(G)中的顶点偶对是无序的，那么这些无序偶对就形 成了无向边，此时图G称为无向图。顶点的度、顶点的入度和顶点的出度：在无向图中，与顶点Vi 相关联的边的数目称为顶点M的度。在有向图中，以顶点M为弧头 的弧的数目称为顶点M的入度；以顶点4为弧尾的弧的数目称为Vi 的出度；顶点环的入度和出度之和称为的度。路径和路径长度：在图G中，假设存在一个顶点序列 V产），使得对于任意0jn-l有v?,vA*e（g）（假设G
3、为有向图）或 （v；,v+l）eE（G）（假设G为无向图），那么该序列是从顶点V?到顶点v尸的一 条路径。一条路径中边的数目称为路径长度。回路和简单回路：在一条路径中，假设组成路径的顶点序列中第一 个顶点与最后一个顶点相同，那么该路径称为回路（或环）；在一个回 路中，假设除第一个顶点与最后一个顶点外，其他顶点只出现一次，那么 该回路称为简单回路（或简单环）。连通图：无向图G中，假设任意两个顶点都是连通的，那么称G为 连通图。单向连通图和强连通图：有向图G中，假设任意两个顶点都是单 向连通的，那么称G是单向连通图；假设任意两个顶点都是强连通的， 那么称G为强连通图。子图：对于图G、G,假设满足V
4、（G）cV（G） Ke（G）cE（Q ,那么 G是 G 的子图。连通分量和强连通分量：一个无向图的极大连通子图称为该无向 图的连通分量；一个有向图的极大强连通子图称为该有向图的强连通 分量。权和带权图：可以为一个图中的每条边标上一个具有某种意义的 实数，该实数就称为是边的权。边上带权的图就称为带权图。生成树和最小生成树：假设无向图G的一个子图G是一棵包含图G所有顶点的树，那么G，称为图G的生成树。在所有形式的生成树中, 边上的权之和最小的生成树，称为最小生成树。3 .请列举可以用图来描述的实际问题。请参考例6-1和例6-2o.请简述图的基本操作及各操作的含义。创立图：创立不包含任何顶点和边的空
5、图。对图作深度优先遍历：类似于树的先序遍历，即从某一个顶点开 始访问，访问后将该顶点去除得到假设干子图，对每个子图再依次 进行深度优先遍历。对图作广度优先遍历：类似于树的逐层遍历，即先从某一个顶点开始访问，然后访问与该顶点相邻接且未被访问过的顶点集 VKG),再访问与VI(G)中顶点相邻接且未被访问过的顶点集 V2(G),重复该过程直至与初始顶点连通的所有顶点都被访问完。 对于非连通图或非强连通图，还要从某一个未被访问的顶点开始 重复上一过程，直至所有顶点访问完毕。获取顶点数目：获取图中所包含的顶点的数目。获取边的数目：获取图中所包含的边的数目。获取与指定顶点相关联的第一条边：对无向图，获取到
6、与指定顶 点相关联的第一条边；对有向图，获取到以指定顶点作为弧尾的 第一条弧。不同表示方法获取到的结果会有所不同(邻接矩阵法 按顶点编号顺序，邻接压缩表和邻接链表按边的添加顺序)。获取与指定边有相同关联顶点的下一条边：对无向图，获取到与 指定边(nVl,nV2)有相同关联顶点nVl的下一条边；对有向图， 获取到与指定M有相同弧尾nVl的下一条弧。不同表 示方法获取到的结果会有所不同(邻接矩阵法按顶点编号顺序， 邻接压缩表和邻接链表按边的添加顺序)。添加一个顶点：向图中添加一个新顶点。添加一条边：对无向图，向图中添加一条新边；对有向图，向图 中添加一条新弧。获取一个顶点中存储的数据：根据顶点编号
7、获取该顶点中存储的 数据。判断一条边是否存在：对无向图，判断两个顶点nVl和nV2之间 是否存在边；对有向图，判断是否存在从顶点nVl到顶点nV2的 弧。设置一条边的权：对无向图，设置指定边(nVl,nV2)上的权；对有 向图，设置指定弧nVl,nV2上的权。获取一条边的权：对无向图，获取指定边(nVl,nV2)上的权；对有 向图，获取指定弧nVl,nV2上的权。4 .请简述图的三种常用表示方法。邻接矩阵法：用矩阵来表示各顶点之间的连接关系。对于有n个 顶点的图G=(V, E),其邻接矩阵A为n*n的方阵，元素Aij(Oi,jn) 定义为：fw-对无向图存在，4)wE(G)，对有向图存在 匕,
8、为eE(G)期E二；00反之其中，Wij为边(Vi,)或7, Vj上的权。邻接压缩表：邻接矩阵的一种压缩表示形式，使用3个顺序表来表示图中顶点之间的连接关系和权。设图中共有n个顶点vo, vi,Vn-|), 3个顺序表分别为s、w和h。在s中依次记录与顶点Vi (i = 0, 相关联的顶点；在w中依次记录s中存储的各条边的权； 在h中依次记录与顶点环相关联的顶点在s中的起始存储位置。邻接链表：图的一种链式存储结构。每个顶点中设置一个指向链表头的指针，在链表中保存与该顶点相邻接的顶点信息(包括顶点位 置及两个顶点形成的边的权)。6 .请简述图的两种常用遍历方法及每一种遍历方法中结点的访 问顺序。
9、广度优先遍历：类似于树的逐层遍历，即先从某一个顶点开始访 问，然后访问与该顶点相邻接且未被访问过的顶点集Vi(G),再访问 与M(G)中顶点相邻接且未被访问过的顶点集V2(G),重复该过程直 至与初始顶点连通的所有顶点都被访问完。对于非连通图或非强连通 图，还要从某一个未被访问的顶点开始重复上一过程，直至所有顶点 访问完毕。深度优先遍历：类似于树的先序遍历，即从某一个顶点开始访问, 访问后将该顶点去除得到假设干子图，对每个子图再依次进行深度优先 遍历。7 .请列举最小生成树和最短路径可以用于解决什么应用问题。请参考例6-1和例6-2o.请简述Prim算法的作用和具体步骤。Prim算法用于最小生
10、成树问题求解。对于有n个顶点的图G=(V,E), Prim算法从空树T开始，按照以下规那么将n个顶点和n-1条边依 次添加到树中，形成最小生成树：(a)从某一顶点V。，开始，将该顶点作为树的根结点加入到T中, 使得T中的数据元素集合D=v(/,数据元素关系集合R= 。(b)对于一个顶点在集合D中、另一个顶点在集合V-D中的那 些边，找出权最小的一条边，将该边在集合V-D中的顶点Vi (i=l,2,.,n-l)加入到集合D中，并将顶点间关系 (j0) , D(vo, Vf)表示当前计算得到的从顶点Vo到顶点vf的最短路径长度(初始 D(v0, Vi*)= w(v0, Vi) o(b)将顶点vm,
11、= argmin(D(v0,vi,)加入到集合S中，并将从顶点Vo, v/eV-S到顶点Vm的最短路径记录下来。假设仍有顶点没有加到集合S中，那么对集合V-S中的顶点V，计算D(v。，,v/) =+o(c)重复上一步骤直至图中所有顶点都加到集合S中。10 .请简述Floyd算法的作用和具体步骤。Floyd算法用于计算每一对顶点之间的最短路径。对于有n个顶点的图G=(V, E),假设要计算任意两个顶点vf和v。(j,k为区间 上的整数且#k)之间的最短路径，那么其计算步骤为：(a)令w(vj： v0)表示连接顶点vf和顶点的边的权(这里为方 便计算,令w(vj, Vj,)=O) , D(Vj,便)表示当前计算得到的从顶点Vj, 到顶点的最短路径长度(初始D(v；,Vk)=w(v；, V。)。(b)对于图中每一个顶点vf (i依次取值为0, 1,n-1),假设D（vj,vk）D（Vj,Vi，）+D（vi,vk,）,那么说明路径（vf,，vAvQ的长度更短，此时令D（W，Vk）=D（Vj；v，）+D（vf,v并更新从顶点看到顶点的路 径。