数据结构复习知识点

数据结构
1.数据结构三要素是什么？逻辑结构包括什么？存储结构包括什么？
逻辑结构、存储结构、数据运算
逻辑结构包括线性结构和非线性结构
线性结构包括线性表、栈、队列，非线性结构包括树、图集合
存储结构包括顺序存储、链式存储、索引存储和散列存储

2.O(n)的大O是什么意思？什么是时间复杂度? ★★★
算法效率的度量通过时间复杂度和空间复杂度。
大O表示的是最坏情况下的时间复杂度，也就是最坏情况下算法中所有语句的频度之和的数量级（一般用大O表示算法复杂度只需要取次数最高的项而且去掉系数就OK）
频度：语句重复执行的次数
时间复杂度就是用来衡量程序运行时间的一个描述，可以用来方便开发者估算出程序的运行时间。
如果某一算法的时间复杂度为O（n2），表明该算法的运行时间与n2这个数量级成正比。n表示问题规模。比如要遍历一个n×n的矩阵的所有元素，时间复杂度就是O（n2）
空间复杂度：算法所消耗的存储空间，用来存放指令、常数、变量等
算法原地工作指算法所需的辅助空间为常量，空间复杂度为O（1）

3.什么是线性表？什么是顺序表？什么是链表？
线性表是具有相同数据类型的n个数据元素的有限序列
顺序表是线性表的顺序存储，特点：表中元素的逻辑顺序与物理顺序相同
插入（最好情况在表尾插入O（1））：O（n）
删除（最好情况在表尾插入O（1））：O（n）
按值查找：o（n） 按位查找O（1）
单链表是线性表的链式存储
建立链表：
头插法（用于链表逆置）、尾插法：O（n） 每插入一个：O（1）
按位查找、按值查找：O(n)
插入节点：遍历链表查找第i-1个元素O（n），插入O（1）
删除：遍历查找第i-1个元素O（n），插入O（1）

4.链表的种类？
（1）单链表：对每个链表节点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。
（2）双链表：想要访问单链表的前驱结点时只能从头开始遍历，时间复杂度高，为此引入双链表。双链表结点中除了数据域，有两个指针prior和next，分别指向前驱结点和后继结点，找某结点的前驱只需通过prior指针，时间复杂度降为O（1）
（3）循环单链表：最后一个结点的指针指向头结点，使整个链表形成一个环。
循环双链表：表尾结点的next指针指向头结点，头结点的prior指针指向表尾结点。
好处：单链表只能从表头结点开始遍历所有结点，而循环单链表可以从表中的任一结点开始遍历整个链表。对单链表我们常常设立头指针，这样在表头表尾操作的时间复杂度分别为O(1)和O(n)，而对于循环列表常常设立尾指针，不管是在表头操作还是表尾操作，时间复杂度都为O（1）
（4）静态链表：借助数组描述线性表的链式存储结构，结点包括数据域和指针域，指针域存放的是结点的相对地址（数组下标），又称游标。需要预先分配一块连续的内存空间。
优点：增删改查不用移动大量元素。缺点：不能随机存取，容量固定不可变。应用场景：不支持指针的高级语言（Basic) 或 数据元素固定不变的场景，如操作系统中的文件分配表FAT。

5.顺序存储结构和链式存储结构的优点★★★
顺序存储结构的优点：
1.最主要的特点是可以随机存取，即通过首地址和元素序号可在时间O（1）内找到指定的元素，链表只能从表头开始遍历，顺序存取元素。
2.存储密度高，每个节点只存储数据元素（链式存储还要存指针）（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比）
3.各种语言都有数组，方便顺序存储的实现，好理解。

链式存储结构的优点：
1.进行插入、删除操作时很方便，不需要移动数据元素。
顺序存储在进行插入操作时需要将插入位置之后的元素全部后移一位，时间复杂度为O（n），而链式存储只需要修改插入位置前驱后继节点指针的指向，时间复杂度为n（1）；
2.不用预先估计存储空间的规模，在需要时向内存申请空间即可，操作灵活。
而顺序存储包含两种方式，静态分配和动态分配，若采用静态分配，一旦存储空间满了就不能再扩充，因此为了规避内存溢出的风险，只能尽量分配足够大的存储空间，但这样又会导致空间的浪费。而动态分配虽然可以扩充存储空间，但是需要移动大量元素，操作效率低。

索引存储：
优点：检索速度快
缺点：附加的索引表额外占用存储空间，增加和删除元素时也要修改索引表。

6.解释一下顺序存储与链式存储★★★
顺序存储是指在内存中开辟连续的存储空间来存放数据，把逻辑上相邻的元素存储在物理位置也相邻的存储单元中。
链式存储的存储空间不是连续的，借助指示元素存储地址的指针来表示元素间的逻辑关系。对每个链表节点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针，通过指针指向下一元素，将所有的元素串起来，从而形成了一个链表。
索引存储：存储元素信息的同时，还简历附加的索引表。
散列存储：根据元素的关键字直接计算出该元素的存储地址。

