北京工业大学 数据结构 期末复习ppt课件

1、,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+

2、类模板的声明表示ADT,4,ADT定义类模板,类模板代表一类类，不代表具体的类 类模板的定义格式: template /类型参数Type,使用时用具体数据类型代替 class className private: Type dataList; public: methodName( ); ; C+引入模板概念，是想突出数据的逻辑结构而忽略其具体的数据类型,5,声明、定义和使用 C+类模板(2),类模板：描述了一组相关的类，它们只能通过类型来区分 1、类模板声明：仅提供了类的名称和类的模板参数 template /类模板 Array 可接受任何类型作为参数 class Array Elem* d

3、ata; int size; /声明类模板Array的类数据 public: Array( int sz ) ; /函数成员 int GetSize( ) ; ; 2、函数成员定义 template Array:Array( int sz ) size = sz; data = new Elemsize; template int Array:GetSize( ) return size; 3、类模板的用法 Array int_array(100); /Array接收int作参数, /int_array为长100的int型数组对象,6,常见上限g(n)的种类(用于比较各算法优劣),O(1)O(

4、logn)O(n)O(nlogn)O(n2) 常数阶 对数 线性 对数乘积 平方 O(n3).O(2n)O(n!) 立方 指数 阶乘 常数：g(n) = 1 对数：g(n) = logn 线性增长： g(n) = n 二阶增长： g(n) = n2 g(n) = nlog(n), n = nlog(n)增长率 = n2 指数增长： g(n) = an,7,题型举例,算法指的是（ ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法D. 解决问题的有限运算序列 将长度为 n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 ( ) 。 A. O( n ) B. O( 1 ) C

5、. O( m )D. O( m + n ),8,第2章 线性表,清楚线性表定义、理解类定义及抽象数据类型中定义的各个基本操作含义 存储形式：顺序存储结构、链式存储结构 顺序存储结构的特点： 1.逻辑结构与物理结构一致； 2.属于随机存取方式 缺点：插入删除元素需要移动，平均约一半的元素， 限制了长度变化 链式存储结构的特点： 1.逻辑结构与物理结构不一致； 2.属于顺序存取方式,9,2.1.2 线性表的存储结构,逻辑结构存储空间 的映射 数据存储单元 建立映射 关系存储单元之间关系 建立映射 线性表2类存储结构 顺序存储（定长的一维数组结构、向量型顺序存储结构 ） 为整个元素动态分配连续空间

6、特点：逻辑相邻物理也相邻 链式存储（变长的线性表存储结构） 按需分配(插入:分配一个结点/删除:回收一结点) 特点：逻辑相邻物理不一定相邻,10,链表单向、循环、双向,不特殊说明，均带头结点(避免对空表的特殊处理) 算法：（时间复杂性） 在有序表中插入/删除结点 给定元素位置，插入/删除相应结点 注意： 对循环链表操作时，尾部的判断 双向链表的插入/删除结点 删除结点一定要释放空间,11,2.4 线性表实现方法的比较,顺序表优点 存储紧凑（逻辑结构由存储相对位置体现，没使用指针，不用花费附加开销 ） 随机访问（给定下标,常量时间可定位） 链表优点 不限定长度（无需事先了解线性表的长度，允许线性

7、表的长度有很大变化 ） 不必移动，仅需改指针即可插删（能够适应经常插入删除内部元素的情况 ） 适用 不能确定长度上限、频繁插删：用链式存储结构 按位置频繁进行读取、数据域占用空间小于指针域：用顺序存储结构,12,有序的顺序表与无序的顺序表相比，其操作优势是（ ）。 A. 删除快 B. 插入快 C. 生成快 D. 查找快。 若对线性表进行的主要操作是按下标存取，且很少插入和删除，则应该采用的存储结构是_；若需要频繁地对线性表进行插入和删除时，则应该采用的存储结构是 。,题型举例,13,第3章 栈与队列,栈与队列的定义、ADT定义及基本操作。 栈的应用：会跟踪递归函数执行过程 深度（纵向）周游 表

8、达式求值(中缀后缀求值) 队列的应用：按层周游 注意：熟悉ADT的操作形式，会直接调用抽象数据类型中定义的操作,14,算符优先关系表,+ - * / ( ) # + - * / ( 错 # =,左,右,15,a/(b-c)+d*e# abc-/de*+,16,后缀表达式求值,循环：依次分析输入序列： 1.输入是操作数：则入栈； 2.输入是运算符：则两次出栈，取操作数2和操作数1，按照运算符进行计算。将结果入栈。 重复，直至遇到结束符“=” 此时栈顶值就是输入表达式的值。,17,第 4 章 字符串(了解）,基本概念 存储结构（顺序、标准类） 基本操作的含义,18,第5章 二叉树,定义、性质、存储

