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

,考试题型,单选：5题，共10分填空：5题，共10分简答题：5题，共45分算法阅读：15分算法设计：20分考试要求：闭卷,第1章概论,DS描述“按一定逻辑关系组织的数据元素的表示及相关操作数据逻辑结构：线性结构、树形结构和图形结构数据存储结构：顺序方法、链接方法、索引方法、散列方法抽象数据类型ADT算法4个特性：通用性、有效性、确定性、有穷性算法分析：T(n)、S(n)算法分析的相关概念；最差、最佳与平均情况的意义,ADT的定义,三元组表示ADT=(D,R,P)ADT抽象数据类型名数据对象D:数据关系R:基本操作P:ADT抽象数据类型名用C+类模板的声明表示ADT,ADT定义类模板,类模板代表一类类，不代表具体的类类模板的定义格式:template/类型参数Type,使用时用具体数据类型代替classclassNameprivate:TypedataList;public:methodName();C+引入模板概念，是想突出数据的逻辑结构而忽略其具体的数据类型,声明、定义和使用C+类模板(2),类模板：描述了一组相关的类，它们只能通过类型来区分1、类模板声明：仅提供了类的名称和类的模板参数template/类模板Array可接受任何类型作为参数classArrayElem*data;intsize;/声明类模板Array的类数据public:Array(intsz);/函数成员intGetSize();2、函数成员定义templateArray:Array(intsz)size=sz;data=newElemsize;templateintArray:GetSize()returnsize;3、类模板的用法Arrayint_array(100);/Array接收int作参数,/int_array为长100的int型数组对象,常见上限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-*/(错#leftchild();/访问左子树DepthOrder(root-rightchild();/访问右子树,Visit(root)/中序,Visit(root)/后序,生成二叉搜索树45,53,12,37,3,100,61,24,90,78,二叉搜索树的删除,在二叉搜索树里删除结点时，不是把以这个结点为根的子树都删除掉，只是删除一个结点，并且还要保持二叉搜索树的性质。删除过程分为两种情况：没有左子树有左子树,没有左子树,若结点p没有左子树，则用右子树的根代替被删除的结点p。,有左子树（改进）,若p(50)有左子树，则在左子树里找中序周游的最后一个结点s(40)，删除s，用s的左子树代替s，用s代替被删p这种方法可以降低二叉树的高度。,已知序列72,73,71,23,94,16,05,68建堆,72,最小堆的插入,插入过程：插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义,插入1320131413,最小堆的删除,用最后结点替换被删结点，自上至下调整成堆(最后结点被删结点,只影响其子树的最小堆性质),12,14,19,24,18,22,15,17,20,删除14142626192622,26,5.6Huffman树及其应用,外部路径长度li扩充二叉树从根到每个外部结点的路径长度之和外部路径长度最小的二叉树：是完全二叉树带权外部路径长度(weightedexternalpath)最小的二叉树：Huffman树要求给出一个具有n个外部结点的扩充二叉树每个外部结点Ki有一个wi与之对应，作为该外部结点的权此扩充二叉树的叶结点带权外部路径长度总和最小注意:不管内部结点，也不用有序特点：权越大的叶结点离根越近,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,与算法有关的典型例题,已知一棵二叉树的前序和中序（后序和中序）遍历序列，构造对应的二叉树通过二叉树，获得对应的树与森林的相关信息深度周游与广度周游二叉树,31,具有n个结点的满二叉树，其叶子结点的个数为_。(如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树,性质3.任何一棵二叉树，n0=n2+1)某棵二叉树的前序序列为ABDEFC，中序序列为DBFEAC，则该二叉树对应的后序序列的结果为_。五个分别带权值为9，2，5，7，12的叶子结点构造Huffman树，进行编码，并写出该树的带权外部路径长度WPL。,给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进算法），求ASL堆排序：给定关键码序列，建初堆。插入、删除结点后，调整为堆,第6章树,树与森林定义、ADT定义、基本操作树（森林）周游(深度优先、广度优先)先根次序周游森林=前序周游二叉树后根次序周游森林=中序周游二叉树树（森林）与二叉树的等价转换树与森林的链式存储结构动态“左子/右兄”二叉链表表示法,森林与二叉树的等价转换,森林由部分组成：森林中第一棵树的根结点森林中第一棵树的子树森林森林中其它树构成的森林,动态“左子/右兄”二叉链表表示法,35,|B|,|C|,|D|,|E|,|F|,|G|,|A|,6.1.4树的周游1、深度优先周游树,一.先根次序周游森林前序周游二叉树首棵树根；首棵树各子树；余下各树根；左子树；右子树依次从左至右对森林每棵树进行先序周游二.后根次序周游森林中序周游二叉树首棵树各子树；首棵树根；余下各树左子树；根；右子树依次从左至右对森林每棵树进行后序周游先序：ABCEFDGHJI后序：BEFCDAJHIG,带右链的先根次序表示法,这种表示法与llinkrlink表示法相比，用ltag代替了llink，占用的存储单元要少些，但并不丢失信息可以从结点的次序和ltag的值完全可以推知llinkltag=0:有左子，它的llink指向该结点数组右邻ltag=1:没有左子，它的llink为空,第7章图,有向图/网：弧、入/出度、有向完全图无向图/网：边、度、无向完全图图的ADT定义存储结构（相邻矩阵、邻接表）及类定义图周游算法（深度、广度）最小生成树（prim)、拓扑排序、单源最短路径（必须会严格按照算法手工走给定实例）,典型题目,能够完成拓扑排序的图一定是一个_。n个顶点的无向连通图至少有的边的条数是_。已知一个有向图的相邻矩阵表示，计算第i个结点的入度的方法是_。已知一个无向图的顶点集为a,b,c,d,e,其相邻矩阵如下所示：(1)画出该图的图形；0100110010000110110110110(2)根据此相邻矩阵，从顶点b出发进行深度优先周游和广度优先周游，写出相应周游的顶点序列。,第8章内排序,直接插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序、桶式排序、基数排序：手工排序每趟过程各种排序方法的性能对比(稳定性、时空)各种排序方法的适用场合、时间复杂度,排序算法的理论性能表8.3,在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（）。A.快速排序B.堆排序C.归并排序D.基数排序堆排序在最坏的情况下的时间复杂度是()。A.O(log2n)B.O(log2n2)C.O(nlog2n)D.O(n2),第10章检索,43,相关概念，ASL顺序查找、二分查找、分块查找散列表（常见的散列函数与解决冲突的方法，计算ASL）查找特点，构造方法,开散列方法拉链法,散列表中每个槽添加一个链表表头，当发生冲突时就拉出一条链，建立一个链表方式的同义词表，动态申请同义词空间例：77、7、110、95、14、75、62h(Key)=Key%11同义词表中同义词可按值的顺序,访问频率的顺序排列,ASL=(1/7)*(1*4+2*2+3*1),例如:关键码集合19,01,23,14,55,68,11,82,36,设定哈希函数H(key)=keyMOD11(表长=11),19,01,23,14,55,68,若采用线性探测法处理冲突，构造该散列表,11,82,36,112136