7.头指针和头结点的区别？★★
不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理。
引入头结点的优点：
1.由于第一个数据节点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在链表其他位置上的操作一致，无需进行特殊处理。
2.无论链表是否为空，其头指针都是指向头结点的非空指针，因此空表和非空表的处理也得到了统一。

8.判断链表是否有环（非常重要！）★★★★★★★
“快慢指针”：创建两个指针fast和slow，开始时两个指针都指向链表头head，在每一步操作中slow向前走一步，fast向前走两步，由于fast比slow移动的快，如果有环，两个指针就会相遇。

9.栈和队列的区别和内存结构★★★
栈（Stack）：是只允许在一端进行插入和删除操作的线性表；先进后出（FILO)
队列（Queue）：是只允许在表的一端进行插入，而在表的另一端进行删除的线性表；先进先出（FIFO）
栈：栈有两种存储方式，采用顺序存储的栈称为顺序栈，采用链式存储的栈称为链栈。顺序栈利用一组地址连续的存储单元存放数据元素，同时附设一个指针指示当前栈顶元素位置。链栈是利用一个单链表存储数据元素，并将表头作为栈顶进行插入和删除操作。
队列：队列也是分为顺序存储和链式存储两种方式，顺序存储是利用一组地址连续的存储单元存放数据元素，并附设两个指针，通常front指针指向队头元素，rear指针指向队尾元素的下一个位置。链式存储是利用一个带有头指针和尾指针的链表存储数据元素。

10.有一个循环队列Q，里面的编号是0到n-1，头尾指针分别是front，rear，现在求Q中元素的个数？★★
因为出队操作会导致队头的存储空间空闲，当rear指针指到maxsize的时候，其实是一种“假溢出”，这时候队列并没有满。为了解决这个问题，我们把存储队列元素的表从逻辑上视为一个环，称为循环队列。
初始：front=rear=0；
出队：front = (front+1)%maxsize 队头指针加一取模
入队：rear = (raer+1)%maxsize 队尾指针加1取模
队列长度=(rear-front+maxsize)%maxsize

11.如何区分循环队列是队空还是队满？★★★
队满条件和队空条件都是rear = front
因此为了区分这两个条件，可以采用的处理方式为：
1.入队时少用一个存储单元，将差一个不满的条件视为队满，判断队空条件不变：队头和队尾指针在同一位置时，队空 rear = front，判断队满条件变为：队头指针在队尾指针的下一位置时，队满，也就是（rear+1）%maxsize = front
2.增设一个数据成员记录元素个数，队空条件为size = 0；队满条件为size=maxsize。

12.栈的应用
（1）括号匹配：匹配过程为从左至右扫描表达式，每当遇到一个右括号时，就判断他和最后出现的那个左括号是否匹配，因此用栈存储被扫描到的左括号。，每当扫描到右括号时，就让栈顶的左括号出栈。
（2）后缀表达式的运算：运算过程是从左到右扫描表达式，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体成一个新的操作数。最后出现的操作数最先被运算，所以用栈来存储操作数。
（3）中缀表达式转后缀表达式：栈中存储还未确定运算顺序的运算符。
（4）递归：最后被调用的函数最先执行结束。
（5）进制转换：以二进制转十进制为例，读入顺序为从低位到高位，而为了简化权值的计算应该从低位到高位加权，先读入的数后加权，因此用栈存储。
（6）迷宫求解
（7）深度优先搜索图
（8）前序遍历二叉树

13.队列的应用
（1）层次遍历：先被遍历的结点，他的孩子也会先被遍历到，将遍历视为入队，将遍历其孩子结点视为出队的话，就是先进先出，因此用队列存储。
（2）图的广度优先遍历：先被遍历的结点，与他邻接的顶点也会先被遍历到，如果将遍历视为入队，将遍历其邻接顶点视为出队的话，就是先进先出，因此用队列存储。
（3）打印机缓冲区（主机和外部设备速度不匹配）：先进入缓冲区排队的先打印
（4）CPU资源竞争中的先来先服务策略