9、结构（相应的类定义） 满二叉树、完全二叉树及扩充二叉树 抽象数据类型定义中的基本操作含义 深度周游（递归与非递归），广度周游 二叉搜索树插入、删除（改进）与检索算法；必须能够跟踪执行过程；求ASL。 堆概念、建堆、筛选、插、删的相关算法(过程) Huffman树构造及Huffman编码,19,深度优先周游二叉树（递归实现）,template void BinaryTree:PreOrder (BinaryTreeNode* root) if(root!=NULL) Visit(root-value( );/前序 DepthOrder(root-leftchild(); /访问左子树 Depth

10、Order(root-rightchild();/访问右子树 ,Visit( root ) /中序,Visit( root ) /后序,20,生成二叉搜索树 45,53,12,37,3,100,61,24,90,78,21,二叉搜索树的删除,在二叉搜索树里删除结点时，不是把以这个结点为根的子树都删除掉，只是删除一个结点，并且还要保持二叉搜索树的性质。 删除过程分为两种情况： 没有左子树 有左子树,22,没有左子树,若结点p没有左子树，则用右子树的根代替被删除的结点p。,23,有左子树（改进）,若p(50)有左子树，则在左子树里找中序周游的最后一个结点s(40)，删除s，用s的左子树代替s，用s

11、代替被删p 这种方法可以降低二叉树的高度。,24,已知序列72,73,71,23,94,16,05,68 建堆,72,25,最小堆的插入,插入过程：插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义,插入13 2013 1413,26,最小堆的删除,用最后结点替换被删结点，自上至下调整成堆 (最后结点被删结点,只影响其子树的最小堆性质),12,14,19,24,18,22,15,17,20,删除14 14262619 2622,26,27,5.6 Huffman树及其应用,外部路径长度li 扩充二叉树从根到每个外部结点的路径长度之和 外部路径长度最小的二叉树：是完全二叉树 带权外部路径

12、长度(weighted external path)最小的二叉树：Huffman树 要求给出一个具有n个外部结点的扩充二叉树 每个外部结点Ki有一个wi与之对应，作为该外部结点的权 此扩充二叉树的叶结点带权外部路径长度总和最小 注意:不管内部结点，也不用有序 特点：权越大的叶结点离根越近,28,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: 0001 b:10 c:1110 d:1111 f:01 g:0000 h:001,29,与算法有关的典型例题,已知一棵二叉树的前序和中序（后序和中序）遍历序列，

13、构造对应的二叉树 通过二叉树，获得对应的树与森林的相关信息 深度周游与广度周游二叉树,30,31,具有n个结点的满二叉树，其叶子结点的个数为_。(如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 ,性质3.任何一棵二叉树，n0 = n2+1) 某棵二叉树的前序序列为ABDEFC，中序序列为DBFEAC，则该二叉树对应的后序序列的结果为_。 五个分别带权值为9，2，5，7，12 的叶子结点构造Huffman树，进行编码，并写出该树的带权外部路径长度WPL。,31,给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进算法），求ASL 堆排序： 给定关键

14、码序列，建初堆。 插入、删除结点后，调整为堆,32,第6章 树,树与森林定义、ADT定义、基本操作 树（森林）周游(深度优先、广度优先) 先根次序周游森林 = 前序周游二叉树 后根次序周游森林 = 中序周游二叉树 树（森林）与二叉树的等价转换 树与森林的链式存储结构 动态“左子/右兄”二叉链表表示法,33,森林与二叉树的等价转换,森林由部分组成： 森林中第一棵树的根结点 森林中第一棵树的子树森林 森林中其它树构成的森林,34,动态“左子/右兄”二叉链表表示法,35, | B |, | C |, | D | ,| E | , |F |, | G | , | A | ,35,6.1.4 树的周游

15、1、深度优先周游树,一.先根次序周游森林前序周游二叉树 首棵树根；首棵树各子树；余下各树 根； 左子树； 右子树 依次从左至右对森林每棵树进行先序周游 二.后根次序周游森林中序周游二叉树 首棵树各子树；首棵树根；余下各树 左子树； 根； 右子树 依次从左至右对森林每棵树进行后序周游 先序：ABCEFD GHJI 后序：BEFCDA JHIG,36,带右链的先根次序表示法,这种表示法与llinkrlink表示法相比，用ltag代替了llink，占用的存储单元要少些，但并不丢失信息 可以从结点的次序和ltag的值完全可以推知llink ltag= =0:有左子，它的llink指向该结点数组右邻 l

16、tag= =1:没有左子，它的llink为空,37,第7章 图,有向图/网：弧、入/出度、有向完全图 无向图/网：边、度、无向完全图 图的ADT定义 存储结构（相邻矩阵、邻接表）及类定义 图周游算法（深度、广度） 最小生成树（prim)、拓扑排序、单源最短路径（必须会严格按照算法手工走给定实例）,38,典型题目,能够完成拓扑排序的图一定是一个_。 n个顶点的无向连通图至少有的边的条数是_。 已知一个有向图的相邻矩阵表示，计算第i个结点的入度的方法是_。 已知一个无向图的顶点集为 a, b, c, d, e , 其相邻矩阵如下所示： (1)画出该图的图形； 0 1 0 0 1 1 0 0 1 0

17、 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 (2)根据此相邻矩阵，从顶点 b 出发进行深度优先周游和广度优先周游，写出相应周游的顶点序列。,39,第 8 章 内排序,直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、桶式排序、基数排序：手工排序每趟过程 各种排序方法的性能对比(稳定性、时空) 各种排序方法的适用场合、时间复杂度,40,排序算法的理论性能 表8.3,41,在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序 堆排序在最坏的情况下的时间复杂度是 ( )。 A. O(

18、 log2 n ) B. O( log2 n2 ) C. O( nlog2 n ) D. O( n2 ),42,第10章 检索,43,相关概念，ASL 顺序查找、二分查找、分块查找 散列表（常见的散列函数与解决冲突的方法，计算ASL）查找特点，构造方法,43,开散列方法 拉链法,散列表中每个槽添加一个链表表头，当发生冲突时就拉出一条链，建立一个链表方式的同义词表，动态申请同义词空间 例：77、7、110、95、14、75、62 h(Key) = Key % 11 同义词表中同义词可按值的顺序,访问频率的顺序排列,ASL = (1/7)*(1*4+2*2+3*1),44,例如: 关键码集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,设定哈希函数 H(key) = key