说明：这些是自己整理回答的答案 可以借鉴 也可能存在错误 欢迎指正
文章目录逻辑结构与物理结构的区别算法常见的数据结构链表存储结构和顺序存储结构的区别数组和链表的区别头指针和头结点的区别线性链表判断整个链表是否有环，如何找到这个环单链表和双链表的区别简述KMP算法栈和队列的区别两个栈实现队列，两个队列实现栈两个栈实现队列树和二叉树的相关概念提问：二叉树和度为2的树的区别二叉树遍历树的遍历二叉平衡树、二叉排序树红黑树图的相关概念图的存储结构深度优先遍历与广度优先遍历最小生成树的算法（普利姆算法，克鲁斯卡尔算法）普利姆算法（Prim）克鲁斯卡尔算法什么时候最小生成树唯一最短路径Dijkstra算法（迪杰斯特拉）floyd算法拓扑排序的概念以及实现关键路径的相关概念各种排序的概括与总结各种查找方法快速排序的优化B树和B+树的区别，以一个m阶数为例哈希表（概念、构造方法、冲突解决）建立方法冲突解决方法用循环比递归的效率高吗？贪心算法和动态规划区别？ 逻辑结构与物理结构的区别逻辑结构 ：是指数据对象中数据元素之间的相互关系
逻辑结构分类：
集合——各个元素之间是“平等”的，类似于数学里面的集合线性结构——数据结构中的数据元素是一对一关系的树性结构——数据结构中的数据元素之间存在一对多的层次关系图形结构——数据结构中的数据元素之间存在多对多的关系物理结构 ：是指数据的逻辑结构在计算机中的存储形式
物理结构的分类：
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的出边邻接点，则权值为∞。
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|