14.介绍一下字符串匹配算法：朴素的匹配算法和KMP算法。（如何实现要会用语言描述）★★★
(1)子串的定位操作称为串的模式匹配，求的是子串（模式串）在主串中的位置。
(2)朴素模式匹配算法：这个方法也称为暴力匹配。就是从源字符串开始搜索，若出现不能匹配，则从原搜索位置+1进行搜索。将主串中所有与给定子串长度相同的子串依次与模式串进行对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止。主串长度：n，模式串长度m，最坏情况下共需对比n-m+1个子串，每个子串对比m个字符，时间复杂度为O(n*m)，很高。
(3)KMP算法：
KMP算法的思想是利用匹配失败后的信息，尽量减少子串与主串的匹配次数以达到快速匹配的目的。
算法实现的关键是求出next数组，next[j]表示：在子串的第j个字符与主串发生失配时，则跳到子串指针应该移动到的位置。
求next数组的方法：在不匹配的位置前，画一个分界线，模式串一步步右移，直到分界线之前能匹配或者模式串完全跨过分界线为止。此时子串指针j指向哪儿，next数组的值就是多少。
匹配方法：匹配过程产生失配时，主串指针i不变，子串指针j退回到next[j]的位置并重新进行比较。
时间复杂度：求next数组O（m），模式匹配O（n),O(m+n)，主要优点是主串不回溯。

15.树的特点与基本术语
(1)树的根结点没有前驱，其他结点都只有一个前驱
(2)树中的所有结点都只有0个或多个后继

(1)祖先：根到结点K的路径上的任意结点都是结点K的祖先
(2)结点的度：一个结点的孩子个数
(3)树的度：数中所有结点的最大度数

16.平衡二叉树、二叉排序树、完全二叉树、二叉搜索树的区别及如何构造★★★
每个结点至多有两棵子树，并且子树有左右之分不能任意颠倒。
(1)满二叉树：除了叶子结点外，其余节点度全为2
(2)完全二叉树：完全二叉树中除了最后一层外，其余每层都含有最多结点数；叶子结点只可能在层次最大的两层上出现。
(3)二叉树排序：左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于右子树的关键字，左子树、右子树又各是一棵二叉排序树。
(4)平衡二叉树：树上任一结点左子树和右子树深度之差不超过1.

(1)二叉树的顺序存储：用一组地址连续的存储单元依次从上到下、从左到右存储完全二叉树上的结点元素，即将完全二叉树上的标号为i的结点存储在数组下标为i-1的存储单元中。对于一般二叉树，为了让数组下标反映二叉树中结点的逻辑关系，只能添加一些空结点，让每个结点与完全二叉树上的结点相对照，但会造成存储空间的浪费。
(2)二叉树的链式存储：用链表结点存储二叉树的每个结点，二叉链表包括数据域、左指针域、右指针域，分别指向其左子树和右子树的根节点。

17.如何由遍历序列构造一颗二叉树？/已知先序序列和后序序列能否重现二叉树？（笔试经常考）★★★
不能，没有中序遍历序列的情况下是无法确定一颗二叉树的
18.二叉树的遍历
先序遍历：访问根节点----先序遍历左子树----先序遍历右子树
中序遍历：中序遍历左子树----访问根节点----中序遍历右子树
后序遍历：后序遍历左子树----后序遍历右子树----访问根节点
层次遍历：借助队列，先将二叉树的根节点入队，然后出队，访问出队结点，若他有左子树则将左子树的根节点入队，若他有右子树则将右子树的根节点入队。然后再出队，访问出队结点。。。。直至队列为空

19.线索二叉树
在含有n个结点的二叉树中会有n+1个空指针，可以利用这些指针存放当前结点的前驱和后继指针，引入线索二叉树可以加快查找结点前驱和后继的速度。
要增加两个标志域标识指针域是指向左（右）孩子的还是指向前驱（后继）的。

20.树的存储结构
(1)双亲表示法：采用一组连续的存储空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。优点：可以很快找到每个结点的双亲结点。缺点：求结点的孩子时要遍历整个结构。
（2）孩子表示法：将每个结点的孩子结点都用单链表链接起来形成一个线性结构。优点：寻找子女方便，寻找双亲则需要遍历n个结点的孩子链表。
（3）孩子兄弟表示法：以二叉链表作为存储结构。每个结点包括三部分内容：结点值、指向第一个孩子结点的指针、指向下一个兄弟结点的指针。“左孩子右兄弟”优点：方便实现树转换为二叉树的操作，易于查找孩子。缺点：找双亲结点比较麻烦。

21.树、森林、二叉树的转换
（1）树–>二叉树：每个结点左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟。
（2）森林–>二叉树：将森林中的每棵树都转换为二叉树，将第二棵二叉树作为第一棵的右子树，将第三棵二叉树作为第二棵二叉树的右兄弟，以此类推，直至只剩下唯一一棵二叉树。
（3）二叉树–>森林：将根节点右链断开形成两棵二叉树，以此类推直至所有二叉树根节点都不存在右子树，最后将每棵二叉树都转换为树，得到森林。

