大学数据结构期末知识点重点总结(考试专用)

1、(完整 word第一章概论。不足：t仅指向后继不能有效找到前驱表达式 = 项项 +| 项 项. 有n个结n)的完全二叉树的高度为|项（n+1)，深度为log2(n+1）1。数据结构描述的是 按照一定逻辑关系组织起来 4.2 双链表的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算a.增加前驱指针，弥补单链表的不足项 ：:= 因子 * /因子左到右编号，则有：2。数据的逻辑结构dli0 为根结点；如果，其父结点编号系模型,反映了事物的组成结构及事物之间的逻辑关表的头结点系数字是 (i1)/2数字 = 0 1 2 3 4 | 5 | 6 2） 当 2i+1prev = p-nex

2、t =代表一个数据或一组有明确结构的数据Le）pp关系集R是定义在集合K上的一组关系其中每个 4.3顺序表和链表的比较初始化操作数栈 OP，运算符栈 OPND;OPND。结点没有右子结点3。周游（重点为由前序中序/中序后序求得二叉树）关系r（rR）都是KK上的二元关系push（）;a.深度优先周游二叉树可以有下列三种周游顺序:数据类型4。3。1 主要优点（实现：栈）读取InfixExp表达式的一项1) 前序周游（tLR 次序)：访问根结点；前序周游a。基本数据类型顺序表的主要优点操作数：直接输出到 PostfixExp 中；左子树；前序周游右子树操作符:整数类型（r)、布尔类型 没用使用指针，

3、不用花费附加开销；线性表元素的操作符:（n（r（r）读访问非常简洁便利b。复合数据类型2） 中序周游(LtR 次序):中序周游左子树;访问根结点；中序周游右子树复合类型是由基本数据类型组合而成的数据类型；链表的主要优点当（：入D；) 后序周游t次序:后序周游左子树；后序周右子树;访问根结点DD结点类型很大变化；能够适应经常插入删除内部元素的情况PostfixExpzb. 广度周游二叉树：从二叉树的顶层(根结点）开到（为止；若 为(，弹出即可始，自上至下逐层遍历；在同一层中，按照从左到4。3。2线性结构（4。3。2（一对多)、图结构（多对多)四则运算符循（当栈非空且栈顶不是右的顺序对结点逐一访问

4、（实现：队列）5。四种基本存储映射方法： 顺序、链接、索引、 a。不宜使用顺序表的场合& 当前运算符优先级栈顶运算符优先级），反 4。存储复弹出栈顶运 算符并输入到 PostfixExp 中,再将当散列经常插入删除时，不宜使用顺序表；线性表的最大前运算符压入栈链式存储结构，6长度也是一个重要因素3.4后缀表达式求值顺序存储结构（仅限完全二叉树：因为完全二叉树性排列紧凑）b.不宜使用链表的场合初始化操作数栈OP；5.二叉搜索树算法分析:目的是从解决同一个问题的不同算法5.二叉搜索树加工、使其优化中选择比较适合的一种，或者对原始算法进行改造、当不经常插入删除时，不应选择链表;当指针的存储 whil

5、e （表达式没有处理完） 加工、使其优化开销与整个结点内容所占空间相 比其比例较大时，渐进算法分析a大分析法：上限，表明最坏情况应该慎重选择item= 读取表达式一项；第三章 栈与队列操作数:入栈 OP；树：对于任何一个结点，设其值为 K，则该结点的分析法：下限，表明最好情况1。栈运算符：退出两个操作数,左子树（若不空)的所有结点的值都小于 K;性表;其特点后进先出；插入：入栈 (压栈；删除:a.栈是一种限定仅在一端进行插入和删除操作的线计算，并将结果入栈右子树（若不空)的所有结点的值都大于出栈（退性表;其特点后进先出；插入：入栈 (压栈；删除:（固定c.递归使用的场合：定义是递归的；数据结构

6、是递 它的左右子树也分别为二叉搜索树第二章 线性表两种归的；解决问题的方法是递归的线性结构的基本特征集合中必存在唯一的一个“第一元素” bc.除最后元素之外,均有唯一的后继应用:1) 数 制 转 换 while （N）N8b.性质:按照中序周游将各结点打印出来，得到的排列按照由小到大有序2.队列a.若线性表的插入操作在一端进行，删除操作在另 c.检索：2.队列一端进行，则称此线性表为队列b。循环队列判断队满对空：从根结点开始，在二叉搜索树中检索值K（tK，则检索结束d。除第一元素之外,均有唯一的前驱线性结构的基本特点：均匀性、有序性3。顺序表主要特性：元素的类型相同；元素顺序地存储在N=N/8

7、;while出栈；第五章 二叉树1。概念一个结点的子树的个数称为度数如果 K 小于根结点的值，则只需检索左子树如果 K 大于根结点的值，则只检索右子树该过程一直持续到找到 K 或者遇上叶子结点如果遇上叶子结点仍没有发现 K，则查找失败的层数数作为向量长度2）括号匹配检验的层数bLoc（ki） = 不匹配情况:各类括号数量不同;嵌套关系不正确0）i * LL）的层数加1*查找关键码:把查找时所经过的点一次写c二叉树的深度定义为二叉树中层数最大的叶结点 d.插入：线性表的优缺点:算法：如果一棵二叉树的任何结点，或者是树叶,或者恰 用待插入结点与树根比较 ,若待插入的关键值小于优点：逻辑结构与存储结

