大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

说明：这些是自己整理回答的答案 可以借鉴 也可能存在错误 欢迎指正

逻辑结构与物理结构的区别

逻辑结构 ：是指数据对象中数据元素之间的相互关系

逻辑结构分类：

集合——各个元素之间是“平等”的，类似于数学里面的集合
线性结构——数据结构中的数据元素是一对一关系的
树性结构——数据结构中的数据元素之间存在一对多的层次关系
图形结构——数据结构中的数据元素之间存在多对多的关系

---

物理结构 ：是指数据的逻辑结构在计算机中的存储形式

物理结构的分类：

1. 顺序存储结构
——把数据元素存放在地址连续的存储单元中，其数据间的逻辑关系和物理关系是一致的。

2. 链式存储结构
——把数据元素存放在任意的存储单元中，这组存储单元可以是连续的，也可以是不连续的。通过指针来找到下一个数据元素的地址。

3.索引存储结构
——B+ 树

4.散列存储结构

---

算法

算法的五大特征

 - 有穷性——有限的步骤
 - 确定性——不可二义性
 - 可行性——每一步都是通过执行有限次数完成的
 - 输入——零个或多个输入
 - 输出——至少有一个或多个输出

好的算法

 - 正确性
 - 可读性
 - 健壮性 ——当输入数据不合法时，算法也能做出相应的反应
 - 效率与低存储需求

时间复杂度： 算法的执行时间与原操的执行次数之和成正比

空间复杂度 ： 如果输入数据所占空间只取决于问题本身，而与算法无关，只需要分析除了输入和程序之外的辅助变量所占用的空间即可。

常见的数据结构

数据结构 ：是指相互之间存在一种或者多种特定关系的数据元素的集合

常见数据结构

数组	——————	一维数组、二维数组
链表	——————	单链表、循环链表
栈		——————	先进后出、递归、后缀表达式、函数调用
队列	——————	先进先出、树的层次遍历、图的广度遍历
树		——————	二叉树、森林、平衡二叉树、线索二叉树、遍历
图		——————	有向图、无向图、最小二叉树、遍历、最短路径

链表存储结构和顺序存储结构的区别

顺序存储结构：是以数据元素的相对物理位置来表示数据元素之间的逻辑关系的

链表存储结构 ：以指针指向来表示数据元素之间的逻辑关系。

