数据结构

1.时间复杂度和空间复杂度

时间复杂度是用于评估执行程序所消耗的时间
空间复杂度是用于评估执行程序所占用的内存空间

2.数据结构、逻辑结构、存储结构

数据结构是计算机存储和组织数据的方式
逻辑结构是指元素之间的逻辑关系，与数据的存储结构无关
存储结构是指元素在计算机中的物理存储方式

3.数据结构的4种逻辑结构

集合结构:数据元素之间同属于一种类型
线性结构:数据元素之间存在一对一的关系
树形结构:数据元素之间存在一对多的关系
图状结构:数据元素之间存在多对多的关系

4.线性表的存储结构及其优缺点

顺序存储:顺序存储中的元素顺序存放，可以随机存取，查找和更新数据比较快，插入和删除数据需要移动元素

链式存储:各元素按照链式连接，各个结点的指针域都指向下一个结点的存储位置，不能随机存取，查找和更新数据比较慢，插入和删除数据比较快

索引存储:为元素建立对应的索引表，每个元素对应有一个关键字和存储地址，查询效率高，但是需要额外空间存储索引表

散列存储:根据元素的关键字经过散列函数计算出映射地址，查找速度快，但是会存在冲突和堆积现象

5.数组和链表的区别

数组需要预先从栈中分配固定的长度，不能动态增添数据项，适用于快速查找和修改，较少使用插入和删除
链表可以从堆中动态地分配空间，可以适应动态增添数据项，适用于经常插入和删除

6.怎么确定单链表是一个环

哈希标记法，创建一张散列表，每访问一个结点，根据结点的关键字经过哈希函数存储到散列表，如果后续访问到某个结点已经存在在散列表中，则证明重复访问了某个结点，证明有环

快慢指针法，同时创建两个指针从链表的头节点出发，一个指针每次移动一个结点，另一个指针每次移动两个结点，然后比较这两个指针指向的结点是否相同，如果相同，说明链表有环，如果不同则重复这个过程。

7.栈、队列

栈是一种操作受限的线性表，只允许队尾入队，在队尾出队，最大的特点是先进后出

顺序队列队列是一种操作受限的线性表，只允许队尾入队，在队头出队，最大的特点是先进先出

循环队列的实现:将数组看成一个环，让rear和front指针沿着环走
为什么要留一个位置:为了区分队空和队满
队空判断条件: front == rear
队满判断条件:（front+1）%n == rear
循环队列的用处:避免了顺序队列尾指针的假溢出

8.树、二叉树、森林

二叉树的度不一定为2，且可以为空，
度为2代表这颗树的某个结点存在2颗子树

树转二叉树，将树转化为孩子兄弟表示法下的二叉树
树转森林，先将树转为二叉树，将第二颗二叉树作为第一颗二叉树的右子树，同理再将第三课二叉树作为第二课二叉树的右子树，直至森林变成一颗树

9.树的遍历方式

前序遍历、中序遍历、后序遍历、层次遍历。

10.树的存储方式

双亲表示法:某个结点增加对父结点的指针域
孩子表示法:邻接表存储某个结点的所有孩子
孩子兄弟表示法:左孩子右兄弟

可以用顺序存储结构、链式存储结构实现

11.简述二叉排序树

二叉排序树是一颗可以为空的二叉树，它的根节点的权值均大于等于其左子树任意结点的权值，并且小于等于右子树任意结点的权值，并且其左右子树也是二叉排序树

12.堆

完全二叉树
除最后一层外，每一层的结点数都达到最大值，最后一层的结点，连续集中在最左边

堆是一颗完全二叉树，任何一个分支节点都不大于（或不小于）其左右结点的值，分为大顶堆、小顶堆

13.线索二叉树

对于n个结点的二叉树，在二叉树的链式存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树

14.哈夫曼树

给定n个权值作为n个叶子节点，构造一棵带权路径长度最小的二叉树叫做最优二叉树，即哈夫曼树

结点的带权路径长度:树的根结点到该结点的路径长度和该结点权重的乘积

树的带权路径长度WPL:哈夫曼树中，所有叶子结点的带权路径长度之和

构造方法:每次从森林中取出两个根节点权值最小的子树合并，分别作为新树的左右子树，新树的根节点的权值为左右子树根节点权值之和。重复n-1次这个操作，最后森林中仅剩的一棵树即是哈夫曼树。

应用:哈夫曼编码，减少编码长度

15.平衡二叉树AVL

AVL是一种特殊的二叉排序树，左右子树都是平衡二叉树，左右子树的高度差的绝对值不超过1

平衡因子:左子树高度减去右子树高度的差

调整方法:找到离插入结点最近，且平衡因子大于1的结点，并以该结点作为子树的根节点进行四种调节方式，有LL,LR,RL,RR。

16.B+树和B树的区别

b树n个关键字的结点对应n+1个子树，b+树n个关键字的结点对应n个子树
度为m的b树的非根结点关键字个数的范围是[m/2]-1到m-1，度为m的b+树的非根结点关键字个数的范围是[m/2]到m
b树所有结点都包含信息，b+树仅叶子节点包含信息，分支节点起到索引作用
b+树的叶子结点通过双链表连接，可以支持顺序查找

17.红黑树

红黑树是一种特殊的二叉查找树，结点可以由黑色和红色标记，适用于删除和插入较多的情况。

性质:
它的根节点和叶子节点都是黑色的，新插入的结点是红色的
它不存在两个相邻的红色结点，所以从根节点到叶节点的最长路径不超过最短路径的2倍（红黑相间和全黑）
对于任意子树的根节点，到达其叶节点的路径上黑结点数量都是相同的
树高不大于2*log2(n+1)

