数据结构复习与习题解析.ppt

一、时间性能 时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序，其中以 快速排序为最好。 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序， 其中以直接插入为最好，特别是对那些对关 键字基本有序的记录序列尤为如此。 时间复杂度为 O(n*d)：基数排序。 1. 按平均时间性能来分，有三类排序方法： 2. 当待排序列按关键字顺序有序时，直接插入排序和起泡排序能 达到 O(n) 的时间复杂度，快速排序的时间性能蜕化为 O(n2) 。 3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中 关键字的分布而改变。 3.5 各种排序方法的综合比较 * * 二、空间性能 指的是排序过程中所需的辅助空间大小。 所有的简单排序方法(包括：直接插入、冒泡和简单选择) 和 堆排序的空间复杂度为 O(1)； 快速排序为 O(logn)，为递归程序执行过程中，栈所需的辅助 空间； 3. 归并排序所需辅助空间最多，其空间复杂度为 O(n)； 4. 链式基数排序需附设队列首尾指针，则空间复杂度为 O(2*rd+n) 三、排序方法的稳定性能 1. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳 定的排序方法。 2. 对于不稳定的排序方法，只要能举出一个实例说明即可。 3. 快速排序、堆排序是不稳定的排序方法。 * * 各种内部排序方法的比较 排序方法 平均时间 最坏情况 最好情况 辅助存储 稳定性 插入排序 O(n2) O(n2) O(n) O(1） 稳定 选择排序 O(n2) O(n2) O(n2) O(1） 稳定 冒泡排序 O(n2) O(n2) O(n) O(1） 稳定 快速排序 O(nlgn) O(n2) O(nlgn ) O(lgn) 不稳定 归并排序 O(nlgn ) O(nlgn) O(nlgn ) O(n） 稳定 堆排序 O(nlgn ) O(nlgn) O(nlgn ) O(1） 不稳定 基数排序 O(d ×n) O(d ×n) O(d ×n) O(n) 稳定 * * 例题解析 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。 （1） 直接插入排序；（2） 起泡排序； 【答】（1）直接插入排序 * * 例题解析 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。 （1） 直接插入排序；（2） 起泡排序； 【答】（2）起泡排序 * * * * * * * 数据结构 与 算法 复习与习题解析(第6-8讲） 第6讲 图 图的相关定义(无向完全图、有向完全图、网、连通图、强连通图、度、入度、出度、生成树和生成森林) 图的存储方式 邻接矩阵 无向图邻接矩阵 有向图邻接矩阵 网的邻接矩阵 每个结点的出度？入度？度？ 图的边数？ 邻接表 每个结点的出度？入度？度？ 图的边数？ * * 例已知某网的邻接（出边）表，请画出该网络。 当邻接表的存储结构形成后，图便唯一确定！ 例题解析 * * 图的遍历 广度优先有哪些信誉好的足球投注网站 从图的某一结点出发，首先依次访问该结点的所有邻接顶点 V1, V2, …, Vn 再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点，重复此过程，直至所有顶点均被访问为止。 深度优先有哪些信誉好的足球投注网站 1、访问指定的起始顶点； 2、若当前访问的顶点的邻接顶点有未被访问的，则任选一个访问之；反之，退回到最近访问过的顶点；直到与起始顶点相通的全部顶点都访问完毕； 3、若此时图中尚有顶点未被访问，则再选其中一个顶点作为起始顶点并访问之，转 2； 反之，遍历结束。 * * 例题解析 * * 熟悉图的存储结构，画出右边有向图的邻接矩阵、邻接表、逆邻接表。写出邻接表表示的图从顶点A出发的深度优先遍历序列和广度优先遍历序列。 深度优先遍历序列为ABCFED，广度优先遍历序列为ABDCEF 邻接矩阵如下 邻接表如下 逆邻接表如下 【答】 最小生成树 普里姆（Prim）算法 将顶点进行归并 克鲁斯卡尔（Kru