8、构一致 ;属于随机存取方式，即查找每个元素所花时间基本一样逐一处理表达式中的每个字符 ch：有两棵非空子树，则此二叉树称作满二叉树树根的关键值，就进入左子树，否则进入右子树； 在子树中,按照同样的方式沿检索路径直到叶结点， 将新结点插入到二叉搜索树的叶子结点位置缺点：空间难以扩充：=【（】ch=非括号：不做任何处理ch=左括号：入栈可以小于 2；最下面一层的结点都集中在该层最左 e.创建：从空的 BST 开始,将关键码按 BST 定义一边的位置上，则称此二叉树为完全二叉树次插入边的位置上，则称此二叉树为完全二叉树.当二叉树里出现空的子树时,就增加新的、特殊的e。插入:插入前检查是否满了，插入时

9、插入处后的ch=右括号：if （栈空)returnfalse二叉树与插入相反，删除在查找成功之后进行,并且要求在表需要复制【（n】e外部路径长度 ：从扩充的二叉树的根到每个外部 删除二叉排序树上某个结点之后，仍然保持二叉排f.删除：删除前检查是否是空的,删除时直接覆盖就 出栈，检查匹配情况，结点(新增的空树叶）的路径长度之和序树的特性，删除过程分为如下情况：被删除的结点是叶子:直接将其删除即可行了【（n)】内部路径长度 I：扩充的二叉树中从根到每个内部4。链表4。1 单链表if (不匹配） return false结点（原来二叉树结点)的路径长度之和性质a顺序存取的存储结构 ,即存取每个数据元

10、素所花费如果结束后，栈非空，返回 falsea。 二叉树的第 i 层（根为第 0 层，i0）最多有 3)p2ir2ipp的时间不相等3）表达式求值b。 深度为k的二叉树至多有2k+11个结点的根去代替被删除的结点pdl1表的头结点c 。链表的插入(q next=p next; p- 计算规则：先括号内，再括号外；同层按照优先级，c. 任何一颗二叉树，度为 0 的结点比度为 2 的结点 6。堆多一个。n0 = n2 + 1a。最小/大堆定义：【（)】即先乘、除/,后加+、减；相同优先级依据结合 d。 满二叉树定理：非空满二叉树树叶数等于其分律，左结合律即为先左后右支结点数加1最小堆:是个关键码序

11、列k0， 具有如下特性（i=0，1，,n/2-1)d。链表的删除next； p-next=3.2后缀表达式：e。 满二叉树定理推论:一个非空二叉树的空子树;e;【（)】(指针)数目等于其结点数加1ki k（左孩子）(完整 word 版)大学数据结构期末知识点重点总结(考试专用)k i k 2i+2（右孩子) （即父2 个孩子）类似可以定义最大堆k i k 2i+1k i k2i+2（即父2c。按层次周游若树不空,则自上而下自左至右访问树中每个结点4。存储结构b.邻接表表示法）)为图中每个顶点建立一个单链表，第 i 个单链表中 第十章 检索的结点表示依附于顶点 Vi 的边(有向图中指以 Vi 为

12、尾的弧)(建立单链表时按结点顺序建立）1。平均检索长度（ASL）是待检索记录集合中元素/.建“初堆周游规模 n 的函数， 其定义为：ASL=一个有孩子的结点开始按堆的定义调整无右兄弟则置空a. 深度优先周游：c。插入:插入点追加到最后，自下而上依次比较父 5D（等价类）与子,直到满足堆的定义从图中某个顶点 V0 出发,访问此顶点，然后依次从 Pi 为检索第 i 个元素的概率；Ci 为找到第 i 个元素V0 的各个未被访问的邻接点出发，深度优先搜索遍 所需的比较次数2.2.d.删除:用最后结点替换被删结点 ,自上至下调整成堆判断两个结点是否在同一个集合中，查找一个给定 通的顶点都被访问到为止结点

13、的根结点的过程称为 FINDe.移出最小/归并两个集合,这个归并过程常常被称为 UNIONb. 广度优先周游：a。除余法（数组中实际的最后一个元素移到根的位置上，从图中的某个顶点 V0 出发，并在访问此顶点之后 用关键码key除以M(取散列表长度)，并取余数作为散列地址利用从左开始向下筛选对堆重新调整为散列地址7.Huffman 树a.概念“UNION/FIND算法用一棵树代表一个集合，如 依次访问 V0 的所有未被访问过的邻接点，随后按果两个结点在同一棵树中，则认为它们在同一个集 这些顶点被访问的先后次序依次访问它们的邻接合中；树中的每个结点（除根结点以外）有仅且有 点，直至图中所有与 V0

14、 有路径相通的顶点都被一个父结点；结点中仅需保存父指针信息，树本身 问到为止,若此时图中尚有顶点未被访问则另选可以 存储为一个以其结点为元素的数组中一个未曾被访问的顶点作起始点重复上述过程散列函数为:hash（key) key mod M直至图中所有顶点都被访问到为止散列函数为:hash（key) key mod M路径:从树中一个结点到另一个结点之间的分支构6。树的顺序存储结构拓扑排序b.解决冲突的方法成这两个结点间的路径a。 带右链的先根次序表示法结点路径长度：从根结点到该结点的路径上分支的 在带右链的先根次序表示中，结点按先根次序顺序数目存储在一片连续的存储单元中开散列方法：把发生冲突的

