考研数据结构的知识点汇总_败者树的高怎么算

第一章
1.数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
2.数据元素：数据的基本单位，（一个数据元素可由若干数据项组成）。
3.数据项：数据的不可分割的最小单位。
4.数据对象：性质相同的数据元素的集合，是数据的一个子集。
5.数据结构：指互相之间存在着一种或多种特定关系的数据元素的集合。包括逻辑结构，存储结构和对数据的运算。（数据元素都不是孤立存在的）。
数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象及对象间的关系和施加于对象的操作等的学科。
用一个由若干位组合起来形成的一个位串表示一个数据元素，称这个位串为元素（element）或者结点（Node）。
数据结构是一个二元组Data_Structure＝（D，R），其中，D是数据元素的有限集，R是D上关系的有限集。
6.抽象数据类型（ADT）：指一个数学模型以及定义在该模型上的一组操作。只取决于它的一组逻辑特性。用一个三元组表示（D,S,P）。
7.数据类型：是程序设计语言中的一个概念，它是一个值得集合和操作的集合。
8.逻辑结构：是指数据之间关系的描述，与数据的存储结构无关。分为线性结构和非线性结构，通常分为四类结构：
（1）集合：结构中的数据元素除了同属于一种类型外，别无其它关系。
（2）线性结构：结构中的数据元素之间存在一对一的关系。
（3）树型结构：结构中的数据元素之间存在一对多的关系。
（4）图状结构（网状结构）：结构中的数据元素之间存在多对多的关系。
9.存储结构：是指数据结构在计算机中的表示，又称为数据的物理结构。它包括数据元素的表示和关系的表示，通常由四种基本的存储方法实现：
（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数据元素间的逻辑关系。存储密度大。但有些操作（如插入、删除）效率较差。
（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、删除等），但存储空间开销大（用于指针），另外不能折半查找等。
（3）索引存储方式。除数据元素存储在一组地址连续的内存空间外，还需建立一个索引表，索引表中索引指示存储结点的存储位置（下标）或存储区间端点（下标）。
（4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。
10.算法:是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。
11.算法的特性：⑴有穷性⑵确定性⑶可行性⑷输入⑸输出。
12.算法的设计目标：正确性，可读性，健壮性，高效率与低存储量需求
算法和程序十分相似，但又有区别。程序不一定具有有穷性，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。
13.算法的时间复杂度：以基本运算的原操作重复执行的次数作为算法的时间度量。一般情况下，算法中基本运算次数T(n)是问题规模n（输入量的多少，称之为问题规模）的某个函数
f(n)，记作：T(n)＝Ο(f(n))
14.数据结构的主要运算：1.建立（create）一个数据结构
2.消除（destroy）一个数据结构
3.从一个数据结构中删除（delete）一个数据元素
4.把一个数据结构中插入（insert）到一个数据元素
5.对一个数据结构进行访问（access）
6.对一个数据结构进行修改（modify）
7.对一个数据结构进行排序（sort）
8. 对一个数据结构进行查找（search）
15.频度:在分析算法时间复杂度时，有时需要估算基本操作的原操作，它是执行次数最多的一个操作，该操作重复执行的次数称为频度。
第二章
1.线性表：具有相同特性数据元素的一个有限序列，该序列中所含元素的个数叫做线性表的长度。
2.逻辑特性：线性表只有一个表头元素，只有一个表尾元素，表头元素没有前驱，表尾元素没有后继。
3.线性结构包括：线性表、栈、队列、串。
4.线性表的存储结构分为：顺序存储结构和链式存储结构。
5.顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。
特性：1.随机访问特性 2.占有连续的存储空间 3.做插入操作时要移动多个元素
6.链表：一种物理储存单元上非连续，非顺序的存储结构。
特性：1.不支持随机访问 2.结点的存储空间利用率较低 3.支持存储空间的动态分布 4.做插入操作时不需要移动元素
7.顺序表与链表各自的特点：
基于空间的比较：①.存储分配方式：
顺序表的存储空间是静态分配的（一次分配）
链表的存储空间是动态分布的（多次分配）
②.存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储总量）
顺序表的存储密度=1
链表的存储密度<1(因为结点中有指针域)
基于时间的比较：①.存取方式：顺序表可以随机存取，链表只能顺序存取
②.插入/删除时移动元素的个数：顺序表平均需移动近一半的元素，链表不需要移动元素，只需要修改指针。
8.插入一个元素时所需移动元素次数的期望值（平均次数）：E=1/(n+1) ∑_(i=1)^(n+1)▒(n-i+1) =n/2
删除一个元素时所需移动元素次数的期望值（平均次数）：E=1/n ∑_(i=1)^n▒(n-i) =(n-1)/2
9.静态链表：用数组描述的链表
①一般链表结点空间来自于整个内存，静态链表则来自于结构体数组。
②静态链表中的指针不是用来存储内存地址的指针型变量，而是一个存储数组下标的整形变量。
10.在链表中设置头结点的作用：主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
11.根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和多重链表；而又根据指针的连接方式，链表又可分成动态链表和静态链表。
12.顺序存储结构是通过物理上相邻表示元素之间的关系的;链式存储结构是通过指针表示元素之间的关系的。
13.试述头结点,首元结点,头指针这三个概念的区别？
答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。
第三章
1.栈：是一种只能在一端（表尾）进行插入或删除操作的线性表。
允许进行插入或删除的一端成为栈顶（TOP），表的另一端成为栈底（栈底固定不变）
主要特点：先进后出（FILO）
可用顺序表和链表来存储栈，可分为顺序栈和链栈。
n个顺序入栈，可在任意时刻出栈，则出栈序列个数：N=1/(n+1) C_2n^n=(2n)!/[(n+1)!n!]
存储栈的一组数组根据是否需要增大可分为静态顺序栈和动态顺序栈。
2.队列：是一种仅允许在表的一端（队尾rear）进行插入，在表的另一端（队头Front）进行删除的线性表
主要特点：先进先出（FIFO）
可用顺序表和链表来存储队列，可分为顺序队列和链队
3.
名称 空状态 满状态
顺序栈 St.top==-1 St.topmaxSize-1
链栈 1st->nextNULL 无
循环队列 qu.rearqu.front （qu.rear+1）%maxsizequ.front
链队 1qu->frontNULL或1qu->frontNULL 无
4.两个栈可以模拟一个队列，但反之不行。
5.循环队列个数：n=（尾-头+表长）%表长
6．共享栈的主要作用：为了提高内存的利用率和减少溢出的可能性。
7.递归：一个函数（或过程）直接或间接地调用本身
递归程序执行中需借助栈这种数据结构来实现。
有效的递归调用函数（或过程）应包括：递推规则、终止条件。
递归程序的优、缺点是什么？
答：递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间较多，运行效率低。
8.循环队列：用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入和队头删除），容易造成“假溢出”现象，即队尾已到达一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度（容量）。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储单元”或“作标记”的方法解决“队满”和“队空”的判定问题。
第四章
1.串（string）：由零个或者多个字符组成的有限序列。
2.串的长度：串中字符的个数。
3.含有零个元素的串叫空串，由一个或多个空格组成的串称为空格串。
4.子串：串中任意连续的字符组成的序列。
5.主串：含有子串的串。
6.用子串第一个字符的位置作为子串在主串中的位置。
7．当两个串的长度相等并且各个对应位置的字符都相等时，两个串相等。
8.串值：双引号括起来的子串。
9.KMP算法的优点：主串指针不回溯。
10.串的存储表示：
（1）串的定长顺序存储表示
与顺序表的定义类似，使用定长存储串只需要分配一片连续的内存，即定义一个字符串类型的数组来存储字符即可完成在连续内存区域中存储的目的。在设置长度的时候，需要多留一位（字符串首位）以存储字符串的长度。
（2）堆分配存储表示
以一段连续分配的地址作为存储字符串的地址，与定长不同的是，要求使用malloc()与free()函数进行内存的动态添加与删除。如果分配地址成功，要求返回一个指向起始地址的指针ch，方便进行后续内存的访问。
（3）串的块链存储表示
用链表来表示串，存储串的信息。在串的定长存储与堆分配存储中，串的一个个字符都是作为单个的单元或者整体连续的内存开始存储的。在串块链存储表示中由于链表的结构因素，使得每一个节点会由不同的字符所组成，节点中的字符数目也不一定相同。由于串的长度不一定是节点大小的整倍数，则链表的最后一个节点不一定全部都是字符，相对地，可以由‘#’符号进行补齐。以链表存储串值时，需要同时设置一个尾指针来指示链表中的最后一个节点。
第五章
1.矩阵的压缩存储：对多个值相同的元素只分配一个存储空间，对零元素不分配空间。
2.相同的元素或者零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵，反之称为稀疏矩阵。
3.稀疏矩阵的顺序存储方式：三元组表示法，伪地址表示法。
稀疏矩阵的链序存储方式：邻接表表示法，十字链表表示法。
4.广义表（列表）：表元素可以是原子或者广义表的一种线性表的扩展结构。
5.广义表的长度：表中最上层元素的个数。
6.广义表的深度：表中括号的最大层数。
7.当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾。
8.广义表通常采用链式存储结构，可用头尾链表存储表示和扩展线性表存储结构。
第六章
1.树的定义是递归的，树的结点包括一个数据元素及若干指向其子树的分支。
2.结点的度：结点拥有的子树的个数或者分支的个数。
3.树的度：树中各节点度的最大值。
4.叶子结点（终端节点）：指度为0的结点。
5. 分支结点：（非终端节点）指度不为0的结点；除了根节点之外的非终端结点称为内部节点。
6.孩子：结点的子树的根。
双亲：B结点是A结点的孩子；则A结点是B结点的双亲。
兄弟：同一个双亲的孩子之间互为孩子。
祖先：从根节点到某结点的路径上的所有结点
子孙：以某结点为根的子树中的所有结点。
堂兄弟：双亲在同一层的结点互为堂兄弟。
7.树的高度（深度）：树中结点的最大层次。
8.结点的深度和高度：
（1）结点的深度是从根节点到该结点路径上的结点个数。
（2）从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径长度为该结点在树中的高度。
（3）根节点的高度为树的高度。
9.有序树：树中结点的子树从左到右是有次序的，不能互换
无序树：树中结点的子树没有顺序，可以任意互换
10.丰满树（理想平衡树）：除最底层外，其它层都是满的。
11.森林：若干棵互不相交的树的集合。
12.树的存储结构：树的顺序存储结构为双亲表示法（每个结点中只保存了指示哪个结点是它的双亲结点的信息）；树的链式存储为孩子表示法或孩子兄弟表示法。
13.二叉树：（1）每个结点最多只有两棵子树，即二叉树中结点的度只能是0,1,2.
（2）子树有左右顺序之分，不能颠倒。
14.满二叉树：树中所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下层。
完全二叉树：对一棵深度为k、有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同的这样的二叉树。
（一棵完全二叉树一定是由一棵满二叉树从右至左从上至下，挨个删除结点所得到的）
15.二叉树的主要性质：
性质一：非空二叉树上叶子结点数等于双分支结点数加一。
性质二：二叉树的第i层最多有2^（i-1）个结点。
性质三：高度（或深度）为k的二叉树最多有（2^k）-1个结点。
性质四：有n个结点的完全二叉树，对各结点从上而下、从左到右依次编号（编号范围为1到n），则结点关系如下。
1.若i为某结点a的编号，则：
2.如果i不等于1，则a的双亲结点编号为 ⌊ⅈ/2⌋。
3.如果2i<=n，则a左孩子结点的编号为2i；如果2i>n，则a无左孩子结点。
4.如果2i+1<=n，则a右孩子结点的编号为2i+1；如果2i+1>n，则a无右孩子结点。
性质五：给定n（n>=1）个结点，能构成1/(n+1) C_2n^n种不同的二叉树。
性质六：具有n（n>=1）个结点的完全二叉树的高度（或深度）为⌊log_2⁡n ⌋+1。
16.二叉树的存储结构：
1.顺序存储结构：用一个数组来存储一棵二叉树（最适合于完全二叉树，用于存储一般二叉树会浪费大量的存储空间）
局限性：不便于存储任意形态的二叉树。
2.链式存储结构：设计出的一种含有一个数据域和两个指针域的链式结点结构。
17.二叉树的遍历：先序遍历、中序遍历、后序遍历和层次遍历。
18.根据二叉树的前、中、后3种遍历序列中的前和中、中和后两对遍历序列都可以唯一确定一棵二叉树，而根据前和后这对遍历序列则不能确定一棵二叉树。
19.对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫做线索化，被线索化了的二叉树称为线索二叉树
20.树（和森林）的遍历：先序遍历（转换为二叉树后对应二叉树的先序遍历）
后序遍历（转换为二叉树后对应二叉树的中序遍历）
21.哈夫曼树（最优二叉树），特点：带权路径最短
路径：指从树中一个结点到另一个结点的分支所构成的路线。
路径长度：指路径上的分支数目。
树的路径长度：指根到每个结点的路径长度之和
带权路径长度：结点具有权值，从该结点到根之间的路径长度乘以结点的权值为该结点的带权路径长度。
树的带权路径长度（WPL）：指树中所有叶子结点的带权路径长度之和。
哈夫曼树的特点：1.权值越大的结点，距离根结点越近。
2.树中没有度为1的结点，这类书又叫做正规（严格）二叉树。
3.树的带权路径长度最短。
22．树在计算机内的表示方式有：(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法。
第七章
1.图：由结点的有穷集合V和边的集合E组成。常常将结点称为顶点，边是顶点的有序偶对。
2.图可分为无向图和有向图（有向图中，通常将边称为弧，含箭头的一端称为弧头，另一端称为弧尾）。
3.与顶点v相关的边的条数称为顶点v的度，指向顶点v的边的条数称为顶点v的入度，由顶点v发出的边的条数称为顶点v的出度。
4.有向完全图：有n个顶点，具有n（n-1）条边的有向图
无向完全图：有n个顶点，具有n（n-1）/2条边的无向图。
5.在一个图中，路径为相邻顶点序偶所构成的序列；路径长度是指路径上边的数目。
6.简单路径：序列中顶点不重复出现的路径。
7.回路（环）：一条路径第一个顶点和最后一个顶点相同的路径。
8.连通图：在无向图中，如果图中任意两个顶点之间都连通，则称该图为连通图；否则，图中的极大连通子图称为连通分量。
9.强连通图：在有向图中，如果对于每一对顶点A和B，从A到B和从B到A都有路径，则称该图为强连通图；否则，图中的极大强连通子图称为强连通分量。
10.邻接矩阵：图的顺序存储结构，代表顶点之间相邻关系的矩阵。
11.邻接表：图的一种链式存储结构，邻接表由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成。
12.图的深度优先搜索遍历(DFS)类似于二叉树的先序遍历；图的广度优先搜索遍历（BFS）类似于树的层次遍历。（两种遍历方法都针对连通图的）
13.最小（代价）生成树：prim算法和kruskal算法。（都是针对无向图的）
14.在构造最小生成树时，如果图中所有边的权值均不相等，则其最小生成树是唯一的。（图中存在边权值相等时生成树也可能唯一）
15.最短路径：Dijkstral算法和Floyd算法（求图中任意一对顶点间的最短路径，通常使用Floyd算法）。
16.AOV网（活动在顶点上的网）：是一种可以形象地反映出整个工程各个活动之间的先后关系的有向图（以顶点表示活动，以边表示活动的先后次序且没有回路）
17.AOE网（活动在边上的网）：边表示活动，边有权值，边代表活动的持续时间。
18.关键路径：在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径；关键路径上的活动成为关键活动。
19. 遍历不唯一的因素有：开始遍历的顶点不同；存储结构不同；在邻接表情况下邻接点的顺序不同。
第八章
1．排序：将原本无序的序列重新排列成有序序列的过程。
2．稳定性：指当待排序序列中有两个或两个以上相同的关键字时，排序前和排序后这些关键字的相对位置，没有发生变化就是稳定，否则就是不稳定。
3.外部排序：对外存中的记录进行排序（相对于内部排序而言）
外排序的基本操作过程是：生成有序归并段（顺串）和归并
4.外部排序：1.m个初始归并段进行k路归并，归并的趟数为⌈〖log〗_k⁡m ⌉。
2.每次归并，所有记录都要进行两次I/O操作。
3.k路归并的败者树的高度为⌈〖log〗_2⁡k ⌉+1，即时间复杂度是O（〖log〗_2⁡k）。
4.k路归并的败者树的建树时间复杂度为O（〖klog〗_2⁡k）
5．直接插入排序用监视哨的作用是：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。
第九章
1．查找：给定一个定值k，在含有n个记录的表中找出关键字等于k的记录。
2.通常把查找过程中对关键字的平均比较次数（也称平均查找长度ASL）作为衡量一个查找算法效率优劣的标准。
3.折半查找要求线性表是有序的，其时间复杂度为〖log〗_2⁡n。
4.描述折半查找的判定树：把当前查找区间中的中间位置上的记录作为树根，左子表和右子表中的记录分别作为根的左子树和右子树，由此得到的二叉树。
5.二叉排序树：（1）若它的左子树不空，则左子树上的所有关键字的值均小于根关键字的值。
（2）若它的右子树不空，则右子树上的所有关键字的值均大于根关键字的值。
（3）左右子树又各是一棵二叉排序树。
6.平衡二叉树：以树中所有结点为根的树的左右子树高度之差的绝对值不超过1.