《数据结构复习与习题解析》由会员分享，可在线阅读，更多相关《数据结构复习与习题解析（29页珍藏版）》请在金锄头文库上搜索。
1、数据结构 与 算法复习与习题解析(第6-8讲）第6讲 图v图的相关定义(无向完全图、有向完全图、网、连通图、 强连通图、度、入度、出度、生成树和生成森林)v图的存储方式q邻接矩阵o无向图邻接矩阵o有向图邻接矩阵o网的邻接矩阵o每个结点的出度？入度？度？o图的边数？q邻接表o每个结点的出度？入度？度？o图的边数？*2例例已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。当邻接表的存储 结构形成后，图 便唯一确定！例题解析*3图的遍历v广度优先搜索从图的某一结点出发，首先依次访问该结点的所有邻接顶点 V1, V2, , Vn 再按这些顶点被访问的先后次序依次访问与它们
2、相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均 被访问为止。 v深度优先搜索1、访问指定的起始顶点； 2、若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的 全部顶点都访问完毕； 3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始 顶点并访问之，转 2； 反之，遍历结束。 *4例题解析*5熟悉图图的存储结储结 构，画出右边边有向图图的邻邻接矩阵阵、邻邻 接表、逆邻邻接表。写出邻邻接表表示的图图从顶顶点A出发发的 深度优优先遍历历序列和广度优优先遍历历序列。深度优优先遍历历序列为为ABCFED，广度优优先遍历历序列为为AB
3、DCEF邻接矩阵如下 邻接表如下逆邻接表如下【答】最小生成树v普里姆（Prim）算法q将顶点进行归并v克鲁斯卡尔（Kruscal）算法q将边进行归并*6例：Prim算法最小代价生成树 的生成过程UV0V1V3V2V4V56165556342V0V1V3V2V4V51 5342(4)(1)(3)(2)(5)*7例： Kruscal 算法 实例的执行过程图G1、初始连通分量： 0,1,2,3,4,52、反复执行添加、放弃动作。条件：边数不等于 n-1时边 动作连通分量(0,2) 添加 0,2,1,3,4,5(3,5) 添加 0,2,3, 5,1,4(1,4) 添加 0,2,3, 5,1,4(2,5
4、) 添加 0,2,3,5,1,4(0,3) 放弃 因构成回路(2,3) 放弃 因构成回路(1,2) 添加 0,2,3,5,1,4最小代价生成树V0V1V3V2V4V56165556342V0V1V3V2V4V51 53425 5*8例题解析v请分别用Prim算法和Kruskal算法构造以下网络的 最小生成树，并求出该树的代价。*9例题解析*10【解析】Prim算法的操作步骤：首先从一个只 有一个顶点的集合开始，通过加入与其中顶点 相关联的最小代价的边来扩充顶点集，直到所 有顶点都在一个集合中。例题解析*11【解析】Kruscal算法的操作步骤： 首先将n个顶 点看成n个互不连通的分量，从边集中
5、找最小代价 的边，如果落在不同连通分量上，则将其加入最小 生成树，直到所有顶点都在同一连通分量上。单源最短路径v在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。v迪杰斯特拉 (Dijkstra) 算法：按路径长度递增次序产生最短路径 1、把 V 分成两组： (1) S：已求出最短路径的顶点的集合。 (2) V - S = T：尚未确定最短路径的顶点集合。 2、将 T 中顶点按最短路径递增的次序加入到 S 中，保证：(1) 从源点 v0 到 S 中各顶点的最短路径长度都不大于 从 v0 到 T 中任何顶点的最短路径长度。 (2) 每个顶点对应一
6、个距离值： S中顶点：从 v0 到此顶点的最短路径长度。 T中顶点：从 v0 到此顶点的只包括 S 中顶点作中间顶点的 最短路径长度。 *12Dijkstra 算法步骤：T 中顶点对应的距离值用辅助数组 D 存放。 Di 初值：若 存在，则为其权值；否则为。 终 点从 v0 到各终点的最短路径及长度 i =1i =2i =3i =4i =5i =6 v1 v2 v3 v4 v5 v6 vjPv5v1v6v4v3v2v0 856 230 13717329v21383032 v2813133032v3v1v11313302220 v38+5v2 192220 v4 v48+5+6v2-v3 212
7、0 v6v513+7v1 21v5v6初始时令 S=v0, T=其余顶点。 v0从 T 中选取一个其距离值最小的顶点 vj，加入 S。 对 T 中顶点的距离值进行修改：若加进 vj 作中间顶点，从 v0 到 vi 的距离值比 不加 vj 的路径要短，则修改此距离值。 重复上述步骤，直到 S = V 为止。 8+5 +6+2v2-v3-v4 *13拓扑排序vAOV网： 在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点表示顶点表示 活动的网络活动的网络(Activity On Vertex network)简 称为AOV网。vv拓扑排序的方法：拓扑排序的方法：1.在有
8、向图中选一个没有前驱的顶点且输出之。 2.从图中删除该顶点和所有以它为起点的弧。3.重复上述两步，直至全部顶点均已输出；或者当图 中不存在无前驱的顶点为止。 *14例题解析v拓扑排序的结果不是唯一的，试 写出下图任意2个不同的拓扑序 列。*15【解析】解题关键是弄清拓扑排序的步骤（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶 点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再 有无前驱的顶点。【答案】（1）0132465 （2）0123465关键路径AOE(Activity on Edge)网络：定义结点为事件，有向边的指向表示事件的执行次序。单位是时间（时刻）。有向
9、边定义为活动，它的权值 定义为活动进行所需要的时间。对AOE网，我们关心两个问题： (1)完成整项工程至少需要多少时间？ ( (2 2) )哪些哪些活动是影响工程进度的活动是影响工程进度的关键？关键？关键路径路径长度最长的路径。路径长度路径上各活动持续时间之和ve(j) 表示事件 vj 的最早发生时间。 vl(j) 表示事件 vj 的最迟发生时间。 ee(i) 表示活动 ai 的最早开始时间。 el(i) 表示活动 ai 的最迟开始时间。 el(i) - ee(i) 表示完成活动 ai 的时间余量。 关键活动关键活动 关键路径上的活动，即 el(i) = ee(i) 的活动。 *16如何找 e
10、l(i) = ee(i) 的关键活动？ 设活动 ai 用弧 表示，其持续时间记为：dut() 则有： (1) ee(i) = ve(j) (2) el(i) = vl(k) - dut() jkai(1) 从 ve(1) = 0 开始向前递推 (2) 从 vl(n) = ve(n) 开始向后递推 如何求 ve(j) 和 vl(j) ？ a8=7a9=4a10=2a11=4a7=9a4=1a5=1a6=2a2=4a1=6v9v8v7v6v4v5v3v2v1a3=5*17a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11活动 ee el el ee 0 06 4 5 7 7 7
11、16 1400 26 6 8 7 7 10 16 1430 20 2 3 0 0 3 0 03求关键路径步骤： 求 ve(i)、vl(j) 求 ee(i)、el(i) 计算 el(i) - ee(i)v1 v2 v3 v4 v5 v6 v7 v8 v9顶点 ve vl064577 16 14 1806687 10 16 14 18a8=7a9=4a10=2a11=4a7=9a4=1a5=1a6=2a2=4a1=6v9v8v7v6v4v5v3v2v1a3=5*18图存储结构遍 历邻接矩阵邻 接 表 十字链表 邻接多重表深度优先搜索DFS广度优先搜索BFS无向图的应用应用图的连通分量图的生成树图的
12、生成树最小生成树Prim算法Kruskal算法最短路径Dijkstra算法Floyd算法（利用DFS）有向图的应用DAG图拓扑排序 关键路径*19第7讲 查找v基本概念：表/记录/关键字/静态查找表/动态查找表 /平均查找长度v顺序表查找和“哨兵”v有序查找：折半查找/插值查找/斐波那契查找v线性索引：稠密索引/分块索引/倒排索引v二叉排序树/平衡二叉树：构建/插入/删除/保持平衡vB-树/B+树：构建/插入/删除操作v散列表：散列函数的选择和处理冲突的方法*20例题解析v设有序表为(a, b, c, d, e, f, g, h, i, j, k, p, q)， 请分别画出对给定值a, g和n
13、进行折半查找的过程。*21【答】例题解析v构造有12个元素的二分查找的判定树，并求解下列问题： （1）各元 素的查找长度最大是多少？ （2）查找长度为1、2、3、4的元素各有 多少？具体是哪些元素？ （3）查找第5个元素依次要比较哪些元素 ？【答】 12个元素的判断树如下图所示：*22653912241171810（1）最大查找长度是树的深度4。（2）查找长度为1的元素有1个，为第6个 ，查找长度为2的元素有2个，为第3个和第 9个，查找长度为3的元素有4个，为第1、4 、7、11个，查找长度为4的元素有5个，为 第2、5、8、10、12个。（3）查找第五个元素依次比较6，3，4，5。例：设有
14、一组关键字32,75,63,48,94,25,36,18,70，采用哈希函数： H(key)=key MOD 11并采用步长为1的线性探测法解决冲突，试在0-10的 散列地址空间中对该关键字序列构造哈希表。【答】依题意，m=11，线性探测再散列的下一地址计算公式为：d1=H(key)， dj+1=(dj+1) MOD 11；j=1,2,.其计算过程如下：H(32)=32 MOD 11=10 H(75)=75 MOD 11=9H(63)=63 MOD 11=8 H(48)=48 MOD 11=4H(94)=94 MOD 11=6 H(25)=25 MOD 11=3H(36)=36 MOD 11=
15、3(冲突) H(36)=(3+1) MOD 11=4(仍冲突)H(36)=(4+1) MOD 11=5 H(18)=18 MOD 11=7H(70)=70 MOD 11=4 (冲突) H(70)=(4+1) MOD 11=5 (仍冲突)H(70)=(10+1) MOD 11=0012345678910702548369418637532例题解析*23第八讲 排序v简单排序方法（0（n2）q插入排序（稳定排序）q选择排序（不稳定排序）q冒泡排序（不稳定排序）v先进排序方法（ O(nlogn)）q快速排序（不稳定排序）q归并排序（稳定排序）q堆排序（不稳定排序）*24一、时间性能 时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以 快速排序为最好。 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序， 其中以直接插入为最好，特别是对那些对关其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。键字基本有序的记录序列尤为如此。 时间复杂度为 O(n*d)：基数排序。 1. 按平均时间性能来分，有三类排序方法： 2. 当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中