顺序存储结构	链表存储结构
读取方便 O(1）	读取不方便 需要遍历 O(n)
插入删除 需要移动大量元素	插入删除方便 只需要改变指针
空间分配 ：一次性	在需要时分配
存储密度 = 1	存储密度 < 1

数组和链表的区别

数组	链表
事先定义长度，不能适应数据动态地增减	动态地进行存储分配，可以适应数据动态地增减
从栈中分配空间	从堆中分配空间
快速访问数据元素，插入删除不方便	查找访问数据不方便，插入删除数据发布

头指针和头结点的区别

头指针	头结点
是链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针	头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前。
是必需的	不是必需的 为了方便操作
具有标识作用	对于插入和删除第一结点，和其他结点操作统一

线性链表

线性链表中一个节点代表一个存储空间，即节点。每一个节点包括两个部分，一个用来存储数据，一个存储下一个元素的地址。

判断整个链表是否有环，如何找到这个环

提问：给定一个单链表，只给出头指针h：
1.如果判断是否存在环？

2.如何知道环的长度？

3.如何找出环的连接点在哪里？

4.带环链表的长度是多少

解法：
1.对于判断一个单链表是否存在环，可以利用追赶的方式，设立两个指针slow、fast，从头指针开始，每次分别前进一步和两步。如果存在环，则两者相遇；如果没有环，fast遇到NULL退出。

2.在slow和fast相遇的地方标记，再次相遇所走过的操作数就是环的长度

3.分别从相遇点和头指针开始走，相遇的那个点就是连接点

4.问题3中连接点距离头指针的长度，加上问题2中求出的环的长度，即为链表的长度。

http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html.

单链表和双链表的区别

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

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

简述KMP算法

KMP算法是在简单模式匹配的基础上对串的模式匹配进行优化。

主要的思路是每趟比较过程中让子串先滑动到一个合适的位置。

当发生不匹配时，不同于简单模式匹配的右移一位，而是移动到适合的位置。

这里所移动的位置依靠与NEXT[]数组，求next[]数组的方法是比较前后缀相同元素。

栈和队列的区别

栈	队列
先进后出	先进先出
允许在表尾进行插入和删除	允许在一段进行插入一段进行删除
插入和删除都在表尾进行	在队尾插入在队头删除
top == -1 为空	front == rear 为空
top++ 进栈	rear = （rear+1）%maxsize进队
top– 出栈	front = （front+1）%maxsize出队

相同点 ：

栈和队列都是线性结构
栈和队列在插入时都是在表尾进行
栈和队列都可以用顺序存储结构和链表存储结构
栈和队列插入和删除操作的时间复杂度和空间复杂度是一样的

不同点 ：

删除元素位置不同，栈在表尾，队在表头
用链表存储时可以实现多栈空间共享，队列不行

两个栈实现队列，两个队列实现栈

两个栈实现队列

栈1 – – – – – – -栈2

入队：把全部元素入栈1，出栈1压入栈2，实现与队列相同的顺序。

出队：在栈2 中以此出队即可。

插入新的元素：不应该在栈2内还有元素时，将栈1中插入的元素入栈，而是等栈2所有元素都出队后，再将栈1 中的元素压入栈2。

树和二叉树的相关概念

提问：二叉树和度为2的树的区别

回答：

二叉树的特点：
1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。
4、二叉树可以是空树、只有一个根结点、根结点只有左子树、根结点只有右子树、根结点左右子树都有。

度为2 的树：树的结点的最大的度为2.

二叉树遍历

先序：

先访问根结点
再先序遍历左子树
最后先序遍历右子树

中序：

从根结点开始，
中序遍历左子树
访问根结点
最后中序遍历右子树

后序遍历

从左到右先叶子结点的方式遍历访问左右子树
最后访问根结点

层次遍历

从根结点的第一层开始访问
从上到下进行遍历，
从左到右访问结点
（利用队列来实现）

树的遍历

先跟遍历：

先访问根结点
从左到右先跟遍历树的每个子树

后跟遍历：

先依次后跟遍历每根子树，
然后再访问根结点

二叉平衡树、二叉排序树

二叉排序树：
是比根结点大的放在右子树，比根结点小的放在左子树

二叉平衡树：
在二叉排序树的基础上，只要保证每个节点左子树和右子树的高度差小于等于1就可以了。
适用于插入删除比较少，但是查找比较多的情况

红黑树

主要性质：

节点是红色或者黑色，没有其他的颜色
根结点是黑色，不能为红。
每个叶节点是黑色，这里的叶子结 节点是指空的叶子结点
不存在两个连续的红色节点，即父节点和子节点不能是连续的红色
从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。

优点：平均查找，添加输出效果都还不错

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm_area_struct（虚拟内存）时就是采用了红黑树来维护内存块的。

图的相关概念

图结构中结点之间的关系是任意的，图中的任意两个结点都可能有关系。

图分为有向图和无向图

有向图的基本算法：拓扑排序、最短路径（Dijkstra算法和Floyd算法）。

无向图的基本算法：最小生成树（prime算法，Kruska算法）、DFS、BFS。

图的存储结构

邻接表：（链式存储结构）由单链表的表头形成的顶点表，和单链表其余结点形成的边表两部分组成；一般顶点表存放顶点信息和指向第一个边结点的指针

邻接矩阵：（顺序存储结构）

有向图的十字链表法

无向图的多重链表法

深度优先遍历与广度优先遍历

深度优先遍历 类似于二叉树的先序遍历

步骤：

（1）访问起始点v

（2）若v的第一个邻接点没有被访问过，则深度遍历该邻接点；

（3）若v的第一个邻接点已经被访问，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止

广度优先算法 类似于层次遍历

步骤：

（1）访问起始点v

（2）依次遍历v的所有未访问过得邻接点

（3）再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止

最小生成树的算法（普利姆算法，克鲁斯卡尔算法）

普利姆算法（Prim）

算法执行过程

将v0到其他顶点的所有边当做候选边
重复以下过程，直到所有的顶点被并入树中
	1.从候选边中挑选出最小的边输出，并将于该边的另一端顶点并入树中
	2.考查所有剩余的顶点，选取与这棵树相接的边最短的边

时间复杂度为O(n2)，适用于稠密图

克鲁斯卡尔算法

思路：
每次找出后候选边中权值最小的边，并入生成树中

算法执行过程

将图中边按照权值从小到大排序，
然后从最小边开始扫描，
并检测当前边是否为候选边，即是否该边并入会构成回路

适用于稀疏图

什么时候最小生成树唯一

所有权值都不相同，或者有相同的边，但是在构造最小生成树的过程中权值相等的边都被并入到最小生成树中的图，其最小生成树是唯一的。

最短路径

Dijkstra算法（迪杰斯特拉）

迪杰斯特拉算法

用于计算图中某一结点到其余顶点的最短路径

思路：

集合s存放图中一找到最短路径的顶点
集合U存放途中剩余顶点

算法步骤：

算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

floyd算法

解决任意两点间的最短路径的一种算法，

可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包

时间复杂度为O(N3)，空间复杂度为O(N2)。

算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

拓扑排序的概念以及实现

AOV网

一种以顶点表示活动，以边表示活动的先后次序且没有回路的有向图

反映出整个工程中各个活动之间的先后关系的有向图。

拓扑算法的核心

过程：

从有向图中选择一个没有前驱（入读为0）的顶点输出
删除1中的顶点，并且删除从该顶点发出的全部边
一直重复

若图中没有环的时候，还可采用深度优先搜索遍历的方法进行拓扑排序

关键路径的相关概念

AOE网——对于活动在边上的我网

AOV和AOE的区别

相同点: 都是无环图

不同点：AOV活动在顶点，边无权值，代表活动之前的先后关系，
AOE活动在边，边有权值，代表活动持续的时间

关键路径的核心算法：

最大路径长度的路径称为关键路径

关键活动：关键路径上的活动为关键路径，关键活动的最早开始时间等于最晚开始时间。由于AOE网中的某些活动是可以同时发生的，所以完成整个工程的时间应该是从始点到终点的最大路径长度，关键路径长度即为工程的最短完成时间。

各种排序的概括与总结

经过一趟排序，能保证一个关键字到达最终位置
冒泡排序、快速排序（交换类）
简单选择、堆排序（选择类）

关键字比较次数和原始序列无关
简单选择、折半排序

排序趟数和原始序列无关
冒泡排序、快速排序（交换类）

将顺序存储更换为链式存储，时间效率低
希尔排序、堆排序

排序最优和最差相同的排序算法
简单选择、归并排序、堆排序

排序算法中那些最坏和平均的时间复杂度是一样的
直接插入、折半插入、冒泡排序、简单选择、堆排序、归并排序

稳定排序算法
直接插入排序，冒泡排序和归并排序。

各种查找方法

查找方法分为静态查找表和动态查找表

静态查找表：顺序查找、折半查找、分块查找

动态查找表：二叉排序树、平衡二叉树

顺序查找：结构简单，顺序结构和链式结构都可以，查找效率低

折半查找：要求查找表为顺序存储结构并且有序

分块查找：先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，从而保存块间是有序的，把各子表中的最大关键词构成一张索引表，表中还包含各子表的起始地址。
特点：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。

二叉排序树：

平衡二叉树：他的左右子树高度差不能大于1，且左右子树也都是平衡二叉树。

快速排序的优化

优化：
1.当整个序列有序时退出算法；
2.当序列长度很小时（根据经验是大概小于 8），应该使用常数更小的算法，比如插入排序等；
3.随机选取分割位置；
4.当分割位置不理想时，考虑是否重新选取分割位置；
5.分割成两个序列时，只对其中一个递归进去，另一个序列仍可以在这一函数内继续划分，可以显著减小栈的大小（尾递归）：
6.将单向扫描改成双向扫描，可以减少划分过程中的交换次数

优化1：当待排序序列的长度分割到一定大小后，使用插入排序
原因：对于很小和部分有序的数组，快排不如插排好。当待排序序列的长度分割到一定大小后，继续分割的效率比插入排序要差，此时可以使用插排而不是快排

优化2：在一次分割结束后，可以把与Key相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割

优化3：优化递归操作
快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化

优点：如果待排序的序列划分极端不平衡，递归的深度将趋近于n，而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。

B树和B+树的区别，以一个m阶数为例

关键词的数量不同：
B+树中具有n个关键字的结点只含有n棵子树。每个结点关键字个数的范围是|m/2| <= n <= m
B树中具有n个关键字的结点含有n+1棵子树。每个结点关键字个数的范围是|m/2| -1<= n <= m-1

存储的位置不同：B+树中数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中。

分支结点的结构不同：B+树的分支结点仅仅存储着关键字信息和儿子的指针，也就是说内部结点仅仅包含着索引信息

查询不同：B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束。

哈希表（概念、构造方法、冲突解决）

概念：根据给定的关键字来计算出关键字的表内地址

建立方法

直接定址法：
H(Key)=a*Key+b
特点：计算简单，且不会产生冲突，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

数字分析法：
适用于关键字位数比较多且标红可能的关键字都是已知的情况

平方取中法：
取关键字平方后的中间几位作为Hash地址
适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数

除留余数法：

冲突解决方法

1.开放定址法
线性探查法：依次探查下一个地址，直到有空位置出现为止（容易产生堆积）
平方探查法：可以减少堆积问题，但是不能探查到hash上的所有单元，可探查到一半单元。

2.链地址法
把所有的同义词用单链表连接起来

3.公共溢出区

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

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

递归算法

优点：代码简洁、清晰，并且容易验证正确性。

缺点：它的运行需要较多次数的函数调用，如果调用层数比较深，需要增加额外的堆栈处理（还有可能出现堆栈溢出的情况），比如参数传递需要压栈等操作，会对执行效率有一定影响。
但是，对于某些问题，如果不使用递归，那将是极端难看的代码。在编译器优化后，对于多次调用的函数处理会有非常好的效率优化，效率未必低于循环。

循环算法

优点：速度快，结构简单。

缺点：并不能解决所有的问题。有的问题适合使用递归而不是循环。如果使用循环并不困难的话，最好使用循环。

贪心算法和动态规划区别？

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

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