数据结构史上最全知识点合集(适用于考研,期末复习)_数据结构必背知识点

文章目录

• 第一章
• • 1.算法的设计主要取决于什么。
  • 1 .什么是数据元素。
  • 1 .时间复杂度
  • 2.空间复杂度
  • 3.数的逻辑结构
  • 4.数的存储结构
  • 5.用循环比递归的效率高吗？
  • 6.贪心算法和动态规划以及分治法的区别？
• 第二章、线性表
• • 7.什么是广义表。
  • 7.顺序表和链表的比较
  • 7.单链表和双链表的区别
  • 8.头指针和头结点的区别？
• 第三章、栈和队列
• • 9.栈和队列的区别？
  • 10.共享栈
  • 11.如何区分循环队列是队空还是队满？
  • 12.栈在括号匹配中的算法思想？
  • 13.栈在通过后缀表达式求值的算法思想？
  • 14.栈在递归中的应用？
  • 15.队列在层次遍历中的作用？
  • 17.矩阵的压缩存储
  • 17.稀疏矩阵，什么是稀疏矩阵
• 第四章、串
• • 18. 定长串用什么存储。
  • 18.串的模式匹配
  • 18.空串和空格串是否一样？并解释。
• 第五章 树与二叉树
• • 19.介绍以下各种树
  • 19.有序数列插入二叉排序树求这个的平均查找长度
  • 20.度为二的树和二叉树的区别：
  • 20. 如何存储二叉树。
  • 20.树和二叉树的相同与不同
  • 21.树的存储结构
  • 22.森林和二叉树的转换
  • 23.树的遍历
  • 24.树的性质
• 第五章 图
• • 24.树的基本定义。
  • 24.图的存储
  • 25.图的遍历
  • 26.最小生成树
  • 27.最短路径
  • 28. AOV网 拓扑排序
  • 28.怎么判断一个图是否有环？（拓扑排序）解释拓扑排序过程
  • 29.AOE网 关键路径
  • 30.稀疏的无向图用什么存储最好
• 第六章 查找
• • 30.查找算法
• 第七章 排序
• • 31.排序算法
  • 32.n个数要排序第K个数，用什么算法

第一章

1.算法的设计主要取决于什么。

算法的设计主要取决于问题的性质、输入数据的规模、时间复杂度、空间复杂度以及算法的可实现性。这些因素共同决定了选择哪种算法进行问题求解。

1 .什么是数据元素。

数据元素是数据结构中的基本单位，通常表示为数据的某个值或对象。在数组中，每个数组元素就是一个数据元素。

1 .时间复杂度

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n), 它是该算法问题规模n的函数，时间复杂度主要分析T(n) 的数量级。算法中基本运算（最深层循环内的语句）的频度与T(n) 同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为 T(n) = O(f(n))
取f(n) 中随n 增长最快的项，将其系数置为1 作为时间复杂度的度量。例如， f(n) = an3 + bn2 + cn的时向复杂度为O(n3)

上式中， O 的含义是T(n) 的数量级，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C
和n0，使得当n >= n0时，都满足0 <=T(n) <=Cf(n) 。 算法的时间复杂度不仅依赖于问题的规模n,也取决于待输入数据的性质（如输入数据元素 的初始状态）

2.空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n 的函数。记为 S(n) = O(g(n)) 一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。算法原地工作是指算法所需的辅助空间为常量，即O(1) 。

3.数的逻辑结构

指的是数据元素之间逻辑关系，与数的存储结构无关，是独立于计算机的，以下是分类图。

4.数的存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构，主要有以下4种：

顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

链式存储。不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。

索引存储。在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。

散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储。其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。

5.用循环比递归的效率高吗？

循环和递归两者是可以互换的，不能决定性的说循环的效率比递归高。

递归的优点是：代码简洁清晰，容易检查正确性；缺点是：当递归调用的次数较多时，要增加额外的堆栈处理，有可能产生堆栈溢出的情况，对执行效率有一定的影响。

循环的优点是：结构简单，速度快；缺点是：它并不能解决全部问题，有的问题适合于用递归来解决不适合用循环。

6.贪心算法和动态规划以及分治法的区别？

贪心算法顾名思义就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，得到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。

动态规划是把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。（各子问题重叠）

分治法（divide-and-conquer）：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。（各子问题独立）

分治模式在每一层递归上都有三个步骤：

分解（Divide）：将原问题分解成一系列子问题；
解决（conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。

例如归并排序。

第二章、线性表

7.什么是广义表。

广义表是对线性表的扩展，它的元素不仅可以是数据元素，也可以是其他的广义表。广义表包括原子元素和子表。广义表可以嵌套，例如 (1, 2,
(3, 4), 5) 是一个包含原子元素和子表的广义表。

7.顺序表和链表的比较

1.存取（读写）方式 顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次。

