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

《北京工业大学 数据结构 期末复习.ppt》由会员分享，可在线阅读，更多相关《北京工业大学 数据结构 期末复习.ppt（48页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、考试题型n单选：5题，共10分n填空：5题，共10分n简答题：5题，共45分n算法阅读：15分n算法设计：20分考试要求：闭卷考试要求：闭卷第第1章章 概论概论nDS描述描述描述描述“按一定逻辑关系组织的数据元素的表示及相关按一定逻辑关系组织的数据元素的表示及相关按一定逻辑关系组织的数据元素的表示及相关按一定逻辑关系组织的数据元素的表示及相关操作操作操作操作n数据逻辑结构：数据逻辑结构：线性结构、树形结构和图形结构线性结构、树形结构和图形结构n数据存储结构：数据存储结构：顺序方法、链接方法、索引方法、散列顺序方法、链接方法、索引方法、散列方法方法n抽象数据类型抽象数据类型ADTn算法算法4个特

2、性：通用性、有效性、确定性、有穷性个特性：通用性、有效性、确定性、有穷性n算法分析：算法分析：T(n)、S(n)算法分析的相关概念算法分析的相关概念；最差、最；最差、最佳与平均情况的意义佳与平均情况的意义ADT的定义的定义n n三元组表示三元组表示ADT=(D,R,P)n nADT 抽象数据类型名抽象数据类型名 n n数据对象数据对象数据对象数据对象D:n n数据关系数据关系数据关系数据关系R:n n基本操作基本操作基本操作基本操作P:n n ADT 抽象数据类型名抽象数据类型名n n用用C+类模板的声明表示类模板的声明表示ADT数据的抽象算法的抽象ADT定义定义类模板类模板n n类模板代表类

3、模板代表类模板代表类模板代表一类一类一类一类类，不代表具体的类类，不代表具体的类类，不代表具体的类类，不代表具体的类n n类模板的定义格式类模板的定义格式类模板的定义格式类模板的定义格式:template template/类型参数类型参数类型参数类型参数Type,Type,使用时用具体数据类型代替使用时用具体数据类型代替使用时用具体数据类型代替使用时用具体数据类型代替class class classNameclassName private:private:Type Type dataListdataList;public:public:methodNamemethodName();();

4、n nC+C+引入模板概念，是想突出数据的逻辑结构而忽略引入模板概念，是想突出数据的逻辑结构而忽略引入模板概念，是想突出数据的逻辑结构而忽略引入模板概念，是想突出数据的逻辑结构而忽略其具体的数据类型其具体的数据类型其具体的数据类型其具体的数据类型声明、定义和使用声明、定义和使用声明、定义和使用声明、定义和使用 C+C+类模板类模板类模板类模板(2)(2)类模板：描述了一组相关的类，它们只能通过类型来区分类模板：描述了一组相关的类，它们只能通过类型来区分类模板：描述了一组相关的类，它们只能通过类型来区分类模板：描述了一组相关的类，它们只能通过类型来区分 1 1、类模板声明：仅提供了类的名称和类的