插入:
出现两个红色结点相邻的情况时，需要作调整，对于新插入结点的叔结点
如果是黑的，就做类似于平衡二叉树的旋转，然后更新结点颜色
如果是红的，就更新颜色，并继续递归向上调整

18.最小生成树两种算法优缺点比较

最小生成树:寻找原图中包含n个结点的极小联通子图

prim:基于贪心策略，先选择一个初始点加入点集S，然后从点集S中选出弧尾未被标记且边权最小的点继续加入点集S，重复上述操作，直至图中所有的点都被收录到S中，只跟结点数有关，适用于稠密图
kruskal:基于贪心策略，贪心地从边集中选出一条最短的边，并使用并查集判断加入边是否会形成环，如果会，就跳过这条边，直至最后选出n-1条边，只跟边数有关，适用于稀疏图

19.图的遍历方式

深度优先搜索
首先访问出发点V，然后访问与V邻接的未被访问的点W，直至访问完与V连通的所有结点，若还有结点未被访问，就继续重复上述操作，直至将所有图中所有的点都访问过

广度优先搜索
首先访问出发点V，并将V加入到队列中，然后弹出队列中的结点，依次访问与其邻接的且未被访问的点，并加入队列中，重复上述操作，直至将所顶点都访问过

20.图的存储方式:

邻接矩阵 适合表示稠密图，需要较大的存储空间
邻接表 适合表示稀疏图，能节省存储空间，能够快速找到它的邻边
十字链表 针对有向图
邻接多重表 针对无向图

21.拓扑排序

是有向无环图的一个线性序列，每个顶点仅出现一次，若存在A到B的路径，则A必然出现在B之前
过程:每次从DAG中选一个入度为0的点并输出，从图中删除该顶点和以它为起点的有向边，重复上述操作直至DAG为空或不存在入度为0的点，后者代表存在环
使用了需要存储图，可以用邻接矩阵或邻接表，拓扑排序算法则需要使用到队列

22.两个最短路径算法有什么不同，用于什么情况

迪杰斯特拉算法
是求解单源最短路的贪心算法，它适用于稀疏图并且不存在负权的图中，主要的过程是:
设有2个点集S和T分别存放标记过的和剩余的结点。默认将源点放入S中，再不断地从T中选取离源点距离最近的点加入S中，同时还要更新这个点相邻的结点到源点的距离，直至T集合为空
时间复杂度是O(v^2)，可以使用堆优化变为O(ElogE)

弗洛伊德算法
是求解多源最短路的动态规划算法，它适用于稠密图，主要的过程是:
枚举k，i，j分别代表中转点，起始点还有终点，对于当前的i到j的距离，我们的选择可以有经过中转点k或者不选择经过，那么选取其中一个距离更短的作为解即可，所以可出状态转移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])，这原本应该是一个三维的dp方程，由k-1层转移到k层，但是这里使用了滚动数组优化掉了
时间复杂度是O(n^3)

23.解释下关键路径和关键活动，什么情况下才有关键路径

有向图的边表示活动，结点表示事件的网称为AOE网
关键路径就是从源点到汇点的所有最大路径长度的路径称为关键路径，关键活动就是关键路径上的活动，

24.哈希函数的特点以及如何处理冲突

哈希表的特点:访问速度快，无序，可能会产生冲突
哈希函数的方法:直接定址法、平方取中法、除留余数法、数学分析法
哈希表会不会发生冲突:没有完美的散列函数，总会发生冲突
解除冲突的方法:开放地址法（线性探查法，平方探查法），链地址法
散列表的建立方法:将关键字根据哈希函数得到映射地址后存储到散列表中
散列表适合存储什么样的数据:需要快速查找且关键字很少重复的数据
影响散列表表平均查找长度的因素:装填因子（散列表数据数/散列表长度）哈希函数，解决冲突的方法

25.排序算法有哪些，及其时间复杂度

插入排序，快速排序，冒泡排序，选择排序，堆排序，希尔排序，归并排序，基数排序

排序最优和最差相同的排序算法
选择排序，堆排序，归并排序，基数排序

最差和平均的算法复杂度一样的排序算法
插入排序，冒泡排序，堆排序，归并排序，选择排序，基数排序

最好最坏平均都一样的排序算法
选择排序，堆排序，归并排序，基数排序

26.汉诺塔

汉诺塔问题可以使用递归的方式解决，可以将在A塔的n个盘子，看成移动n-1个盘子到B塔和移动最后一个盘子到C塔的问题，接着就是解决n-1盘子如何移动的子问题，这本质上跟主问题是一致的，只不过目标塔由C塔变为了B塔，而辅助塔由B塔变为了C塔，所以整个问题规模降到了n-1，因此可以一直继续递归分解子问题，最终解决整个问题

27.简述背包问题

背包是一个动态规划问题，问题的描述是给定一组具有重量和价值的物品，在限定重量的背包内如何放下总价值最大的物品。

可以用dp[i][j]代表前i件物品放入j容量的背包中的最大容量，对于这种情况，总共可以有两种选择，一、不放第i件物品，问题就转化为i-1件物品放入j容量的背包的情况即dp[i-1][j]，二、放第i件物品，问题就转化为i-1件物品放入j-第i件物品重量的问题，所以第i层的状态可以由i-1层状态转移过来，所以可以从初试层一直递推下去得到背包问题的最优结果

28.KMP的主要思想

建立一个next数组用于存储失配结点的跳转位置，实际上是存储了模式串的最大相同前后缀长度，当在某一个位置失配时，可以将模式串的前缀滑动到后缀相同的位置，从而主串匹配的位置i无需回溯，并继续从该位置继续比较