22.树与二叉树的应用：哈夫曼树、并查集
（1）哈夫曼树是带权路径长度最小的二叉树
（2）构造方法：首先将这n个结点构成森林，每次在森林中找到两棵权值最小的树作为新结点的左右子树，并将新结点的权值设为左右子树权值之和。在森林中删除选出的两棵树，并将新得到的树加入森林。重复上述步骤，直至森林中仅剩一棵树，就是哈夫曼树。
（3）哈夫曼树的用途：哈夫曼编码。将每个字符当作一个独立的结点，其权值为他出现的频度，构造出哈夫曼树。将转向左孩子的边标记为0，转向右孩子的边标记为1，依次读出每个结点路径的标记，即可得到字符的哈夫曼编码。
好处：出现频率高的字符被赋予了更高的权值而在哈夫曼树中处于上层，得到更短的编码，这样可以缩短总体的编码长度，降低传输难度。在构造哈夫曼树的过程中，所有字符结点均作为哈夫曼树的叶子节点，一个叶子节点不会成为另一个叶子结点的祖先，因此不会存在一个编码是另一个编码的前缀的现象，不会造成解码上的错误。
（4）并查集：每一个集合以森林中的一棵树表示，集合的并操作就转化成了合并两棵树（只需要改变第二棵树根节点的指向），集合的查操作就转化成了判断两个结点是否在同一棵树中。

23.图的基本概念
(1)图是由顶点集和边集构成，边集可为空，顶点集不可为空
(2)完全图：在全图的任意两个顶点间都存在边
(3)子图：设有两个图，其中一个图的顶点集和边集分别是另一个图顶点集和边集的子集
(4)连通：在无向图中，若两个顶点间有路径，则称两个顶点连通。
连通图：图中任意两个顶点连通
连通分量：无向图中的极大连通子图
(5)强连通：在有向图中，如果有一对顶点v和w，从v到w和从w到v都有路径，则称这两个顶点是强连通的
强连通图：每对顶点都是强联通的
强连通分量：极大强连通子图
(6)生成树：包含图中全部顶点的极小连通子图。

24.邻接表和邻接矩阵（如何存储大数据）★
(1)邻接矩阵法（适用于存储稠密图）：用一个一维数组存储图中顶点信息，用一个二维数组存储图中边的信息（即各顶点间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。空间复杂度O(n2),n为图中顶点个数。
(2)邻接表法（适用于存储稀疏图）：图中顶点用一个一维数组存储，存储顶点数据和边表头指针。为每个顶点建立一个单链表，存储依附于此顶点的边，这个单链表就成为边表（对于有向图来说叫出边表）空间复杂度：无向图（每条边存储了两次）：O（V+2E） 有向图O（V+E）

25.介绍一下深度优先搜索和广度优先搜索是如何实现的？★★★
(1)广度优先搜索（非递归）：类似于二叉树的层序遍历算法，是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先遍历那样有往回退的情况。基本思想：先访问起始顶点v，再由v出发，依次访问v未被访问过的邻接顶点w1、w2…，然后依次访问w1、w2…的未被访问过的顶点，重复这个过程，直至图中所有顶点都被访问过为止。
实现：借助一个辅助队列，先把初始顶点入队，然后每访问一个顶点，就要把此顶点出队，然后把顶点未访问过的邻接顶点依次入队，直至队空。
时间复杂度=访问顶点的时间+找邻接顶点的时间，即访问边的时间，采用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O（V2）

(2)深度优先搜索（递归）：深度优先搜索类似于树的先序遍历，他的策略是尽可能深的搜索一个图。
基本思想是：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接但未被访问的顶点w1，再访问与W1邻接但未被访问的顶点w2…重复上述过程，当不能再向下访问时，依次退回到最近被访问的结点，若他还有顶点未被访问过，则从该点开始继续上述的搜索过程，直至图中所有顶点都被访问过为止。
实现：递归实现
时间复杂度=访问顶点的时间+找邻接顶点的时间，即访问边的时间，采用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O（V2）

26.最小生成树和最短路径用什么算法来实现？（迪杰斯特拉、弗洛依德、普利姆、克鲁斯卡尔）算法的基本思想是什么？算法的时间复杂度？如何进行优化？（必考）★★★★★★★
一．最小生成树
生成树：包含图中全部顶点的极小连通子图
（1）Prim(普里姆)：归并顶点
思路：从某一顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
实现方法：两个数组，一个用来存储各顶点加入生成树的最小代价，一个用来存储各顶点是否已经加入了最小生成树。每次归并一个新顶点前，要遍历这两个数组找到还未加入树且权值最小的顶点；归并一个新顶点后要更新这两个数组。
时间复杂度：此算法是双层循环，外层循环控制次数，一共要归并n个顶点，因此要循环n-1次，内层并列两个循环，每个循环负责遍历一个数组，其时间复杂度为o（n），因此此算法的时间复杂度为O（n2），时间复杂度只与顶点有关，与边无关，适用于稠密图。

