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

1、1，2，试题，单项选择：5道题，10分填空：5道题，10分简答题：5道题，45分算法阅读：15分算法设计：20分考试要求：闭卷，3，第1章导论，DS描述了“根据一定的逻辑关系组织的数据元素的表示和相关的运算数据逻辑结构：线性结构，树形结构和图形结构。数据存储结构：顺序法、链接法、索引法、散列法。抽象数据类型ADT算法有四个特点：通用性、有效性、确定性、有限算法分析：T(n)、S(n)算法分析相关概念；最差情况、最佳情况和平均情况的含义，4，ADT的定义，三重表示ADT=(D，R，P) ADT抽象数据类型名称数据对象D:数据关系R :基本操作P: ADT抽象数据类型名称用c类模板的声明表示ADT

2、，5，ADT定义类模板，它表示一个类，它不表示具体类模板：模板/类型参数类型的定义格式，并且使用具体数据类型代替类名 privpublic : MethodName()；引入模板的概念是为了突出数据的逻辑结构，而忽略其特定的数据类型。6.声明、定义和使用C类模板(2)。类模板：描述一组相关的类，这些类只能通过类型来区分。1.类模板声明：只提供类的名称和类的模板参数模板/类模板数组可以接受任何类型的参数类数组Elem*数据；int大小；/声明类模板数组的类数据public : Array(int SZ)；/函数成员int GetSize()；2.函数成员定义模板数组：数组(整数SZ)大小=SZ数

3、据=新Elem大小；模板整数数组：GetSize()返回大小； 3。类模板数组int_array的用法(100)；/Array接收int作为参数，/int_array是一个int数组对象，长度为100，7，那种常用的上限g(n)(用来比较每种算法的优缺点)，O(1)-(错#值()；/序言DepthOrder(root-left child()；/访问左边的子树DepthOrder(root-right child()；/访问右子树，访问(根)/中间顺序，访问(根)/后顺序，21，生成二进制搜索树45，53，12，37，3，100，61，24，90，78，22，删除二进制搜索树，删除过程分为两种

4、情况：没有左子树，23，没有左子树，如果节点P没有左子树，被删除的节点P将被右子树的根替换。24，有一个左子树(改进)。如果p(50)有一个左子树，在左子树中找出中间顺序遍历的最后一个节点s(40)，删除S，用S的左子树替换S，用S替换删除的P。，25，已知序列72，73，71，23，94，16，05，68，72，26，插入最小堆，插入过程：插入点被附加到末尾，父子顺序从下到上进行比较，直到满足堆的定义，插入13 2013 1413，27，删除最小堆。仅影响其子树的最小堆属性)，12，14，19，24，18，22，15，17，20，删除14 1426 2619 2622，26，28，5.6霍夫

5、曼树及其应用外部路径长度li从根到每个外部节点的路径长度之和最小的二叉树是具有最小加权外部路径长度的二叉树：霍夫曼树需要具有n个外部节点的扩展二叉树，并且每个外部节点Ki具有与其对应的wi作为该外部节点的权重，该扩展二叉树的叶节点具有加权外部路径的最小总长度。注：无论内部节点，都没有顺序特征：权重越大，叶节点离根越近，29、3、5、29、14、7、8、C3、D4、E5、23、F6、11、H 构造相应的二叉树，并通过二叉树得到相应的树和林之间的相关性(如果二叉树的任何节点，或者树叶，或者只有两个非空的子树，那么这个二叉树被称为全二叉树，属性3。 任何二叉树，n0=n2 1)如果二叉树的前序序列是

6、ABDEFC，中间序序列是DBFEAC，那么对应于该二叉树的后序序列的结果是_ _ _ _ _ _ _ _ _ _ _ _ _ _。权重分别为9、2、5、7和12的五个叶节点构造霍夫曼树，对其进行编码，并写出树的加权外路径长度WPL。给定密钥序列，创建二叉搜索树，删除一个节点(根据教科书中的改进算法)，并找到ASL堆排序：给定密钥序列，构建初始堆。插入和删除节点后，将其调整为堆，33。第六章：树，树和森林定义，ADT定义，基本操作树(森林)遍历(深度优先，宽度优先)第一根顺序遍历森林=前顺序遍历二叉树然后根顺序遍历森林=中间顺序遍历二叉树(森林)和二叉树等价转换树和森林链存储结构动态“左子/右

7、弟”二元链表森林和二叉树之间的等价转换，森林由三部分组成：森林中第一棵树的根节点， 森林中第一棵树的子树，该森林由森林中的其他树、35、动态左子/右弟二进制链表表示，30 | f |、| g |、| a |、36、6.1.4树遍历1。 深度第一遍历树，1。根顺序中的第一个遍历林二叉树中的第一个遍历树根；第一棵树的每个子树；剩下的树根；左子书；右子树从左到右依次穿过森林中的每棵树。2.以根后顺序穿过森林以中间顺序穿过二叉树中第一棵树的子树；第一个树根；剩余树的左子树；根；右子树从左到右对林中的每棵树进行后向遍历：ABCEFD GHJI后向：BEFCDA JHIG，37，它是右链的第一个根顺序的表

8、示。与llink-rlink表示法相比，这种表示法使用ltag代替了占用较少存储单元的llink。但它不会丢失信息。从节点的顺序和ltag值可以推断，llink ltag=0:有一个左子节点，它的link指向没有左子节点的节点数组的右邻居ltag=1:它的LINK为空，38，图7，有向图/网：弧，入/出度，有向完全图无向图/网：边，度和无向图的ADT定义存储结构(邻接矩阵，邻接表)和类定义图遍历算法(深度，宽度)最小值具有n个顶点的无向连通图的边数至少为_ _。给定有向图的邻接矩阵表示，计算第I个节点度的方法是_ _ _ _ _ _ _ _ _ _ _ _ _ _。已知无向图的顶点集是a，b，

9、c，d，e，其邻接矩阵如下：(1)画出图；0 1001 100 100 000 101 101 101 101 101 10(2)根据这个相邻矩阵，从顶点B开始进行深度优先遍历和宽度优先遍历，并写出相应遍历的顶点序列。40，第8章中的排序，直接插入排序，冒泡排序，快速排序，直接选择排序，堆排序，合并排序，桶排序，基数排序：手动排序过程中各种排序方法的性能比较(稳定性，时间和空间)各种排序方法的适用场合和时间复杂度，41，排序算法的理论性能表8.3，42，在以下排序方法中，a .快速排序b .堆排序c .合并排序d .基数排序最差情况下堆排序的时间复杂度为()。a . o(log2n)b . o(log2n 2)c . o(nlog2n)d . o(N2)，43，第10章搜索，43，相关概念，ASL顺序搜索，二进制搜索，块搜索散列表(通用散列函数和冲突解决方法，计算ASL)搜索特征和构造方法向散列表中的每个槽添加一个链表头，当有冲突时拉出一个链，建立一个链表同义词表，并动态应用同义词空间示例：77，7，110，95，14ASL=(1/7)*(1*4 2*2 3*1)，45，例如，键集19，01，2 3，14，55，68，11，82，36，集散列函数H(键)=键MOD 11(表长度)该散列表的构造，11，82，36，11，21，36，62，51，46，第11章，索引技术(理解概念)