北京工业大学-数据结构-期末复习(课堂PPT).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,使用时用具体数据类型代替,class className,private:,Type dataList;,public:,methodName();,;,C+,引入模板概念，是想突出数据的逻辑结构而忽略其具体的数据类型,5,声明、定义和使用,C+,类模板,(2),类模板：描述了一组相关的类，它们只能通过类型来区分,1,、类模板声明：仅提供了类的名称和类的模板参数,template,/,类模板,Array,可接受任何类型作为,参数,class Array Elem*data;,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(logn)O(n)O(nlogn)O(n,2,),常数阶 对数 线性 对数乘积 平方,O(n,3,),.O(2,n,)O(n!),立方 指数 阶乘,常数：,g(n)=1,对数：,g(n)=logn,线性增长：,g(n)=n,二阶增长：,g(n)=n,2,g(n)=nlog(n),n=nlog(n),增长率,-,*,/,(,错,#,#,，入栈,#/,4,.,2,(,入栈,#/,（,2,b,输出,b,ab,1,-,-(,，入栈,#/,（,-,4,.,2,c,输出,c,abc,1,),-,出栈输出,直至,(,#/,（,abc-,3.2,)=(,出栈不输出,#/,3,.2,+,+#,，入栈,#+,4,.2,d,输出,d,abc-/d,1,*,*+,，入栈,#+*,4,.2,e,输出,e,abc-/de,1,#,连续出栈输出,abc-/de*+,5,16,后缀表达式求值,循环：依次分析输入序列：,1.,输入是操作数：则入栈；,2.,输入是运算符：则,两次出栈，,取操作数,2,和操作数,1,，按照运算符进行,计算,。将,结果入栈,。,重复，直至遇到结束符,“,=,”,此时栈顶值就是输入表达式的值。,17,第,4,章 字符串,(,了解）,基本概念,存储结构（顺序、标准类）,基本操作的含义,18,第,5,章 二叉树,定义、,性质,、存储结构（相应的类定义）,满二叉树、完全二叉树及扩充二叉树,抽象数据类型定义中的基本操作含义,深度周游（递归与非递归），广度周游,二叉搜索树,插入、删除（改进）与检索算法；必须能够跟踪执行过程；求,ASL,。,堆,概念、建堆、筛选、插、删的相关算法,(,过程,),Huffman,树,构造及,Huffman,编码,19,深度优先周游二叉树（递归实现）,template,void BinaryTree:,PreOrder (BinaryTreeNode*root),if(root!=NULL),Visit(root-value();,/,前序,DepthOrder(root-leftchild();/,访问左子树,DepthOrder(root-rightchild();/,访问右子树,Visit,(root),/,中序,Visit,(root),/,后序,20,45,12,53,3,24,100,90,61,37,生成二叉搜索树,45,53,12,37,3,100,61,24,90,78,78,21,二叉搜索树的删除,在二叉搜索树里删除结点时，不是把以这个结点为根的子树都删除掉，只是删除一个结点，并且还要保持二叉搜索树的性质。,删除过程分为两种情况：,没有左子树,有左子树,22,没有左子树,若结点,p,没有左子树，则用右子树的根代替被删除的结点,p,。,50,30,80,20,90,85,40,35,88,32,50,30,20,90,85,40,35,88,32,23,有左子树（改进）,若,p(50),有左子树，则在左子树里找中序周游的最后一个结点,s(40),，,删除,s,，用,s,的左子树代替,s,，用,s,代替被删,p,这种方法可以降低二叉树的高度。,50,30,80,20,90,85,40,35,88,32,40,30,80,20,90,85,35,32,88,24,已知序列,72,73,71,23,94,16,05,68,建堆,72,25,最小堆的插入,插入过程：插入点追加到最后，,自下而上,依次比较,父与子,，直到满足堆的定义,12,14,19,24,18,13,22,15,17,26,20,12,14,19,24,18,20,22,15,17,26,13,12,13,19,24,18,20,22,15,17,26,14,插入,13 20,13 1413,26,最小堆的删除,用最后结点,替换,被删结点，,自上至下,调整成堆,(,最后结点,被删结点,只影响其子树的最小堆性质,),12,14,19,24,18,22,15,17,26,20,删除,14,14,262619 2622,26,12,19,26,24,18,22,15,17,20,12,19,22,24,18,26,15,17,20,27,5.6 Huffman,树及其应用,外部路径长度,li,扩充二叉树从根到每个外部结点的路径长度之和,外部路径长度最小的二叉树：是完全二叉树,带权外部路径长度,(weighted external path),最小的二叉树：,Huffman,树,要求给出一个具有,n,个外部结点的扩充二叉树,每个外部结点,K,i,有一个,w,i,与之对应，作为该外部结点的权,此扩充二叉树的叶结点带权外部路径长度,总和最小,注意,:,不管内部结点,，也不用有序,特点：,权越大的叶结点离根越近,28,3,5,29,14,7,8,c3,d4,e5,23,f6,11,h8,b2,8,15,19,29,42,58,100,建树,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,与算法有关的典型例题,已知一棵二叉树的前序和中序（后序和中序）遍历序列，构造对应的二叉树,通过二叉树，获得对应的树与森林的相关信息,深度周游与广度周游二叉树,30,31,具有,n,个结点的满二叉树，其叶子结点的个数为,_,。,(,如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树,性质,3.,任何一棵二叉树，,n,0,=n,2,+1,),某棵二叉树的前序序列为,ABDEFC,，中序序列为,DBFEAC,，则该二叉树对应的后序序列的结果为,_,。,五个分别带权值为,9,，,2,，,5,，,7,，,12,的叶子结点构造,Huffman,树，进行编码，并写出该树的,带权外部路径长度,WPL,。,31,给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进算法），求,ASL,堆排序：,给定关键码序列，建初堆。,插入、删除结点后，调整为堆,32,第,6,章 树,树与森林定义、,ADT,定义、基本操作,树（森林）周游,(,深度优先、广度优先,),先根次序周游森林,=,前序周游二叉树,后根次序周游森林,=,中序周游二叉树,树（森林）与二叉树的等价转换,树与森林的链式存储结构,动态,“,左子,/,右兄,”,二叉链表表示法,33,森林与二叉树的等价转换,森林由部分组成：,森林中第一棵树的根结点,森林中第一棵树的子树森林,森林中其它树构成的森林,34,动态,“,左子,/,右兄,”,二叉链表表示法,35,D,A,B,C,E,F,G,|B|,|C|,|D|,|E|,|F|,|G|,|A|,35,6.1.4,树的周游,1,、深度优先周游树,一,.,先根次序周游森林,前序,周游,二叉树,首棵树根；首棵树各子树；余下各树,根；左子树；右子树,依次从左至右对森林每棵,树,进行,先序周游,二,.,后根次序周游森林,中序,周游,二叉树,首棵树各子树；首棵树根；余下各树,左子树；根；右子树,依次从左至右对森林每棵,树,进行,后序,周游,先序：,ABCEFD GHJI,后序：,BEFCDA JHIG,A,B,C,F,E,D,G,H,J,I,A,B,G,H,C,E,F,I,D,J,36,带右链的先根次序表示法,这种表示法与,llinkrlink,表示法相比，用,ltag,代替了,llink,，占用的存储单元要少些，但并不丢失信息,可以从结点的次序和,ltag,的值完全可以推知,llink,ltag=0:,有左子，它的,llink,指向该结点数组右邻,ltag=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,0 0 0 1 1,0 1 1 0 1,1 0 1 1 0,(2),根据此相邻矩阵，从顶点,b,出发进行深度优先周游和广度优先周游，写出相应周游的顶点序列。,39,第,8,章 内排序,直接插入排序、冒泡排序、,快速排序,、直接选择排序、,堆排序,、归并排序、桶式排序、基数排序：手工排序每趟过程,各种排序方法的性能对比,(,稳定性、时空,),各种排序方法的适用场合、时间复杂度,40,算法,最大时间,平均时间,最小时间,S(n),稳定性,直接插入排序,(n,2,),(n,2,),(n),(1),稳定,冒泡排序,(n,2,),(n,2,),(n),(1),稳定,直接选择排序,(n,2,),(n,2,),(n,2,),(1),不稳定,Shell,排序,(n,3/2,),(n,3/2,),(n,3/2,),(1),不稳定,快速排序,(n,2,),(nlog n),(nlog n),(log n),不稳定,归并排序,(nlog n),(nlog n),(nlog n),(n),稳定,堆排序,(nlog n),(nlog n),(nlog n),(1),不稳定,桶式排序,(n+m),(n+m),(n+m),(n+m),稳定,基数排序,(d(n+r),(d(n+r),(d(n+r),(n+r),稳定,排序算法的理论性能 表,8.3,41,在下列排序方法中，平均时间性能为,O(nlogn),且空间性能最好的是（）。,A.,快速排序,B.,堆排序,C.,归并排序,D.,基数排序,堆排序在最坏的情况下的时间复杂度是,(),。,A.O(log,2,n)B.O(log,2,n,2,),C.O(nlog,2,n)D.O(n,2,),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,MOD,11(,表长,=11),19,01,23,14,55,68,若采用线性探测法处理冲突，构造该散列表,11,82,36,1 1 2 1 3 6 2 5 1,45,第,11,章 索引技术（了解概念）,稠密索引、稀疏索引的适用场合。,线性索引,静态索引,倒排索引,动态索引,各种索引关键概念、特点、适用场合,46,第,12,章 高级数据结构,多维数组,压缩存储：三元组表，十字链表,广义表概念，存储,平衡二叉搜索树（目的）,ASL,47,根据数据状态及实际应该背景，抽象数学模型，选择数据结构、存储方法，设计算法并实现。,类定义：,抽象类定义,根据具体存储结构定义子类,48,