（2）Kruskal（克鲁斯卡尔）：归并边
思路：每次选择一条权值最小的边，且这条边所连的2个顶点间还未存在路径，我们使这条边两头连通，重复上述操作直至所有结点都连通。
实现方法：将图中边按照权值从小到大排列，然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路的话，则将该边并入当前生成树。直到所有的边都检测完为止。
时间复杂度：用堆来存放边的集合O（logE），用并查集来判断2顶点是否连通（是否属于同一个集合），O(E logE)
时间复杂度只与边有关，适合边稀疏顶点多的图

二、最短路径
（1）广度优先遍历（解决无权图的单源最短路径问题）
实现方法：需要借助一个数组和一个辅助队列。先把初始顶点入队，然后每访问一个顶点v，就要把v出队，然后把v未访问过的邻接顶点w1、w2…依次入队，并把他们的最短路径长度改为v的最短路径长度+1，重复上述操作直至队空。
时间复杂度=访问顶点的时间+找邻接顶点的时间，即访问边的时间，采用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O（V2）
(2)Dijkstra(迪杰斯特拉)(带权图/无权图的最短路径)
思路：设置一个集合s记录已经求得最短路径的顶点，初始时把源点加入此集合，集合每并入一个新顶点，都要修改源点到未求得最短路径的顶点的最短路径长度，重复上述过程使得所有顶点都加入集合。（与prim相似）（贪心算法）
时间复杂度：算法的核心部分在于一个双重循环，外层循环控制算法进行的轮数，每次循环归并一个顶点且共有n个顶点，所以算法需要进行n轮。双重循环的内循环又是两个并列的单重for循环组成(找距离最小顶点和更新距离),时间复杂度为O(n2) ，其中n为图中的顶点数。

（3）Floyd(弗洛伊德)
思路：首先初始化一个方阵，如果两个顶点间有边，就用边的权值作为最短路径存入方阵。然后逐步尝试在原路径中加入顶点k作为中间顶点。若路径变短，则替代源路径并形成新的方阵。
时间复杂度：算法的核心为一个三重循环，外层循环用来控制迭代次数，每考虑将一个顶点作为中转点就会迭代一次，因此外层循环要循环n-1次。内层的两层循环用来遍历矩阵，更新最短路径长度，所以时间复杂度为O(n3)， 其中n是图中的顶点数。

27.拓扑排序
AOV网是顶点表示活动的网络，边<Vi，Vj>表示活动i必须先于活动j进行。
对AOV网进行拓扑排序的步骤：从AOV网中选择一个没有前驱的顶点并输出，然后从网中删除该顶点和所有以它为起点的有向边，重复上述步骤直到AOV网为空或者不存在无前驱的顶点为止。
时间复杂度：由于删除每个顶点的同时还要删除以他为起点的边，因此每个顶点和每条边都会被遍历一次。采用邻接表存储方式：O(V+E)，采用邻接矩阵存储方式：O（V2）

28.关键路径
AOE网：顶点表示事件，边表示活动，边上的权值表示活动开销
在AOE网中，有些活动是可以并行的，从源点到汇点的路径可能有很多条，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。。完成整个工程的最短时间就是关键路径的长度。
29.查找算法的评价指标：平均查找长度（ASL）
所有查找过程中进行关键字的比较次数的平均值

30.顺序查找（线性查找）
基本思想：从线性表的一端或者链表的表头开始，逐个检查关键字是否满足给定条件。若找到，则查找成功。若已经查找到线性表的另一端或者链表的表尾，还没有找到，则查找失败。
优化思路1：若表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回失败信息，降低查找失败的平均查找长度。
优化思路2：若每个元素被查的概率不等，则将被查概率大的放在靠前的位置。

31.折半查找（二分查找）：仅适用于有序的顺序表
每次确定中间元素后，都需要通过数组下标拿到它的值，因此需要随机存取的特性，只能使用线性表。
基本思想：在有序表中，取中间元素作为比较对象，如果要查找的值和中间元素的关键字相等，则查找成功；若小于中间元素的关键字，则在中间元素的左半区继续查找；若大于中间元素的关键字，则在中间元素的右半区继续查找。重复上述过程，直到查找成功。
实现方法：初始化一个数组A存放有序表中元素，初始化三个伪指针low，high，mid，分别表示查找区域的最左元素下标，查找区域的最右元素下标，以及当前比较元素下标。如果A[mid]>查找值key，则让high=mid-1，查找左半区；如果A[mid]<key，则让low=mid+1，查找右半区。直至A[mid]=key或者low>high为止。
时间复杂度：折半查找的查找过程可以用一棵平衡二叉树表示，根据元素个数可以计算出树的高度为log2(n+1)，每次查找的最多查找次数等于树的高度，因此时间复杂度为O（log2 n）(以二为底n的对数)

