数据结构复习指导-省名师优质课赛课获奖课件市赛课百校联赛优质课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。不能作为科学依据。,数据结构复习纲领,1/70,1,第,1,章 概论,基本术语,：程序、数据结构、算法、数据逻辑结构、数据存放结构、抽象数据类型。,算法,：,4,个特征（通用性、有效性、确定性、有穷性）,算法分析：,算法分析相关概念；渐进分析方法以及,3,个符号（,O,，,，,）含义；最差、最正确与平均情况意义,2/70,2,逻辑结构：,线性结构、树形结构和图形结构,存放结构：,次序方法、链接方法、索引方法、散列方法,3/70,3,将长度为,n,单链表接在长度为,m,单链表之后算法时间复杂度为,(),。,A.O(n),B.,O(1),C.O(m),D.O(m+n),4/70,4,抽象数据类型与数据结构定义区分在于,。,数据逻辑结构主要描述元素之间逻辑关系，它独立于数据,_,。,数据结构基本存放方式有与,_,。,算法分析主要内容是分析算法,_,。,5/70,5,第,2,章 线性表,清楚线性表定义、了解类定义及抽象数据类型中定义各个基本操作含义,存放形式：次序存放结构与链式存放结构,次序存放结构特点,：,1.,逻辑结构与物理结构一致；,2.,属于随机存取方式,缺点：插入,删除元素需要移动，平均约二分之一元素，,限制了长度改变,链式存放结构特点,：,1.,逻辑结构与物理结构不一致；,2.,属于次序存取方式,6/70,6,次序表和有序表,次序表,：线性表采取次序存放结构表示,(,向量,),有序表,：内容按从小到大排列线性表,算法,：,（时间复杂性）,在有序表中插入,/,删除一个元素使其仍有序,在给定位置插入,/,删除一个元素,7/70,7,链表,单向、循环、双向,不特殊说明，均带头结点,算法,：（时间复杂性）,在有序表中插入,/,删除结点,给定元素位置，插入,/,删除对应结点,注意,：,对循环链表操作时，尾部判断,双向链表插入,/,删除结点,删除结点一定要释放空间,线性表实现方法比较（教材,2.4,）,8/70,8,有序次序表与无序次序表相比，其操作优势是（）。,A.,删除快,B.,插入快,C.,生成快,D,.,查找快,9/70,9,线性表链式存放结构主要包含,_,、,_,、,_,三种形式。,线性表次序存放是经过,_,来表示数据元素之间逻辑关系，而链式存放结构是经过,_,表示数据元素之间逻辑关系。,单链表带头结点目标是,_,。,10/70,10,若对线性表进行主要操作是按照下标存取，且极少插入和删除，则应该采取存放结构是,；若需要频繁地对线性表进行插入和删除时，则应该采取存放结构是,。,11/70,11,第,3,章 栈与队列,栈与队列,定义、抽象数据类型定义及基本操作,。,栈应用：*会跟踪递归函数执行过程,*深度（纵向）周游,*表示式,（掌握后缀表示式计算中栈应用）,队列应用：按层周游,注意：,熟悉,ADT,操作形式，会直接调用抽象数据类型中定义操作,12/70,12,栈经典题,判回文、判表示式括号是否匹配（,思绪,）,给定一个中缀表示式，按照教材给出算法转换为后缀表示式（,掌握,）,给定后缀表示式，按照教材上给出算法,跟踪,计算后缀表示式过程（,掌握,）,13/70,13,假设入栈次序为,1234,，则以下不可能出现出栈序列为：,4321 3421 1234 3412,给定一个序列,ssxxssxxxxsxsxxxssss,s,代表入栈，,x,代表出栈，这是正当操作序列吗？,14/70,14,栈和队列共同点是,。,A.,都是先进后出,B.,都是先进先出,C.,只允许在端点处插入和删除元素,D.,没有共同点,15/70,15,仅允许在一端进行插入删除线性表称为,。,设元素,15,，,25,，,35,和,45,入队，然后三个元素出队，此时留在队列里元素是,。,16/70,16,设数组,data m,作为循环队列,SQ,存放空间，,front,为队头指针，,rear,为队尾指针，则执行出队操作后其头指针,front,值为,(),。,A.SQ.front=SQ.front+1,B.SQ.front=(SQ.front+1)%(m 1),C.SQ.front=(SQ.front 1)%m,D,.SQ.front=(SQ.front+1)%m,17/70,17,若已知一个栈入栈序列是,1,2,n.,其出栈序列为,p,1,p,2,p,n,。若,p,1,=n,，,则,p,i,为（）。,A.i,B.n-i,C,.n-i+1,D.,不确定,18/70,18,给定表示式,23+(34*45)/(5+6+7),（,1,）将其转换成后缀表示式,（,2,）跟踪后缀表示式计算过程,19/70,19,void,DFS(Graph G,int,v,int,mark),visitedv=mark;,coutv;,for,(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w),if,(!visitedw)DFS(G,w,mark);,/DFS,递归算法阅读,20/70,20,void,programXP(Graph G,int,&visited),for,(v=0;vG.vexnum;+v),visitedv=0;/,访问标志数组初始化,s=0;,for,(v=0;vG.vexnum;+v),if,(!visitedv),s+;,DFS(G,v,s);,21/70,21,（,1,）写出运行,programXP(),算法后,visited,最终止果,（,2,）简述这个算法功效,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,22/70,22,第,4,章 字符串,(,了解）,基本概念,存放结构（次序、标准类）,基本操作含义,23/70,23,第,5,章 二叉树,基本概念,定义、性质、存放结构,（对应类定义）,满二叉树、完全二叉树及扩充二叉树,抽象数据类型定义中基本操作含义,深度周游（递归与非递归），广度周游,二叉搜索树插入、删除（改进）与检索算法。必须能够跟踪执行过程。,堆概念、建堆与调整堆相关算法（过程）,Huffman,树及,Huffman,编码,24/70,24,与算法相关经典例题,已知一棵二叉树前序和中序（后序和中序）遍历序列，结构对应二叉树,经过二叉树，取得对应树与森林相关信息,深度周游与广度周游二叉树,二叉搜索树与堆相关算法要能够依据给定实例写出执行过程,25/70,25,仅知二叉树先序序列“,abcdefg,”,不能唯一确定一棵二叉树,由二叉树先序和中序序列建树,假如同时已知二叉树中序序列“,cbdaegf,”,则会怎样？,二叉树先序序列,二叉树中序序列,左子树,左子树,右子树,右子树,根,根,26/70,a b c d e,f,g,c b d a e g f,比如,:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列,中序序列,27/70,某棵二叉树前序序列为,ABDEFC,，中序序列为,DBFEAC,，则该二叉树对应森林按层遍历结果为,_,。,设,a,、,b,为一棵二叉树上两个结点，在中序遍历时，,a,在,b,前条件是（）。,A.a,在,b,右方,B.a,是,b,祖先,C,.a,在,b,左方,D.a,是,b,子孙,28/70,28,二度树与二叉树有何区分？,有,28,个结点二叉树最大和最小深度是多少？,在一棵度为,3,树中，度为,3,结点个数为,2,，度为,2,结点个数为,1,，则度为,0,结点个数有几个？,29/70,29,由五个分别带权值为,9,，,2,，,5,，,7,，,14,叶子结点组成,Huffman,树，写出该树带权路径长度,WLP,，及计算步骤。,30/70,30,给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中改进算法）。,给定关键码序列，判断是否为最大值堆或最小值堆，假如不是，调整成堆。,给定关键码序列，建初堆。,31/70,31,二叉搜索树删除,与插入相反，删除在,查找成功,之后进行，而且要求在删除二叉排序树上某个结点之后，,依然保持二叉排序树特征,。,删除过程分为以下情况：,被删除结点,是叶子,被删除结点,只,有左子树,或,只有右子树,被删除结点,有左、右子树,32/70,50,30,80,20,90,85,40,35,88,32,（,1,）被删除结点是,叶子结点,被删关键字,=20,88,其双亲结点中对应指针域值改为“空”,33/70,50,30,80,20,90,85,40,35,88,32,（,2,）被删除结点,只有左子树,或者,只有右子树,其双亲结点对应指针域值改为“指向被删除结点左子树或右子树”。,被删关键字,=40,80,34/70,若,p,有左右子树，则在左子树里找,中序周游最终一个结点,r,，,将,r,右指针置成指向,p,右子树根,，,用结点,p,左子树根去代替被删除结点,p,。,50,30,80,20,90,85,40,35,88,32,30,80,20,90,85,40,35,88,32,p,r,被删关键字,=50,（,3,）被删除结点,现有左子树，也有右子树,35/70,50,30,80,20,90,85,40,35,88,32,（,3,）被删除结点,现有左子树，也有右子树,40,40,以其前驱替换之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字,=50,36/70,第,6,章 树,树与森林,：定义、抽象数据类型定义,以及基本操作含义,树与森林链式,存放结构,（教材,6.2,）,树与森林次序,存放结构,（教材,63,）,树、森林遍历，与二叉树之间关系,，,相互转换,树深度优先周游与广度优先周游,读懂代码,6.6-6.7,37/70,37,树链式存放,1.,子结点表表示法,2.,左子结点,/,右弟兄结点表示法,3.,动态结点表示法,4.,动态,“,左子,/,右兄,”,二叉链表表示法,5.,父指针表示法,38/70,38,1.,子结点表表示法,每个分支结点均存放其子结点信息，子结点按照从左至右次序形成一个链表。,“,子结点表,”,表示法在数组中存放树结点。每个结点包含结点值、一个父指针以及一个指向子结点链表指针。,结点最左结点可由链表第一个表项找到。,39/70,39,A,D,F,B,C,G,H,E,IJ,K,L,A,A,A,B,0,A,C,0,A,A,A,A,A,G,2,A,D,1,A,E,1,A,F,2,A,H,2,A,I,3,A,J,3,A,A,A,K,6,A,L,6,0,1,2,3,4,5,6,7,8,9,10,11,索引 值 父 子,1,2,3,4,5,6,8,9,10,11,7,子结点表示法,40/70,40,2.,静态左子,/,右兄表示法,每个结点都存放结点值及指向父结点、最左子结点和右侧弟兄指针。,假如两棵树存放在同一个数组中，将其中一个添加为另一棵树子树只需简单设置三个指针值即可。,这种表示法比子结点表表示法空间效率更高，而且结点数组中每个结点仅需要固定大小存放空间。,41/70,41,静态左子,/,右兄表示法,H,B,G,A,C,D,I,J,E,F,A,A,/,A,B,0,A,C,0,A,A,A,A,A,G,/,A,D,0,A,E,2,A,F,2,A,H,6,A,I,6,A,J,7,0,1,2,3,4,5,6,7,8,9,左子 值 父 右兄,A,A,A,A,A,A,A,A,A,A,A,A,A,A,42/70,42,静态左子,/,右兄表示法,H,B,G,A,C,D,I,J,E,F,A,A,7,A,B,0,A,C,0,A,A,A,A,A,G,/,A,D,0,A,E,2,A,F,2,A,H,6,A,I,6,A,J,7,0,1,2,3,4,5,6,7,8,9,左子 值 父 右兄,A,A,A,A,A,A,A,A,A,A,A,A,A,A,43/70,43,3.,动态结点表示法,为每个结点分配可变存放空间。,将一个指向子结点指针数组作为结点一部分分配给结点。在子结点数目不变时，这种方法效果最正确；假如子结点数目发生变动（尤其是增加），就必须提供一个专门校正机制来改变子结点指针数组大小。,每个结点存放一条子结点指针链表。本质上,“,子结点表,”,表示法相同，不过它动态地分配结点空间，而不是把结点分配在数组中。,44/70,44,A,D,F,B,C,G,H,E,I,J,K,L,E,0,A,A,A,F,0,A,H,0,A,I,0,A,J,0,A,K,0,A,A,A,L,0,子结点表示法,A,A,2,A,B,2,A,G,2,A,D,2,A,C,3,45/70,45,4.,动态,“,左子,/,右兄,”,二叉链表表示法,D,A,B,C,E,F,G,|B|,|C|,|D|,|E|,|F|,|G|,|A|,46/70,46,5.,父指针表示法,树最简单表示方法是对每个结点只保留一个指针域指向其父结点，这种实现被称为,父指针,(parent pointer),表示法,假如两个结点抵达同一根结点，它们一定在同一棵树中。假如找到根结点是不一样，两个结点就不在同一棵树中,47/70,47,父指针数组表示法,父结点索引,标识,结点索引,48/70,48,树次序存放,1.,带右链先根次序表示法,2.,带双标识位先根次序表示法,49/70,49,1.,带右链先根次序表示法,在带右链先根次序表示中，结点按,先根次序次序,存放在一片连续存放单元中。每个结点除包含结点本身数据外，还附加两个表示结构信息字段，结点形式为,:,info,是结点数据，,rlink,是右指针，指向结点下一个弟兄,ltag,是一个左标识，,当结点没有子结点,，即,对应二叉树中结点没有左子结点时，,ltag,为,1,，不然为,0,50/70,50,带右链先根次序表示法,51/70,51,带右链先根次序,rlink-ltag,52/70,52,2.,带双标识位先根次序表示法,带右链先根次序表示法中每个结点都包含,ltag,和,rlink,字段，实际上,rlink,也不是必需。一位,rtag,就足以表示出整个森林结构信息。,要求当结点没有下一个弟兄，即对应二叉树中结点没有右子结点时,rtag,为,1,，不然为,0,。,53/70,53,带双标识位先根次序,rtag-ltag,54/70,54,第,7,章 图,有向图,/,网,：弧、入,/,出度、有向完全图,无向图,/,网,：边、度、无向完全图,图抽象数据类型定义,存放结构（相邻矩阵,/,邻接表）概念及,类定义,图周游算法,（掌握深度,/,广度，生成树）,最小生成树（,prim),、拓扑排序、单源最短路径,（必须会，且严格按照算法手工走给定实例）55/70,55,经典题目,能够完成拓扑排序图一定是一个,_,。,n,个顶点无向连通图最少有边条数是,_,。,已知一个有向图相邻矩阵表示，计算第,i,个结点入度方法是,_,。,56/70,56,已知一个无向图顶点集为,a,b,c,d,e ,其相邻矩阵以下所表示：,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,(1),画出该图图形；,(2),依据此相邻矩阵，从顶点,b,出发进行深度优先周游和广度优先周游，写出对应遍历顶点序列。,57/70,57,第,8,章 内排序,直接插入排序、冒泡排序、,快速排序,、直接选择排序、,堆排序,、归并排序、桶式排序、,基数排序,：手工排序每趟过程,各种排序方法适用场所、时间复杂度,必须熟悉快速排序、堆排序算法,58/70,58,在以下排序方法中，平均时间性能为,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,),59/70,59,用某种排序方法对线性表,(25,，,84,，,21,，,47,，,15,，,27,，,68,，,35,，,20),进行排序时，假如元素序列前几趟改变情况以下：,84,，,47,68,，,35,，,15,，,27,，,21,，,25,，,20,（第一趟）,68,，,47,，,27,，,35,，,15,，,20,，,21,，,25,，,84,（第二趟）,47,，,35,，,27,，,25,，,15,，,20,，,21,，,68,，,84,（第三趟）,35,，,25,，,27,，,21,，,15,，,20,，,47,，,68,，,84,（第四趟）,则所采取排序方法是（）。,A.,选择排序,B,.,堆排序,C.,归并排序,D.,快速排序,60/70,60,对关键字序列,(72,87,61,23,100,15,7,60,，,20),进行快速排序。请写出前,3,次次调用分割函数结果。,61/70,61,第,10,章 检索,相关概念，,ASL,次序查找、二分查找、分块查找,散列表（常见散列函数与处理冲突方法，计算,ASL,）查找特点，结构方法,62/70,62,在一个无序次序表中，查找不成功与能够找到一个元素所需时间相比较，耗时比较结果为（）。,A.,长,B.,短,C.,相等,D.,不可判断,假如要求一个线性表既能较快地查找，又能适应动态改变要求，能够采取（）。,A.,分块查找,B.,次序查找,C.,折半查找,D.,散列查找,63/70,63,假设散列表长度为,m,，散列函数为,H(key),，若用线性探测法处理冲突，则散列地址序列形式表示为,_,H,i,=(H(key)+d,i,)MOD m,_,。,在各种查找方法中，平均检索长不依赖于结点个数,n,查找方法是,_,散列,_,。,64/70,64,比如,:,关键码集合,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,65/70,65,第,11,章 索引技术,（了解概念）,稠密索引、稀疏索引适用场所。,线性索引,静态索引,倒排索引,动态索引,各种索引关键概念、特点、适用场所,66/70,66,第,12,章 高级数据结构,（了解概念）,广义表概念，存储,平衡二叉搜索树（定义、目）,67/70,67,依据数据状态及实际应该背景，抽象数学模型，选择数据结构、存放方法，设计算法并实现。,类定义：,抽象类定义,依据详细存放结构定义子类,68/70,68,考试题型,单项选择：,5,题，共,10,分,填空：,5,题，共,10,分,简答题：,4,题，共,40,分,算法阅读：,20,分,算法设计与数据结构设计：,20,分,69/70,69,考试要求：,能够带一张,A4,纸，不允许粘贴,70/70,70,