15、关键码存储在散列表主拓扑排序的方法是：1）选择一个入度为 0 的顶点 表之外（在主表外拉出单链表） 且输出之闭散列方法：把发生冲突的关键码存储在表中另一2）从图中删掉此顶点及所有的出边个位置上结构的信息字段,结点的形式为：树的路径长度：树中每个结点的路径长度之和每个结点除包括结点本身数据外 ,还附加两个表示 3）回到第 1 步继续执行，直至图空或者图不空但 c。线性探查结构的信息字段,结点的形式为：找不到无前驱(入度为 0）的顶点为止b。带权的路径长度基本思想：如果记录的基位置存储位置被占用，就树中所有叶子结点的带权路径长度之和=其中：权值 ：结点到根的路径长度info是结点的数据是右指针指向

16、结点的单源最短路径（Dijkstra）211i） =c。编码：左 0 右 1一个兄弟;ltag 是一个左标记，当结点没有子结点（g每对顶点间的最短路径（Floyd算法)i1，否则为 0d.如何构建:选取序列中最小的相加生成树如此反b。 带双标记位的先根次序表示法7。最小生成树d.散列表的检索1。假设给定的值为 K,根据所设定的散列函数 h，复a。Prim算法计算出散列地址 h（K)第六章 树概念规定当结点没有下一个兄弟（即对应的二叉树中结点没有右子结点时）rtag 为 1，否则为 0b。Kruskalc. 带双标记位的层次次序表示法c两种算法比较算法适合稠密图b。Kruskal2。 如果表中该

17、地址对应的空间未被占用，则检索失败，否则将该地址中的值与 K 比较若N，则称 k 是 k的父结 点，k是k 结点按层次次序顺序存储在一片连续的存储单元中算法适合稀疏图3。 若相等则检索成功否则,按建表时设定的处理冲突方法查找探查序列的下一个地址 ,如此反复下的子结点第七章 图第八章 内排序去，直到某个地址空间未被占用(可以插入),或者关键码比较相等（有重复记录，不需插入）为止N， 则称互为兄弟若有一条由 k 到达 ks 的路径，则 称 k 是 ks 的祖1。定义算法直接插入排序最大时间（n2）平均时间(n2)e删除标记）f.散列表的插入：遇到墓碑不停止,知道找到真正的先，ks是k的子孙a.假设

18、图中有n个顶点，e条边：空位置树/a。树转换成二叉树加线： 在树中所有兄弟结点之间加一连线抹线: 对每个结点,除了其最左孩子外 ,去除其与其含有 e=n(n-1）/2 条边的无向图称作完全图含有 e=n(n-1) 条弧的有向图称作有向完全图若边或弧的个数 e nlogn,则称作稀疏图，否则称作稠密图冒泡排序直接选择排序Shell 排序(n2） (n2）(n3/2）（n2） (n2）第十一章 索引技术概念：a.主码：数据库中的每条记录的唯一标识b。辅码：数据库中可以出现重复值的码余孩 子之间的连线b. 顶点的度(TD)=出度（OD）+入度(ID)45 顶点的出度： 以顶点 vc。连通图、连通分量

19、b。二叉树转化成树顶点的入度: 以顶点v为弧头的弧的数加线：若p结点是双亲结点的左孩子则将p的右c。连通图、连通分量孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与 p 的双亲用线连起来若图G中任意两个顶点之间都有路径相通则称抹线：抹掉原二叉树中双亲与右孩子之间的连线图为连通图快速排序堆 排 序 (n2）（n)（n)（ n)（ n)（ nlog n）(n+m）2.B 树a。定义:B 树定义：一个 m 阶 B 树满足下列条件:m除根和叶外其它每个结点至少有 个子结点；调整:将结点按层次排列，形成树结构c。森林转换成二叉树将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根 ,再以根结点为轴若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量d.强连通图、强连通分量对于有向图，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图否则，其各个极大强连通子图称作它的强连通分量基数排序最小时间(n） （n）(d(n+r)S（n）（1） （1）（d(n+r）稳 定性稳定稳定例外(空树，or）（4) 所有的叶在同一层,可以有 1 到 m1 个关键码（5) 有k 个子结点的非根结点恰好包含k1 个关键码心,顺时针旋转,构成二叉树型结构e。生成树、生成森林d。二叉树转换成森林假设一个连通图有 n 个顶点和 e 条边，其中 条