32.分块查找
基本思想：将查找表分为若干子块，块内元素无序，块间有序，即第一个块中的最大关键字小于第二个块中所有记录的关键字，以此类推。再建立一个索引表索引，表中的每个元素含有各块的最大关键字和各块第一个元素的地址，索引表按关键字有序排列。
查找过程分为两步，第一步是在索引表中确定待查记录所在的块，可以顺序或折半查找索引表；第二步是在块内顺序查找。

33.二叉排序树（BST）
定义：左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于右子树的关键字，左子树、右子树又各是一棵二叉排序树。
查找：先将给定值与根节点的关键字比较，如果相等则查找成功，如果小于根节点关键字，则在左子树上查找，如果大于根节点关键字则在右子树上查找，这是一个递归的过程。
构造：从一棵空树出发，依次输入元素，将他们插入二叉排序树中的合适位置，使其符合二叉排序树定义。
删除：如果删除节点是叶节点，则直接删除；如果是非叶节点且只有一棵子树，则让这棵子树成为被删除结点父节点的子树；若是非叶节点且有左右两棵子树，则用被删除节点的直接前驱或者直接后继（中序遍历）替代。
平均查找长度：二叉排序树的平均查找长度主要取决于树的高度。最好情况：二叉排序树的平衡的（左右子树高度之差不超过1），O（log2 n）；最坏情况：二叉排序树是一个只有左（右）孩子的单支树，O（n）

34.平衡二叉树（AVL）
引入目的：为避免树的高度增长过快，降低二叉排序树的性能。
定义：任意节点左右子树高度之差的绝对值不超过1的树。
结点的平衡因子：结点左子树和右子树的高度差
插入：每当在二叉排序树中插入（删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。如果导致了不平衡，则先找到插入路径上离插入节点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树（最小平衡子树），在保持二叉排序树特性的前提下，调整各节点的位置关系，使之重新达到平衡。
设最小平衡子树的根节点为A
如果由于在结点A的左孩子的左子树上插入新节点而导致失去平衡，则通过一次右单旋转调整。
如果由于在结点A的右孩子的右子树上插入新节点而导致失去平衡，则通过一次左单旋转调整。
如果由于在结点A的左孩子的右子树上插入新结点而导致失去平衡，则先通过一次左旋再通过一次右旋调整。
如果由于在结点A的右孩子的左子树上插入新结点而导致失去平衡，则先通过一次右旋再通过一次左旋调整。
平均查找长度：含有n个节点的平衡二叉树的最大深度为O（log2 n），因此平衡二叉树的平均查找长度为O（log2 n）

35.红黑树（RBT）原理是什么？建立过程？★★★
引入目的：为了保持AVL树的平衡性，在进行插入和删除操作后，需要频繁地调整全数的整体拓扑结构，代价较大。因此在AVL树的平衡标准上进一步放宽条件，形成红黑树。对于红黑树来说，插入删除操作很多时候不会破坏其红黑特性，无需频繁调整树的形态，即使要调整也可以在常数级时间内完成。
定义：红黑树是满足如下红黑性质的二叉排序树：
（1）每个结点是红色或者黑色的
（2）根、叶节点是黑色的
（3）不存在两个相邻的红结点
（4）对于每个结点，从该结点到任一叶结点的简单路径上，所含黑结点数量相同。
插入：先进行查找操作，确定插入位置并插入。如果新结点是根，则染为黑色，若新节点非根，则染为红色。如果插入后不满足红黑树定义，则需要调整使其重新满足红黑树定义。

36.B树（多路平衡查找树）
B树的阶：B树中所有结点的孩子个数最大值
定义：B树是满足如下特性的m叉树：
（1）树中每个结点至多有m棵子树，即至多有m-1个关键字
（2）若根节点不是终端结点，则至少有两棵子树。
（3）除根节点外的所有非叶结点至少有m/2棵子树
（4）所有叶结点都出现在同一层次上，并且不携带信息
查找：（1）在B树里找结点（2）在结点里找关键字
插入：（1）首先进行查找操作，找出插入该关键字的最低层中的某个非叶节点。
（2）进行插入操作，如果插入后被插入节点的关键字个数超过m-1，则需要对节点进行分裂。分裂方法是：从中间位置将关键字一分为二，左部分放在原结点中，右部分放在新结点中，中间位置的关键字插入原节点的父结点中。若此时导致父节点关键字个数也超过上限，则继续分裂。
删除：如果被删除的关键字k不在终端结点中时，可以用k的前驱或者后继来替代k。如果被删除的关键字在终端结点，则有2种情况：如果被删除关键字所在节点删除前的关键字个数>=m/2，则直接删除。反之需要重新调整结点，向兄弟结点借一个关键字或者与兄弟节点和双亲结点中的关键字进行合并。
用作数据库索引

