北京工业大学数据结构复习PPT课件

1 考试题型 单选 5题 共10分填空 5题 共10分简答题 5题 共45分算法阅读 15分算法设计 20分考试要求 闭卷 2 第1章概论 DS描述 按一定逻辑关系组织的数据元素的表示及相关操作数据逻辑结构 线性结构 树形结构和图形结构数据存储结构 顺序方法 链接方法 索引方法 散列方法抽象数据类型ADT算法4个特性 通用性 有效性 确定性 有穷性算法分析 T n S n 算法分析的相关概念 最差 最佳与平均情况的意义 3 ADT的定义 三元组表示ADT D R P ADT抽象数据类型名 数据对象D 数据关系R 基本操作P ADT抽象数据类型名用C 类模板的声明表示ADT 4 ADT定义类模板 类模板代表一类类 不代表具体的类类模板的定义格式 template 类型参数Type 使用时用具体数据类型代替classclassName private TypedataList public methodName C 引入模板概念 是想突出数据的逻辑结构而忽略其具体的数据类型 5 声明 定义和使用C 类模板 2 类模板 描述了一组相关的类 它们只能通过类型来区分1 类模板声明 仅提供了类的名称和类的模板参数template 类模板Array可接受任何类型作为参数classArray Elem data intsize 声明类模板Array的类数据public Array intsz 函数成员intGetSize 2 函数成员定义templateArray Array intsz size sz data newElem size templateintArray GetSize returnsize 3 类模板的用法Arrayint array 100 Array接收int作参数 int array为长100的int型数组对象 6 常见上限g n 的种类 用于比较各算法优劣 O 1 O logn O n O nlogn O n2 常数阶对数线性对数乘积平方 O n3 O 2n O n 立方指数阶乘常数 g n 1对数 g n logn线性增长 g n n二阶增长 g n n2g n nlog n n nlog n 增长率 n2指数增长 g n an 7 题型举例 算法指的是 A 计算机程序B 解决问题的计算方法C 排序算法D 解决问题的有限运算序列将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为 A O n B O 1 C O m D O m n 8 第2章线性表 清楚线性表定义 理解类定义及抽象数据类型中定义的各个基本操作含义存储形式 顺序存储结构 链式存储结构顺序存储结构的特点 1 逻辑结构与物理结构一致 2 属于随机存取方式缺点 插入 删除元素需要移动 平均约一半的元素 限制了长度变化链式存储结构的特点 1 逻辑结构与物理结构不一致 2 属于顺序存取方式 9 2 1 2线性表的存储结构 逻辑结构 存储空间的映射数据 存储单元建立映射关系 存储单元之间关系建立映射线性表2类存储结构顺序存储 定长的一维数组结构 向量型顺序存储结构 为整个元素动态分配连续空间特点 逻辑相邻物理也相邻链式存储 变长的线性表存储结构 按需分配 插入 分配一个结点 删除 回收一结点 特点 逻辑相邻物理不一定相邻 10 链表 单向 循环 双向 不特殊说明 均带头结点 避免对空表的特殊处理 算法 时间复杂性 在有序表中插入 删除结点给定元素位置 插入 删除相应结点注意 对循环链表操作时 尾部的判断双向链表的插入 删除结点删除结点一定要释放空间 11 2 4线性表实现方法的比较 顺序表优点存储紧凑 逻辑结构由存储相对位置体现 没使用指针 不用花费附加开销 随机访问 给定下标 常量时间可定位 链表优点不限定长度 无需事先了解线性表的长度 允许线性表的长度有很大变化 不必移动 仅需改指针即可插删 能够适应经常插入删除内部元素的情况 适用不能确定长度上限 频繁插删 用链式存储结构按位置频繁进行读取 数据域占用空间小于指针域 用顺序存储结构 12 有序的顺序表与无序的顺序表相比 其操作优势是 A 删除快B 插入快C 生成快D 查找快 若对线性表进行的主要操作是按下标存取 且很少插入和删除 则应该采用的存储结构是 若需要频繁地对线性表进行插入和删除时 则应该采用的存储结构是 题型举例 13 第3章栈与队列 栈与队列的定义 ADT定义及基本操作 栈的应用 会跟踪递归函数执行过程 深度 纵向 周游表达式求值 中缀 后缀 求值 队列的应用 按层周游注意 熟悉ADT的操作形式 会直接调用抽象数据类型中定义的操作 14 a b c d e abc de 15 后缀表达式求值 循环 依次分析输入序列 1 输入是操作数 则入栈 2 输入是运算符 则两次出栈 取操作数2和操作数1 按照运算符进行计算 将结果入栈 重复 直至遇到结束符 此时栈顶值就是输入表达式的值 16 第4章字符串 了解 基本概念存储结构 顺序 标准类 基本操作的含义 17 第5章二叉树 定义 性质 存储结构 相应的类定义 满二叉树 完全二叉树及扩充二叉树抽象数据类型定义中的基本操作含义深度周游 递归与非递归 广度周游二叉搜索树插入 删除 改进 与检索算法 必须能够跟踪执行过程 求ASL 堆概念 建堆 筛选 插 删的相关算法 过程 Huffman树构造及Huffman编码 18 深度优先周游二叉树 递归实现 templatevoidBinaryTree PreOrder BinaryTreeNode root if root NULL Visit root value 前序DepthOrder root leftchild 访问左子树DepthOrder root rightchild 访问右子树 Visit root 中序 Visit root 后序 19 生成二叉搜索树45 53 12 37 3 100 61 24 90 78 20 二叉搜索树的删除 在二叉搜索树里删除结点时 不是把以这个结点为根的子树都删除掉 只是删除一个结点 并且还要保持二叉搜索树的性质 删除过程分为两种情况 没有左子树有左子树 21 没有左子树 若结点p没有左子树 则用右子树的根代替被删除的结点p 22 有左子树 改进 若p 50 有左子树 则在左子树里找中序周游的最后一个结点s 40 删除s 用s的左子树代替s 用s代替被删p这种方法可以降低二叉树的高度 23 已知序列72 73 71 23 94 16 05 68建堆 72 24 最小堆的插入 插入过程 插入点追加到最后 自下而上依次比较父与子 直到满足堆的定义 插入1320 1314 13 25 最小堆的删除 用最后结点替换被删结点 自上至下调整成堆 最后结点 被删结点 只影响其子树的最小堆性质 12 14 19 24 18 22 15 17 20 删除1414 2626 1926 22 26 26 5 6Huffman树及其应用 外部路径长度li扩充二叉树从根到每个外部结点的路径长度之和外部路径长度最小的二叉树 是完全二叉树带权外部路径长度 weightedexternalpath 最小的二叉树 Huffman树要求给出一个具有n个外部结点的扩充二叉树每个外部结点Ki有一个wi与之对应 作为该外部结点的权此扩充二叉树的叶结点带权外部路径长度总和最小注意 不管内部结点 也不用有序特点 权越大的叶结点离根越近 27 3 5 29 14 7 8 c3 d4 e5 23 f6 11 h8 b2 建树 g7 a下标 1 1 0 1 0 1 1 0 0 0 a 0001b 10c 1110d 1111f 01g 0000h 001 28 与算法有关的典型例题 已知一棵二叉树的前序和中序 后序和中序 遍历序列 构造对应的二叉树 通过二叉树 获得对应的树与森林的相关信息深度周游与广度周游二叉树 29 29 具有n个结点的满二叉树 其叶子结点的个数为 如果一棵二叉树的任何结点 或者是树叶 或者恰有两棵非空子树 则此二叉树称作满二叉树 性质3 任何一棵二叉树 n0 n2 1 某棵二叉树的前序序列为ABDEFC 中序序列为DBFEAC 则该二叉树对应的后序序列的结果为 五个分别带权值为9 2 5 7 12的叶子结点构造Huffman树 进行编码 并写出该树的带权外部路径长度WPL 30 给定关键码序列 创建二叉搜索树 并删除某个结点 按照教材中的改进算法 求ASL堆排序 给定关键码序列 建初堆 插入 删除结点后 调整为堆 31 第6章树 树与森林定义 ADT定义 基本操作树 森林 周游 深度优先 广度优先 先根次序周游森林 前序周游二叉树后根次序周游森林 中序周游二叉树树 森林 与二叉树的等价转换树与森林的链式存储结构动态 左子 右兄 二叉链表表示法 32 森林与二叉树的等价转换 森林由 部分组成 森林中第一棵树的根结点森林中第一棵树的子树森林森林中其它树构成的森林 33 动态 左子 右兄 二叉链表表示法 33 B C D E F G A 34 6 1 4树的周游1 深度优先周游树 一 先根次序周游森林 前序周游二叉树首棵树根 首棵树各子树 余下各树根 左子树 右子树依次从左至右对森林每棵树进行先序周游二 后根次序周游森林 中序周游二叉树首棵树各子树 首棵树根 余下各树左子树 根 右子树依次从左至右对森林每棵树进行后序周游先序 ABCEFDGHJI后序 BEFCDAJHIG 35 带右链的先根次序表示法 这种表示法与llink rlink表示法相比 用ltag代替了llink 占用的存储单元要少些 但并不丢失信息可以从结点的次序和ltag的值完全可以推知llinkltag 0 有左子 它的llink指向该结点数组右邻ltag 1 没有左子 它的llink为空 36 第7章图 有向图 网 弧 入 出度 有向完全图无向图 网 边 度 无向完全图图的ADT定义存储结构 相邻矩阵 邻接表 及类定义图周游算法 深度 广度 最小生成树 prim 拓扑排序 单源最短路径 必须会严格按照算法手工走给定实例 37 典型题目 能够完成拓扑排序的图一定是一个 n个顶点的无向连通图至少有的边的条数是 已知一个有向图的相邻矩阵表示 计算第i个结点的入度的方法是 已知一个无向图的顶点集为 a b c d e 其相邻矩阵如下所示 1 画出该图的图形 0100110010000110110110110 2 根据此相邻矩阵 从顶点b出发进行深度优先周游和广度优先周游 写出相应周游的顶点序列 38 第8章内排序 直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 归并排序 桶式排序 基数排序 手工排序每趟过程各种排序方法的性能对比 稳定性 时空 各种排序方法的适用场合 时间复杂度 39 排序算法的理论性能表8 3 40 在下列排序方法中 平均时间性能为O nlogn 且空间性能最好的是 A 快速排序B 堆排序C 归并排序D 基数排序堆排序在最坏的情况下的时间复杂度是 A O log2n B O log2n2 C O nlog2n D O n2 41 第10章检索 41 相关概念 ASL顺序查找 二分查找 分块查找散列表 常见的散列函数与解决冲突的方法 计算ASL 查找特点 构造方法 42 开散列方法拉链法 散列表中每个槽添加一个链表表头 当发生冲突时就拉出一条链 建立一个链表方式的同义词表 动态申请同义词空间例 77 7 110 95 14 75 62 h Key Key 11同义词表中同义词可按值的顺序 访问频率的顺序排列 ASL 1 7 1 4 2 2 3 1 43 例如 关键码集合 19 01 23 14 55 68 11 82 36 设定哈希函数H key k