5、模板参数、类模板声明：仅提供了类的名称和类的模板参数、类模板声明：仅提供了类的名称和类的模板参数、类模板声明：仅提供了类的名称和类的模板参数template classtemplate /类模板类模板类模板类模板 Array Array 可接受任何类型作为可接受任何类型作为可接受任何类型作为可接受任何类型作为参数参数参数参数class Array Elem*data;class Array Elem*data;intint size;size;/声明类模板声明类模板声明类模板声明类模板ArrayArray的类数据的类数据的类数据的类数据 public:public:Array(Array(in

6、tint szsz);/函数成员函数成员函数成员函数成员 intint GetSizeGetSize()();2 2、函数成员定义、函数成员定义、函数成员定义、函数成员定义template Array:template Array:Array(Array(intint szsz)size=size=szsz;data=new;data=new ElemsizeElemsize;template template intint Array:Array:GetSizeGetSize()()return size;return size;3 3、类模板的用法、类模板的用法、类模板的用法、类模板的用法

7、 ArrayArray int_array(100);/int_array(100);/ArrayArray接收接收接收接收intint作参数作参数作参数作参数,/int_arrayint_array为为为为长长长长100100的的的的intint型数组对象型数组对象型数组对象型数组对象常见常见上限上限g(n)的种类的种类(用于比较各算法优劣用于比较各算法优劣)n nO(1)O(1)O(lognO(logn)O(nO(n)O(nlognO(nlogn)O(n)O(n2 2)常数阶常数阶常数阶常数阶 对数对数对数对数 线性线性线性线性 对数乘积对数乘积对数乘积对数乘积 平方平方平方平方 O(nO

8、(n3 3).O(2.O(2n n)O(nO(n!)!)立方立方立方立方 指数指数指数指数 阶乘阶乘阶乘阶乘n n常数：常数：常数：常数：g(ng(n)=1)=1n n对数：对数：对数：对数：g(ng(n)=)=lognlognn n线性增长：线性增长：线性增长：线性增长：g(ng(n)=n)=nn n二阶增长：二阶增长：二阶增长：二阶增长：g(ng(n)=n)=n2 2n ng(ng(n)=)=nlog(nnlog(n),),n=n=nlog(nnlog(n)增长率增长率增长率增长率 =n -*/(错错#/#，入栈，入栈，入栈，入栈#/#/4 4.2 2(入栈入栈入栈入栈#/#/（2 2b

9、b输出输出输出输出b babab1 1-(-(，入栈，入栈，入栈，入栈#/#/（-4 4.2 2c c输出输出输出输出c cabcabc1 1)-出栈输出出栈输出出栈输出出栈输出,直至直至直至直至(#/#/（abcabc-3.23.2)=(,)=(,出栈不输出出栈不输出出栈不输出出栈不输出#/#/3 3.2.2+/,/+#+#，入栈，入栈，入栈，入栈#+#+4 4.2.2d d输出输出输出输出d dabc-/dabc-/d1 1*+*+，入栈，入栈，入栈，入栈#+*#+*4 4.2.2e e输出输出输出输出e eabcabc-/de-/de1 1#连续出栈输出连续出栈输出连续出栈输出连续出栈输

10、出abcabc-/de*+-/de*+5 5后缀表达式求值后缀表达式求值 n n循环：依次分析输入序列：循环：依次分析输入序列：循环：依次分析输入序列：循环：依次分析输入序列：n n1.1.1.1.输入是操作数：则入栈；输入是操作数：则入栈；输入是操作数：则入栈；输入是操作数：则入栈；n n2.2.2.2.输入是运算符：则输入是运算符：则输入是运算符：则输入是运算符：则两次出栈两次出栈两次出栈两次出栈，取操作数取操作数取操作数取操作数2 2 2 2和操和操和操和操作数作数作数作数1 1 1 1，按照运算符进行，按照运算符进行，按照运算符进行，按照运算符进行计算计算计算计算。将。将。将。将结果入

11、栈结果入栈结果入栈结果入栈。n n重复，直至遇到结束符重复，直至遇到结束符重复，直至遇到结束符重复，直至遇到结束符“=”n n此时栈顶值就是输入表达式的值。此时栈顶值就是输入表达式的值。此时栈顶值就是输入表达式的值。此时栈顶值就是输入表达式的值。第第 4 4 章章 字符串字符串(了解）了解）l 基本概念基本概念l 存储结构（顺序、标准类）存储结构（顺序、标准类）l 基本操作的含义基本操作的含义第第5 5章章 二叉树二叉树定义、定义、性质性质、存储结构（相应的类定义）、存储结构（相应的类定义）满二叉树、完全二叉树及扩充二叉树满二叉树、完全二叉树及扩充二叉树抽象数据类型定义中的基本操作含义抽象数据

12、类型定义中的基本操作含义深度周游（递归与非递归），广度周游深度周游（递归与非递归），广度周游二叉搜索树二叉搜索树插入、删除（改进）与检索算法；插入、删除（改进）与检索算法；必须能够跟踪执行过程；求必须能够跟踪执行过程；求ASL。堆堆概念、建堆、筛选、插、删的相关算法概念、建堆、筛选、插、删的相关算法(过程过程)Huffman树树构造及构造及Huffman编码编码深度优先周游二叉树（递归实现）深度优先周游二叉树（递归实现）1.1.templatetemplate2.2.void void BinaryTreeBinaryTree:PreOrderPreOrder (BinaryTreeNodeB

13、inaryTreeNode*root)*root)3.3.if(rootif(root!=NULL)!=NULL)4.4.Visit(rootVisit(root-value();-value();/前序前序前序前序5.5.DepthOrder(rootDepthOrder(root-leftchildleftchild();/();/访问左子树访问左子树访问左子树访问左子树6.6.7.7.DepthOrder(rootDepthOrder(root-rightchildrightchild();/();/访问右子树访问右子树访问右子树访问右子树8.8.9.9.10.10.Visit(root

14、)/中序中序Visit(root)/后序后序451253324100906137 生成二叉搜索树生成二叉搜索树45,53,12,37,3,100,61,24,90,7878二叉搜索树的删除n在二叉搜索树里删除结点时，不是把以这个在二叉搜索树里删除结点时，不是把以这个结点为根的子树都删除掉，只是删除一个结结点为根的子树都删除掉，只是删除一个结点，并且还要保持二叉搜索树的性质。点，并且还要保持二叉搜索树的性质。n删除过程分为两种情况：删除过程分为两种情况：n没有左子树没有左子树n有左子树有左子树没有左子树 若结点若结点p p没有左子树，则用右子树的根代替被删除没有左子树，则用右子树的根代替被删除的

15、结点的结点p p。50308020908540358832503020908540358832有左子树（改进）若若p(50)p(50)有左子树，则在左子树里找中有左子树，则在左子树里找中序周游的最后一个结点序周游的最后一个结点s(40)s(40)，删除删除s，用用s的左子树代替的左子树代替s，用，用s代替被删代替被删p 这种方法可以降低二叉树的高度。这种方法可以降低二叉树的高度。50308020908540358832403080209085353288已知序列已知序列72,73,71,23,94,16,05,68 建堆建堆72727272最小堆的插入最小堆的插入n n插入过程：插入点追加到最

16、后，插入过程：插入点追加到最后，自下而上自下而上依次比较依次比较父与子父与子，直到满足堆的定义，直到满足堆的定义121419241813221517262012141924182022151726131213192418202215172614插入插入13 2013 1413 最小堆的删除最小堆的删除n n用最后结点用最后结点替换替换被删结点，被删结点，自上至下自上至下调整成堆调整成堆n n(最后结点最后结点被删结点被删结点,只影响其子树的最小堆性质只影响其子树的最小堆性质)12141924182215172620删除删除14 14262619 2622 2612192624182215172

17、01219222418261517205.6 Huffman树及其应用n n外部路径长度外部路径长度lin n扩充二叉树从根到每个外部结点的路径长度之和扩充二叉树从根到每个外部结点的路径长度之和 n n外部路径长度最小的二叉树：是完全二叉树外部路径长度最小的二叉树：是完全二叉树n n带带权权外外部部路路径径长长度度(weighted external path)最最小小的的二叉树：二叉树：Huffman树树n n要求给出一个具有要求给出一个具有n个外部结点的扩充二叉树个外部结点的扩充二叉树n n每每个个外外部部结结点点Ki有有一一个个wi与与之之对对应应，作作为为该该外外部部结点的权结点的权n

18、 n此此扩扩充充二二叉叉树树的的叶叶结结点点带带权权外外部部路路径径长长度度总总和和最最小小 n n 注意注意:不管内部结点不管内部结点，也不用有序也不用有序n n特点：特点：权越大的叶结点离根越近权越大的叶结点离根越近35291478c c3 3d d4 4e e5 523f f6 611h h8 8b b2 281519294258100建树建树g g7 7a a下标：下标：下标：下标：1 1101011000a:0001a:0001b:10b:10c:1110c:1110d:1111d:1111f:01f:01g:0000g:0000h:001h:001与算法有关的典型例题与算法有关的典

19、型例题p已知一棵二叉树的前序和中序（后已知一棵二叉树的前序和中序（后序和中序）遍历序列，构造对应的序和中序）遍历序列，构造对应的二叉树二叉树p通过二叉树，获得对应的树与森林通过二叉树，获得对应的树与森林的相关信息的相关信息p深度周游与广度周游二叉树深度周游与广度周游二叉树31n具有具有n个结点的满二叉树，其叶子结点个结点的满二叉树，其叶子结点的个数为的个数为_。(如果一棵二叉树的如果一棵二叉树的如果一棵二叉树的如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二任何结点，或者是树叶，或者恰有两棵非空子树，则此二任何结点，或者是树叶，或者恰有两棵非空子树，则此二任何结点，或者是树叶

20、，或者恰有两棵非空子树，则此二叉树称作满二叉树叉树称作满二叉树叉树称作满二叉树叉树称作满二叉树,性质性质性质性质3.3.任何一棵二叉树，任何一棵二叉树，任何一棵二叉树，任何一棵二叉树，n n0 0=n=n2 2+1+1)n某棵二叉树的前序序列为某棵二叉树的前序序列为ABDEFC，中序序列为中序序列为DBFEAC，则该二叉树对，则该二叉树对应的后序序列的结果为应的后序序列的结果为_。n五个分别带权值为五个分别带权值为9，2，5，7，12 的叶子的叶子结点构造结点构造Huffman树，进行编码，并写出该树，进行编码，并写出该树的树的带权外部路径长度带权外部路径长度WPL。n给定关键码序列，创建二叉

21、搜索树，给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进并删除某个结点（按照教材中的改进算法），求算法），求ASLn堆排序：堆排序：n给定关键码序列，建初堆。给定关键码序列，建初堆。n插入、删除结点后，调整为堆插入、删除结点后，调整为堆第第6 6章章 树树q树与森林定义、树与森林定义、ADT定义、基本操作定义、基本操作q树（森林）周游树（森林）周游(深度优先、广度优先深度优先、广度优先)q先根次序周游森林先根次序周游森林=前序周游二叉树前序周游二叉树q后根次序周游森林后根次序周游森林=中序周游二叉树中序周游二叉树q树（森林）与二叉树的等价转换树（森林）与二叉树的等价转换q树与森

22、林的链式存储结构树与森林的链式存储结构q动态动态“左子左子/右兄右兄”二叉链表表示法二叉链表表示法森林与二叉树的等价转换n n森林由部分组成：森林由部分组成：n n森林中第一棵树的根结点森林中第一棵树的根结点n n森林中第一棵树的子树森林森林中第一棵树的子树森林n n森林中其它树构成的森林森林中其它树构成的森林动态“左子/右兄”二叉链表表示法 35DABCEFG|B|C|D|E|F|G|A|6.1.4 树的周游树的周游 1、深度优先周游树、深度优先周游树 一一一一.先根次序周游森林先根次序周游森林先根次序周游森林先根次序周游森林 前序前序前序前序周游周游周游周游二叉树二叉树二叉树二叉树n n首

23、棵树根；首棵树各子树；余下各树首棵树根；首棵树各子树；余下各树首棵树根；首棵树各子树；余下各树首棵树根；首棵树各子树；余下各树n n根；根；根；根；左子树；左子树；左子树；左子树；右子树右子树右子树右子树n n依次从左至右对森林每棵依次从左至右对森林每棵依次从左至右对森林每棵依次从左至右对森林每棵树树树树进行进行进行进行先序周游先序周游先序周游先序周游二二二二.后根次序周游森林后根次序周游森林后根次序周游森林后根次序周游森林 中序中序中序中序周游周游周游周游二叉树二叉树二叉树二叉树n n首棵树各子树；首棵树根；余下各树首棵树各子树；首棵树根；余下各树首棵树各子树；首棵树根；余下各树首棵树各子树

24、；首棵树根；余下各树n n 左子树；左子树；左子树；左子树；根；根；根；根；右子树右子树右子树右子树n n依次从左至右对森林每棵依次从左至右对森林每棵依次从左至右对森林每棵依次从左至右对森林每棵树树树树进行进行进行进行后序后序后序后序周游周游周游周游n n先序：先序：先序：先序：ABCEFD GHJIABCEFD GHJIn n后序：后序：后序：后序：BEFCDA JHIGBEFCDA JHIGABCFEDGHJIABGHCEFIDJ带右链的先根次序表示法带右链的先根次序表示法 n n这这种种表表示示法法与与llinkllinkrlinkrlink表表示示法法相相比比，用用ltagltag代代

25、替替了了llinkllink，占占用用的的存储单元要少些，但并不丢失信息存储单元要少些，但并不丢失信息n n可以从结点的次序和可以从结点的次序和ltagltag的值完全可以推知的值完全可以推知llinkllinkn nltagltag=0:=0:有左子，它的有左子，它的llinkllink指向该结点数组右邻指向该结点数组右邻n nltagltag=1:=1:没有左子，它的没有左子，它的llinkllink为空为空第第7章章 图图n n有向图有向图/网：弧、入网：弧、入/出度、有向完全图出度、有向完全图n n无向图无向图/网：边、度、无向完全图网：边、度、无向完全图n n图的图的ADTADT定义

26、定义n n存储结构（相邻矩阵存储结构（相邻矩阵、邻接表）及类定义邻接表）及类定义n n图周游算法（深度图周游算法（深度、广度）广度）n n最小生成树（最小生成树（prim)prim)、拓扑排序、单源最、拓扑排序、单源最短路径（必须会严格按照算法手工走给定短路径（必须会严格按照算法手工走给定实例）实例）典型题目典型题目1.1.能够完成拓扑排序的图一定是一个能够完成拓扑排序的图一定是一个_。2.2.n n个顶点的无向连通图至少有的边的条数是个顶点的无向连通图至少有的边的条数是_。3.3.已知一个有向图的相邻矩阵表示，计算第已知一个有向图的相邻矩阵表示，计算第i i个结个结点的入度的方法是点的入度的

27、方法是_。4.4.已知一个无向图的顶点集为已知一个无向图的顶点集为 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 出出发发进进行行深深度度优优先先周周游和广度优先周游，写出相应周游的顶点序列。游和广度优先周游，写出相应周游的顶点序列。第第 8 章章 内排序内排序 qq直接插入排序、冒泡排序、直接插入排序、冒泡排序、快速排序快速排序、直接选择排序、直接选择排序、堆排序堆排序、归并排序、桶式、

28、归并排序、桶式排序、基数排序：手工排序每趟过程排序、基数排序：手工排序每趟过程qq各种排序方法的性能对比各种排序方法的性能对比(稳定性、时空稳定性、时空)qq各种排序方法的适用场合、时间复杂度各种排序方法的适用场合、时间复杂度算法算法算法算法最大最大最大最大时间时间时间时间平均平均平均平均时间时间时间时间最小最小最小最小时间时间时间时间S(nS(n)稳稳稳稳定性定性定性定性直接插入排序直接插入排序直接插入排序直接插入排序(n(n2 2)(n(n2 2)(n(n)(1)(1)稳稳稳稳定定定定冒泡排序冒泡排序冒泡排序冒泡排序(n(n2 2)(n(n2 2)(n(n)(1)(1)稳稳稳稳定定定定直接

29、直接直接直接选择选择选择选择排序排序排序排序(n(n2 2)(n(n2 2)(n(n2 2)(1)(1)不不不不稳稳稳稳定定定定ShellShell排序排序排序排序(n(n3/23/2)(n(n3/23/2)(n(n3/23/2)(1)(1)不不不不稳稳稳稳定定定定快速排序快速排序快速排序快速排序(n(n2 2)(nlog(nlog n)n)(nlog(nlog n)n)(log(log n)n)不不不不稳稳稳稳定定定定归归归归并排序并排序并排序并排序(nlog(nlog n)n)(nlog(nlog n)n)(nlog(nlog n)n)(n(n)稳稳稳稳定定定定堆排序堆排序堆排序堆排序(n

30、log(nlog n)n)(nlog(nlog n)n)(nlog(nlog n)n)(1)(1)不不不不稳稳稳稳定定定定桶式排序桶式排序桶式排序桶式排序(n+m(n+m)(n+m(n+m)(n+m(n+m)(n+m(n+m)稳稳稳稳定定定定基数排序基数排序基数排序基数排序(d(n+r(d(n+r)(d(n+r(d(n+r)(d(n+r(d(n+r)(n+r(n+r)稳稳稳稳定定定定排序算法的理论性能排序算法的理论性能 表表8.3 在在在在下下下下列列列列排排排排序序序序方方方方法法法法中中中中，平平平平均均均均时时时时间间间间性性性性能能能能为为为为O(nlognO(nlogn)且且且且空间

31、性能最好的是（空间性能最好的是（空间性能最好的是（空间性能最好的是（）。）。）。）。A.A.快速排序快速排序快速排序快速排序 B.B.堆排序堆排序堆排序堆排序 C.C.归并排序归并排序归并排序归并排序 D.D.基数排序基数排序基数排序基数排序 堆排序在最坏的情况下的时间复杂度是堆排序在最坏的情况下的时间复杂度是堆排序在最坏的情况下的时间复杂度是堆排序在最坏的情况下的时间复杂度是 ()()。A.O(logA.O(log2 2 n)n)B.O(log B.O(log2 2 n n2 2)C.O(nlogC.O(nlog2 2 n)n)D.O(n D.O(n2 2)第第10章章 检索检索43qq相关

32、概念，相关概念，ASLASLqq顺序查找、二分查找、分块查找顺序查找、二分查找、分块查找qq散列表（常见的散列函数与解决冲突的散列表（常见的散列函数与解决冲突的方法，计算方法，计算ASL）查找特点，构造方法）查找特点，构造方法 开散列方法 拉链法n散列表中每个槽添加一个链表表头，当发生冲突时就拉出一条链，散列表中每个槽添加一个链表表头，当发生冲突时就拉出一条链，建立一个链表方式的同义词表，动态申请同义词空间建立一个链表方式的同义词表，动态申请同义词空间n例：例：77、7、110、95、14、75、62 h(Keyh(Key)=Key%11)=Key%11n同义词表中同义词可按值的顺序同义词表中

33、同义词可按值的顺序,访问频率的顺序排列访问频率的顺序排列ASL=(1/7)*(1*4+2*2+3*1)例如例如:关键码集合关键码集合 19,01,23,14,55,68,11,82,36 设定设定哈希函数 H(key)=key MOD 11(表长=11)190123 145568若采用线性探测法处理冲突，构造该散列表若采用线性探测法处理冲突，构造该散列表11 82361 1 2 1 3 6 2 5 1第第1111章章 索引技术（了解概念）索引技术（了解概念）n稠密索引、稀疏索引的适用场合。稠密索引、稀疏索引的适用场合。n线性索引线性索引n静态索引静态索引n倒排索引倒排索引n动态索引动态索引各种索引关键概念、特点、适用场合各种索引关键概念、特点、适用场合第第1212章章 高级数据结构高级数据结构n多维数组多维数组n压缩存储：三元组表，十字链表压缩存储：三元组表，十字链表n广义表概念，存储广义表概念，存储n平衡二叉搜索树（目的）平衡二叉搜索树（目的）ASL 根据数据状态及实际应该背景，抽根据数据状态及实际应该背景，抽象数学模型，选择数据结构、存储方象数学模型，选择数据结构、存储方法，设计算法并实现。法，设计算法并实现。类定义：类定义：l抽象类定义抽象类定义l根据具体存储结构定义子类根据具体存储结构定义子类