37.B数和B+树的区别★★★
（1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树。而在B树中，具有n个关键字的结点含有n+1棵子树。
（2）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中。而在B树中，叶结点包含的关键字与其他结点包含的关键字是不重复的。
（3）在B+树中，非叶节点仅起索引作用，叶结点包含关键字对应记录的存储地址.而B树的结点中都包含关键字对应记录的存储地址。

38.哈希表的概念、构造方法、哈希有几种类型？哈希冲突的解决办法？★★★★
定义：根据关键字而直接进行访问的数据结构
构造方法：
（1）直接定址法：直接取某个线性函数值作为散列地址（不会产生冲突，适合关键字分布基本连续的情况，若不连续则空位较多，会造成存储空间浪费）
（2）除留取余法：取一个最接近散列表表长的质数p，散列函数为key%p
（3）数字分析法：选取数码分布较为均匀的若干位作为散列地址
（4）平方取中法：取平方值的中间几位作为散列地址。
处理冲突的方法：
（1）开放定址法：可存放新表项的空闲地址既向他的同义词表项开放，又向他的非同义词表项开放。
A、线性探测法：冲突发生时，顺序查看表中下一个单元，直到找出一个
空闲单元，缺点：大量元素在相邻的散列地址上堆积起来，降低了查找效率。
B、平方探测法：增量序列为02，12，-12，22…以此类推。优点：避免出现堆积问题，缺点：不能探测到散列表上的所有单元。
C、双散列法：需要使用两个散列函数，当通过第一个散列函数得到的地址发生冲突时，则利用第二个散列函数计算该关键字的地址增量。
D、伪随机序列法：增量为随机数。
（2）拉链法：把所有同义词存储在一个链表中，将散列地址为i的同义词链表的头指针存放在散列表的第i个单元中。
查找效率：取决于散列函数、处理冲突的方法和装填因子。装填因子定义为一个表的装满程度：表中记录数/散列表长度。

39.查找算法时间复杂度比较
查找算法 时间复杂度
顺序查找（线性查找） O（n）
折半查找（二分查找） O（log2 n）
分块查找
二叉排序树（BST） O（log2 n）----O(n)
平衡二叉树（AVL） O（log2 n）

线性结构 顺序查找
折半查找
分块查找
树形结构 二叉排序树
二叉平衡树
红黑树
B树、B＋树
散列结构 散列表

40.排序的定义
算法的稳定性：两个关键字相同的元素排序前后相对顺序不变
排序算法分类：
（1）内部排序：排序期间元素全部存放在内存中（关注如何降低时间复杂度）
（2）外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序过程中不断在内外存之间移动元素。（关注如何使读写磁盘次数减少）

41.直接插入排序
思路：每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。
空间复杂度：使用常数个辅助单元，空间复杂度为O（1）
时间复杂度：最好：表中元素有序，每插入一个元素只需要比较一次而不需要移动 O（n）；最坏：表中元素逆序，O（n2）

42.折半插入排序
思路：每次将一个待排序的记录通过折半查找，找出其在前面已经排好序的子序列中的待插入位置，然后统一的移动待插入位置之后的所有元素，将其插入。
实现：初始化一个数组A存放已经排好序的子序列，初始化三个伪指针low，high，mid，分别表示查找区域的最左元素下标，查找区域的最右元素下标，以及当前比较元素下标。如果A[mid]>查找值key，则让high=mid-1，查找左半区；如果A[mid]<key，则让low=mid+1，查找右半区。直至low>high时停止查找，将low指针及之后的元素全部右移一位，并将元素插入到low指针所指位置。
时间复杂度：仅减少了比较元素的次数，约为O（nlog2 n），元素移动次数未改变O(n2)，因此时间复杂度还是O（n2）

43.希尔排序（缩小增量排序）
只能用于顺序存储：按照给定增量找子表时需要随机存取特性
直接插入排序的时间复杂度为O（n2），如果待排序序列是正序，其时间复杂度可提高至O（n），由此可见直接插入排序适用于基本有序和数据量不大的排序表，希尔排序通过以上两点对直接插入排序进行了改进。
思路：把相隔某个增量d的记录组成一个子表，对各子表分别进行直接插入排序，缩小增量d重复上述过程，直至d为1为止。
空间复杂度：仅使用了常数个辅助单元，空间复杂度为O（1）
时间复杂度：约为O（n1.3），最坏情况下为O（n）
稳定性：不稳定，相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。