2.逻辑结构与物理结构 采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。

3.查找、插入和删除操作 对于按值查找，顺序表无序时，两者的时间复杂度均为O(n); 顺序表有序时，可采用折半查找，此时的时间复杂度为O(log2n) 。

对于按序号查找，顺序表支持随机访问，时间复杂度仅为0(1), 而链表的平均时间复杂度为O(n)
。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。

4.空间分配 顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。

7.单链表和双链表的区别

单链表 ：只能向后访问，不能逆向访问

双链表 ：在单链表的基础上添加一个指向前驱结点的指针域，实现双向遍历

8.头指针和头结点的区别？

头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。

头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。

第三章、栈和队列

9.栈和队列的区别？

队列是允许在一段进行插入另一端进行删除的线性表。队列顾名思义就像排队一样，对于进入队列的元素按“先进先出”的规则处理**，在表头进行删除在表尾进行插入**。由于队列要进行频繁的插入和删除，一般为了高效，选择用定长数组来存储队列元素，在对队列进行操作之前要判断队列是否为空或是否已满。如果想要动态长度也可以用链表来存储队列，这时要记住队头和对位指针的地址。

栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行，与队列类似一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行，因此要有一个size变量来记录当前栈的大小，当进栈时size不能超过数组长度，size+1，出栈时栈不为空，size-1。

10.共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。这样能够更有效的利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。

11.如何区分循环队列是队空还是队满？

普通情况下，循环队列队空和队满的判定条件是一样的，都是Q.front == Q.rear。

ps:队头指针指向第一个数；队尾指针指向最后一个数的下一个位置，即将要入队的位置。

方法一：牺牲一个单元来区分队空和队满，这个时候
(Q.rear+1)%MaxSize == Q.front才是队满标志 。

方法二：类型中增设表示元素个数的数据成员。
这样，队空的条件为Q.size == 0;
队满的条件为Q.size== MaxSize。

12.栈在括号匹配中的算法思想？

括号匹配算法思想

（1）出现的凡是“左括号”，则进栈；

（2）出现的是“右括号”，

首先检查栈是否空？

若栈空，则表明该“右括号”多余

否则和栈顶元素比较

若相匹配，则栈顶“左括号出栈”

否则表明不匹配

（3）表达式检验结束时，

若栈空，则表明表达式中匹配正确

否则表明“左括号”有余；

13.栈在通过后缀表达式求值的算法思想？

顺序扫描表达式的每一项，然后根据它的类型做如下相应操作：若该项是操作数，则将其压入栈中；若该项是操作符,则连续从栈中退出两个操作数y 和x,
形成运算指令XY, 并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。

14.栈在递归中的应用？

递归是一种重要的程序设计方法。简单地说，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归
策略只需少量的代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量。但在通常情况下，它的效率并不是太高。

将递归算法转换为非递归算法，通常需要借助栈来实现这种转换。

15.队列在层次遍历中的作用？

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，待当前层或当前行处理完毕，就可以处理下一层或下一行。使用队列是为了保存下一步的处理顺序。下面用二叉树层次遍历的例子，说明队列的应用。

16.队列在计算机系统中的应用？

队列在计算机系统中的应用非常广泛，以下仅从两个方面来简述队列在计算机系统中的作用：第一个方面是解决主机与外部设备之间速度不匹配的问题，第二个方面是解决由多用户引起
的资源竞争问题。

对于第一个方面，仅以主机和打印机之间速度不匹配的问题为例做简要说明。主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，由于速度不匹配，若直接把输出的
数据送给打印机打印显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印输出的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样做既保证了打印数据的正确，又使主机提高了效率。由此可见，打印数据缓冲区中所存储的数据就是一个队列。