44.冒泡排序
思路：从后往前两两比较相邻元素的值，若为逆序则交换他们，直至将最小的元素交换到待排序序列的第一个位置，即为一趟冒泡。下一趟冒泡时，前一趟确定的最小元素不再参与比较。重复进行冒泡直至元素不再发生交换为止。
时间复杂度：最好情况：当初始序列有序时，进行一趟冒泡即可跳出循环，时间复杂度为O（n）。最坏情况：放初始序列为逆序时，要进行n-1趟冒泡，第i趟冒泡要进行n-i次关键词比较，因此时间复杂度为O（n2）
稳定性：稳定，关键字相同时元素不发生交换
空间复杂度：O（1）

45.快速排序（是所有内部排序算法中平均性能最优的排序算法）
思路：在待排序表中取一个元素作为枢轴，通过一趟排序将待排序表分为两部分，左子序列中所有元素均小于枢轴，右子序列中所有元素均大于枢轴，然后在左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
每次由一个枢轴将待排序序列分成左右两部分，这个过程类似于构造一棵二叉树，最小高度为log2 n,最大高度为n
空间复杂度：快速排序是递归的，需要一个递归工作栈实现，其容量与递归调用的最大深度一致。最好情况下O（log2 n），最坏情况下O（n），平均O（log2 n）
时间复杂度：最好：每次选择的枢轴元素都能将序列化分成均匀的两部分，O（nlog2 n）；最坏：初始排序表基本有序或者逆序时，O（n2）。
稳定性：不稳定

46.简单选择排序
思路：每一趟（比如第i趟）在后面n-i+1个待排序元素中选取关键字最小的元素，与第i个元素进行交换，每一趟排序可以确定一个元素的最终位置，经过i-1趟排序就可以让整个排序表有序。
空间复杂度：O（1）
时间复杂度：O（n2）
稳定性：不稳定

47.堆、大顶堆、小顶堆实现及应用 ★★
堆是一种特殊的完全二叉树
大顶堆：每个父节点的值都大于孩子节点
小顶堆：每个父节点的值都小于小子节点
堆排序思路（以从大到小排序为例）：首先将元素构成初始大根堆，输出堆顶元素，并把堆底元素送入堆顶。此时根节点已经不满足大根堆的性质，堆被破坏，将堆顶元素向下调整使其继续满足大根堆的性质，再输出栈顶元素。重复上述步骤，直至堆中仅剩一个元素为止。
插入：先将新结点放在堆的末端，再对新结点向上调整。
删除：被删除元素用堆底元素替代，然后将该元素不断向下调整。
空间复杂度：O（1）
时间复杂度：建堆时间为O（n)，之后进行n-1次向下调整，每次调整时间复杂度为O（h）,时间复杂度为O（nlog2n）
稳定性：不稳定

48.归并排序
归并的含义是将两个或两个以上的有序表组合成了一个新的有序表。
二路归并排序：将待排序表中的n个记录视为n个有序子表，每个子表长度为1。然后两两归并，得到n/2个长度为2的有序表，继续两两归并，直至归并成一个长度为n的有序表为止。
实现：初始化两个数组A和B，将两个要进行归并操作的有序表复制到数组B的相邻位置，每次从B中的两个有序表分别取出一个关键字进行比较，将大的存入A，重复上述操作直至B空。
空间复杂度：O（n）
时间复杂度：O（nlog2 n）
稳定性：稳定

49.基数排序
不基于比较和移动，而是基于关键字各位的大小进行排序。
思路：设置r个空队列，按照各个关键字位权重递增的次序，对d个关键字位分别进行分配和收集操作。分配：顺序扫描各个元素，根据当前处理的关键字位将元素插入相应队列。收集：把各个队列中的结点依次出队并连接。
空间复杂度：O（r），r是队列数
时间复杂度：基数排序需要进行d趟分配和收集（d是关键字位数），一趟分配要O（n），一趟收集要O（r），时间复杂度为O（d(n+r)）
稳定性：稳定

50.插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序（必考）、堆排序、基数排序等排序算法的基本思想是什么？时间复杂度？是否稳定？给一个例子，问冒泡和快速排序在最坏的情况下比较几次？（排序必考）★★★★★★

排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性

插入排序 直接插入排序 O（n2） O(n) O(n2) O（1） 稳定
折半插入排序 O（n2） 稳定
希尔排序 O（nlog2 n）—O(n2) O（n1.3） O（n2） O（1） 不稳定
交换排序 冒泡排序 O（n2） O(n) O(n2) 0(1) 稳定
快速排序 O（nlog2 n） O(nlog2 n) O(n2) O(log2 n)–O(n) 不稳定
选择排序 简单选择排序 O（n2） O(n2) O(n2) O(1) 稳定
堆排序 O（nlog2 n） O(nlog2 n) O(nlog2 n) 0(1) 不稳定
归并排序 O(nlog2 n) O(nlog2 n) O(nlog2 n) O（n） 稳定
基数排序 O（d(n+r)） O? 稳定