对于第二个方面， CPU (即中央处理器，它包括运算器和控制器）资源的竞争就是一个典型
的例子。在一个带有多终端的计算机系统上，有多个用户需要CPU 各自运行自己的程序，它们分别通过各自的终端向操作系统提出占用CPU 的请求。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列，每次把CPU 分配给队首请求的用户使用。当相应的程序运行结束或用完规定的时间间隔后，令其出队，再把CPU 分配给新的队首请求的用户使用。这样既能满足每个用户的请求，又使CPU 能够正常运行。

17.矩阵的压缩存储

数据结构中，提供针对某些特殊矩阵的压缩存储结构。这里所说的特殊矩阵，主要分为以下两类：

含有大量相同数据元素的矩阵，比如对称矩阵； 含有大量 0 元素的矩阵，比如稀疏矩阵、上（下）三角矩阵；
针对以上两类矩阵，数据结构的压缩存储思想是：矩阵中的相同数据元素（包括元素 0）只存储一个。

17.稀疏矩阵，什么是稀疏矩阵

稀疏矩阵是指大部分元素为零的矩阵。为了节省存储空间，稀疏矩阵通常采用压缩存储格式，例如三元组（行号、列号、非零值）存储非零元素，而不是直接存储所有矩阵元素。

第四章、串

快速唤起记忆知识框架：

18. 定长串用什么存储。

定长串通常使用顺序存储，即使用一个固定大小的数组来存储字符串。定长串的长度在创建时就确定，数组大小与串的长度一致。

18.串的模式匹配

子串的定位操作通常称为串的模式匹配，他求的是子串（常称模式串）在主串中的位置。

暴力模式匹配算法的思想是：从主串的第一个字符起，与子串的第一个字符比较，相等则继续比较；不等则从主串的下一个位置起，继续和子串开始比较，直到最后看是否匹配成功。

以下的子串为：‘abcac’:

改进的模式匹配算法-----KMP算法：

在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

18.空串和空格串是否一样？并解释。

空串和空格串是不一样的。
空串是一个长度为0的字符串，没有任何字符。空格串是一个由一个或多个空格字符组成的字符串，长度大于0，包含至少一个空格字符。

第五章 树与二叉树

19.介绍以下各种树

二叉树：有左右子树的区分和度不超过2。（度是指节点所拥有的子树个数）
二叉排序树：左子树均小于根，根均小于右节点。（左小右大，根中间）
线索二叉树：设置两个标识标记左右指针指向的是孩子还是前躯节点。
平衡二叉树：左右子树高度差绝对值小于等于1。
哈夫曼树：又称最优二叉树，是一种带权路径长度最短的二叉树。给定一组权值，通过特定的算法构造出哈夫曼树，使得树中所有叶子节点的带权路径长度之和最小
完全二叉树：设二叉树的深度为h，除第h层外，其它各层的节点数都达到最大个数，且第h层所有的节点都连续集中在最左边，这就是完全二叉树

19.有序数列插入二叉排序树求这个的平均查找长度

20.度为二的树和二叉树的区别：

二叉树有左右子树之分。

20. 如何存储二叉树。

链式存储：每个节点包含数据、左子节点指针和右子节点指针，适合二叉树的存储。通常使用指针或引用来表示左右子节点。
顺序存储：使用数组存储二叉树，当二叉树是完全二叉树时，顺序存储可以更节省空间，节点的父子关系通过数组下标来表示。

20.树和二叉树的相同与不同

相同点：树和二叉树都是层次化的非线性数据结构，节点之间有父子关系。
不同点：
1.树：每个节点可以有多个子节点。
2.二叉树：每个节点最多有两个子节点（左子节点和右子节点）。

21.树的存储结构

双亲表示法：每个结点中保存指向双亲的“指针”（实则为数组下标）

孩子表示法：顺序存储各个结点，每个结点中保存孩子链表头指针；

孩子兄弟表示法：节点含数据、指向第一个孩子和下一个兄弟的指针，能方便实现树与二叉树的转换。

22.森林和二叉树的转换

（1）森林转换二叉树：

先将森林的各个树转换为二叉树，再将各个树的根结点视为兄弟关系绑在一起即可；如图所示：

（2）二叉树转换森林：

左边为孩子，右边为兄弟，最右边一条线上的为各个树的根结点；如图所示：

23.树的遍历

先序中序后序三种，递归实现。
先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

24.树的性质

性质3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0 必定为n2＋1 （即n0=n2+1）

性质4:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i， 其右孩子编号必为2i＋1；其双亲的编号必为i/2。

第五章 图

24.树的基本定义。

树是由一个根节点和若干子节点构成的非线性数据结构。树结构是一种层次化的结构，其中每个节点至多有一个父节点，并且没有环。树的每个节点可以有零个或多个子节点。

24.图的存储

1.邻接矩阵：用两个数组，一个数组保存顶点集，一个数组保存边集。

2.邻接表：数组与链表相结合的存储方法。

25.图的遍历

1.深度优先遍历（DFS）：从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
2.广度优先遍历（BFS）：类似于树的层次遍历。

26.最小生成树

1.普里姆（prime）：
先将一个起点加入最小生成树，之后不断寻找与最小生成树相连的边权最小的边能通向的点，并将其加入最小生成树，直至所有顶点都在最小生成树中
2.克鲁斯卡尔（kluskal）:
在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。
对比普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔(Kruskal)算法主要针对边来展开，边数较少时效率非常高，所以对于稀疏图有很大的优势；
普里姆(Prim)算法对于稠密图，边数非常多的情况更好一些
所有权值都不相同，或者有相同的边，但是在构造最小生成树的过程中权值相等的边都被并入到最小生成树中的图，其最小生成树是唯一的。

27.最短路径

迪杰斯特拉
思想：从图中选取到源点v0路径长度最短的顶点并入到集合S中，修改顶点v0到剩下的顶点的最短路径长度值，直到所有顶点都并入到S中为止。

Folyd算法
三重for循环

28. AOV网 拓扑排序

实现思路：
从有向无环图中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

28.怎么判断一个图是否有环？（拓扑排序）解释拓扑排序过程

拓扑排序用于判断有向图是否有环。拓扑排序是将有向图中的顶点按依赖关系排列成一个线性顺序。若图中存在环，则无法完成拓扑排序。
过程：从入度为0的节点开始，逐一将其加入拓扑序列，并删除其相关的边。如果删除后某节点的入度变为0，则将该节点加入拓扑序列。继续此过程，直到所有节点都被处理。如果途中无法处理所有节点，说明图中存在环。

29.AOE网 关键路径

关键路径：在AOE（边表示活动）网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。把关键路径上的活动称为关键活动。关键路径既是最短，又是最长。最短：完成工期的最短事件。最长：图中的最长路径。

30.稀疏的无向图用什么存储最好

邻接表是存储稀疏无向图最好的方法。由于在稀疏图中，边的数量远小于顶点的平方数，使用邻接表可以节省大量的空间。邻接表仅存储实际存在的边，避免了邻接矩阵存储所有顶点对的无用边（通常为零）

第六章 查找

平均查找长度

其中，n代表记录的个数；pi代表查找第i个记录的概率 ( 通常认为pi =1/n )；ci代表找到第i个记录所需的比较次数。

30.查找算法

1. 顺序查找:
   从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。 ASLs(n)=(1+2+ … +n)/n =(n+1)/2；
   2.二分查找(折半查找):
   基本思路：设R[low,high]是当前的查找区间，首先确定该区间的中间位置mid=(low+high)/2，然后将待查的k值与R[mid]比较，若相等，则查找成功，返回该位置。否则需要确定新的查找区间。若R[mid]>k,则新的查找区间为[low,…,mid-1],类似地，若R[mid]<k,则新的查找区间为[mid+1,high]时间复杂度:O(log2n)
   3.分块查找:
   分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。
   分块查找的算法为顺序查找和折半查找两种算法的简单合成
   

4.二叉排序树
5.平衡二叉树
左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值≤ 1。任一结点的平衡因子只能取：-1、0 或 1；如果树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是AVL树；
如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。

【LL平衡旋转】若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转(以B为旋转轴）。

【RR平衡旋转】若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转(以B为旋转轴）。

【LR平衡旋转】若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转(以插入的结点C为旋转轴）。

【RL平衡旋转】若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转(以插入的结点C为旋转轴）。

6.B树
①树中每个结点至多有m棵子树（至多m-1个关键字）；
②若根结点不是叶子结点，则至少有两棵子树；
③除根之外的所有非终端结点至少有⌈ m/2 ⌉课子树（至少⌈ m/2 ⌉-1个关键字）；
④所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便千分析B-树的查找性能）；

①树高最高：因为B树中每个结点最多有m棵子树，m-1个关键字，所以在一棵高度为h的m阶B树中关键字的个数应满足n≤(m- 1)(1+m+m2 +…+mh-1)=mh-1,因此有h≥ logm(n+1)。
②树高最低：若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树的高度达到最大。由B树的定义:第一层至少有1个结点;第二层至少有2个结点;除根结点外的每个非终端结点至少有⌈m/2⌉棵子树，则第三层至少有2⌈m/2⌉个结点…第h+1层至少有2(⌈m/2 )h-1个结点，注意到第h+1层是不包含任何信息的叶结点。
对于关键字个数为n的B树，叶结点即查找不成功的结点为n+1,由此有n+1≥2(⌈m/2⌉)h-1,即若树高最小，则h≤log⌈m/2⌉((n+1)/2)+ 1.

7.散列表

哈希函数的构造:

除留余数法:
Hash(key)=key mod p (p是一个整数)。该方法的关键是选取有个合适的p值，一般情况下，若表长为m，取p为小于等于m的最大质数
直接定址法:
Hash(key) = a·key + b (a、b为常数)
①优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突。
②缺点：要占用连续地址空间，空间效率低。

冲突处理

开放定址法:开放定址法的基本思想为有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。其冲突函数为Hi=(Hash(key)+di) mod m ( 1≤i < m )

二次探测法

链地址法
相同哈希地址的记录链成一单链表，m个哈希地址就设m个单链表，然后用用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
①取数据元素的关键字key，计算其哈希函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行②解决冲突。
②利用链表的前插法或后插法将该元素插入此链表。
查找散列表的平均查找长度
【例子】已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，设每个记录的查找概率相等。
解： ①用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m。

在此方法中，ASL=(16+2+33+4+9)/12=2.5。
②用链地址法处理冲突

在此方法中，ASL=(16+24+3+4)/12=1.75。

第七章 排序

31.排序算法

32.n个数要排序第K个数，用什么算法