记：此篇博客是关于考研复试中专业课面试的相关知识点，按个人理解来总结的，用来锻炼自己的逻辑思维，可能不太准确，希望指正。
1、数组和链表的区别？
从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况，即数组大小定义之后不能改变，当数据增加时会超出数组的长度，当数据减少时会造成内存浪费。链表与数组相反，它能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。
从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是连式存储结构，他的存储空间不是必须连续的，可以是任意的，因此链表的访问必须从前往后依次进行，访问效率较数组来说比较低。
如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O（n），而单链表来说只需要在第一次寻找i的位置时时间复杂度为O（n），其余的插入和删除操作时间复杂度均为O(1），大大提高了插入和删除的效率。所以当插入和删除操作频繁时，链表的优势就越明显。
2、单链表结构和顺序存储结构的区别？
存储分配方式：顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。
时间性能：当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为O（n^2），而单链表在确定i位置的指针后，其时间复杂度仅为O（1）。
空间性能：由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受限制。
3、头指针和头结点的区别？
头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。
头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。
双向链表：即在单链表的每个节点上添加一个指向其前驱结点的指针域，双向链表中每个节点都有两个指针域，分别指向其直接前驱和直接后继，用空间换取了时间上的性能优化。
4、逻辑结构与物理结构？
数据的逻辑结构包括4种，（1）集合：数据元素之间除了有相同的数据类型再没有其他的关系 （2）线性结构：数据元素之间是一对一的关系 （3）树形结构：数据元素之间是一对多的关系 （4）图状结构：数据元素之间是多对多的关系。
物理结构也有4中，（1）顺序存储结构 （2）链式存储结构 （3）索引存储结构 （4）散列存储结构
5、邻接矩阵与邻接表的区别？
邻接矩阵表示：无向图的邻接矩阵是对称的，矩阵的行或列的有效元素的个数之和是节点的度。有向图的邻接矩阵不一定对称，矩阵中行的有效元素的个数之和是节点的出度，列的有效元素的个数之和是节点的入度。
邻接表表示：无向图的每条边在邻接表中存储两次，若想知道节点的度，只需要求出对应链表中节点的个数即可。有向图的边在邻接表中仅存储一次，若想知道节点的出度，则需要遍历对应的链表，若要求节点的入度则还需要遍历其他的链表。
邻接矩阵的优点是可以很方便的知道两个节点之间是否存在边，以及快速的添加或删除边；缺点是如果邻接矩阵中节点个数比较少容易造成存储空间的浪费。
邻接表的优点是节省空间，只给实际存在的边分配存储空间；缺点是在涉及度时可能需要遍历整个链表。
6、用循环比递归的效率高吗？
循环和递归两者是可以互换的，不能决定性的说循环的效率比递归高。
递归的优点是：代码简洁清晰，容易检查正确性；缺点是：当递归调用的次数较多时，要增加额外的堆栈处理，有可能产生堆栈溢出的情况，对执行效率有一定的影响。
循环的优点是：结构简单，速度快；缺点是：它并不能解决全部问题，有的问题适合于用递归来解决不适合用循环。
7、贪心算法和动态规划以及分治法的区别？
贪心算法顾名思义就是做出在当前看来是最好的结果，它不从整体上加以考虑，也就是局部最优解。贪心算法从上往下，从顶部一步一步最优，的到最后的结果，它不能保证全局最优解，与贪心策略的选择有关。
动态规划是把问题分解成子问题，这些子问题可能有重复，可以记录下前面子问题的结果防止重复计算。动态规划解决子问题，前一个子问题的解对后一个子问题产生一定的影响。在求解子问题的过程中保留哪些有可能得到最优的局部解，丢弃其他局部解，直到解决最后一个问题时也就是初始问题的解。动态规划是从下到上，一步一步找到全局最优解。
8、单链表和双链表？
当存储多个类型一样的数据元素的时候可以用数组来存储，数组可以根据下标进行随机访问，但数组有一个缺陷是不能动态的进行插入和删除操作，而链表刚好弥补了这个缺陷，对于元素的插入和删除很方便，但是访问的效率下降了很多。
单链表是只有一个指针指向其后继节点的地址，只要知道单链表的首地址便能够遍历整个链表，由于单链表的存储空间不一定连续，所以不能进行随机访问，只有通过next指针才能够访问到下一个节点。单链表只能向后访问，而不能够逆向访问，为了克服这一缺陷，有了使用更广泛的双链表，即在单链表的基础上添加一个指向其前驱节点的指针域，实现双向遍历，但是也只能顺序访问，用空间换取了时间上的性能改进。
9、栈和队列的区别？
队列是允许在一段进行插入另一端进行删除的线性表。队列顾名思义就像排队一样，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。由于队列要进行频繁的插入和删除，一般为了高效，选择用定长数组来存储队列元素，在对队列进行操作之前要判断队列是否为空或是否已满。如果想要动态长度也可以用链表来存储队列，这时要记住队头和对位指针的地址。
栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行，与队列类似一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行，因此要有一个size变量来记录当前栈的大小，当进栈时size不能超过数组长度，size+1，出栈时栈不为空，size-1。
10、栈和队列的相同之处和不同之处？
相同点：（1）栈和队列都是线性结构 （2）栈和队列在插入时都是在表尾进行 （3）栈和队列都可以用顺序结构或者链表表示 （4）栈和队列插入和删除操作的时间复杂度和空间复杂度都一样。
不同点：（1）在删除元素时位置不同，栈在表尾进行，队列在表头进行 （2）用链表存储时，栈可以实现多栈空间共享（共享栈），队列却不行。
11、算法的特点？
算法的五大特性：确定性、有穷性、可行性，有0个或多个输入、有1个或多个输出
时间复杂度：算法的执行时间与原操作的执行次数之和成正比
空间复杂度：如果输入数据所占空间只取决于问题本身，而与算法无关，只需要分析除了输入和程序之外的辅助变量所占用的空间即可。
12、线性链表？
线性链表中一个节点代表一个存储空间，即存储节点，简称节点。每一个节点包括两部分，分别是指针域，用来存储指向下一个或前一个节点的地址，数据域用来存储数据元素的值。链式存储结构中，存储空间是可以不连续的，也就是数据的存储顺序与数据元素的逻辑结构可以不相同，数据元素之间的逻辑关系由指针域来确定。且链式存储结构可以用来表示线性结构也可以用来表示非线性结构。
13、树与二叉树的相关概念？
树是非线性结构，其元素之间有明显的层次关系。在树的结构中，每个节点都只有一个前件称为父节点，没有前件的节点为树的根节点，简称为树的根；每个节点可以有多个后件成为节点的子节点，没有后件的节点称为叶子节点。
在树的结构中，一个节点所拥有的子节点个数称为该节点的度，树中最大的节点的度为树的度，树的最大的层次称为树的深度
二叉树：在二叉树中只有一个根节点，一个节点最多只能有两个子节点，称为左子树和右子树。
满二叉树：满二叉树是指除了最后一层外其他节点均有两颗子树，第k层有2^（k-1）个节点，深度为m的树共有2^m-1个节点
完全二叉树：完全二叉树是指除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点
二叉树的存储：二叉树可以用链式存储结构来存储，满二叉树和完全二叉树可以用顺序存储结构来存储
二叉树的遍历：二叉树有先序遍历（根左右），中序遍历（左根右）和后续遍历（左右根）
14、图的相关概念？
图的表示：G=（V,E）=（顶点，边）；无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边
迪杰斯特拉（dijkstra）算法：迪杰斯特拉算法是经典的单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心层层向外扩展，直到扩展的终点为止，迪杰斯特拉算法要求边的权值不能为负权。
弗洛伊德（Floyd）算法：弗洛伊德算法是经典的求任意顶点之间的最短路径，其边的权值可为负权，该算法的时间复杂度为O(N^3),空间复杂度为O（N^2）。
普里姆（prim）算法：用来求最小生成树，其基本思想为：从联通网络N={V,E}中某一顶点u0出发，选择与他关联的最小权值的边，将其顶点加入到顶点集S中，此后就从一个顶点在S集中，另一个顶点不在S集中的所有顶点中选择出权值最小的边，把对应顶点加入到S集中，直到所有的顶点都加入到S集中为止。
克鲁斯卡尔（kruskal）算法：用来求最小生成树，其基本思想为：设有一个有N个顶点的联通网络N={V,E},初试时建立一个只有N个顶点，没有边的非连通图T，T中每个顶点都看作是一个联通分支，从边集E中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到T中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。
15、深度优先搜索步骤？
（1）访问起始点v
（2）若v的第一个邻接点没有被访问过，则深度遍历该邻接点；
（3）若v的第一个邻接点已经被访问，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止
16、广度优先搜索的步骤？
（1）访问起始点v
（2）依次遍历v的所有未访问过得邻接点
（3）再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止
17、拓扑排序的概念以及实现？
拓扑排序在工程中的应用十分重要，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程完成后才能执行。把以顶点为活动，边为活动间先后顺序关系的有向图成为顶点活动网，简称为AOV网。一个AOV网应该是有向无环图，不应该存在回路，如果要存在回路的话则该回路上的所有活动都无法执行。在AOV网中如果不存在回路，则可以把所有的活动排列成一个序列，称该序列为拓扑序列，拓扑序列并不是唯一的。形成拓扑序列的过程称为拓扑排序。
拓扑排序的步骤：
（1）在有向图中任意选择一个没有前驱的节点输出
（2）从图中删去该节点以及与他相连的边
（3）重复以上步骤，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图，所以可以通过拓扑排序来判断一个图是否存在环。
18、关键路径的相关概念？
AOE网是一种以顶点为事件，弧为活动，权为活动的持续时间的带权有向无环图，通常AOE网用来估算工程的完成时间。
关键路径：在AOE网中，从起始点到终点的最大路径长度的路径为关键活动。最大路径长度是指：该路径上的活动持续时间之和最大。
关键活动：关键路径上的活动为关键路径，关键活动的最早开始时间等于最晚开始时间。由于AOE网中的某些活动是可以同时发生的，所以完成整个工程的时间应该是从始点到终点的最大路径长度，关键路径长度即为工程的最短完成时间。
19、对各种查找方法的概括？
查找表是成为集合的数据结构，各元素间的约束力最差的数据结构，各元素除了在同一个集合中就再没有其他关系。查找分为静态查找表和动态查找表；静态查找表包括：顺序查找、折半查找、分块查找；动态查找包括：二叉排序树和平衡二叉树。
（1）顺序查找：把待查关键字key放入哨兵位置（i=0），再从后往前依次把表中元素和key比较，如果返回值为0则查找失败，表中没有这个key值，如果返回值为元素的位置i（i!=0）则查找成功，设置哨兵的位置是为了加快执行速度。他的时间效率为O（n），其特点是：结构简单，对顺序结构和连式结构都适用，但是查找效率太低。
（2）折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上界<=查找范围的下界。
（3）分块查找：先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，也就是保证块间是有序的（但是子表内不一定有序），把各子表中的最大关键字构成一张索引表，表中还包含各子表的起始地址。他的特点是：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。
（4）二叉排序树：二叉排序树的定义为：或者是一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树。在查找时可以进行动态的插入，插入节点要符合二叉排序树的定义，这也是动态查找和静态查找的区别，静态查找不能进行动态插入。
（5）平衡二叉树：平衡二叉树又称为AVL树，它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。
平衡因子：是指左子树的高度减去右子树的高度，它的值只能为1,0，-1
如果再一个平衡二叉树中插入一个节点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括4中情况：在左子树的左子树上插入节点时向右进行单向旋转；在右子树的右子树上插入节点时向左进行单向旋转；在左子树的右子树插入节点时先向左旋转再向右旋转；在右子树的左子树插入节点时先向右旋转再向左旋转。
20、哈希表的概念、哈希函数的构造方法、哈希冲突的解决办法？
哈希表又称为散列表，是根据关键字码的值直接进行访问的数据结构，即它通过把关键码的值映射到表中的一个位置以加快查找速度，其中映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希函数的构造方法包括：直接定址法，除留余数法，数字分析法，平方取中法，折叠法，随机数法
（1）直接定址法：取关键字的某个线性函数值作为散列地址，H(key)=a*key+b。
（2）除留余数法：取关键字对p取余的值作为散列地址，其中p<m,即H(key)=key%p (p<m)。
（3）数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列的地址，适用于所有关键字都已知的情况。
（4）平方取中法：对关键字求平方，再取结果中的中间几位作为散列地址。
（5）折叠法：将关键字分为位数相同的几部分，然后取这几部分的叠加和作为散列地址。适用于关键字位数较多，且关键字中每一位上数字分布大致均匀。
（6）随机数法：选择一个随机函数，把关键字的随机函数值作为散列地址。适合于关键字的长度不相同时。
哈希冲突的解决方法包括：开放定址法和拉链法，当冲突发生时，使用某种探测技术形成一个探测序列，然后沿此序列逐个单单元查找，直到找到该关键字或者碰到一个开放的地址为止，探测到开放的地址表明该表中没有此关键字，若要插入，则探测到开放地址时可将新节点插入该地址单元。其中开放定址法包括：线性探查法，二次探查法，双重散列法
（1）线性探查法：基本思想，探查时从地址d开始，首先探查T[d],在探查T[d+1]...直到查到T[m-1]，此后循环到T[0],T[1]...直到探测到T[d-1]为止。
（2）二次探查法：基本思想，探查时从地址d开始，首先探查T[d],再探查T[d+1^2],T[d+2^2]...等，直到探查到有空余地址或者探查到T[d-1]为止，缺点是无法探查到整个散列空间。
（3）双重散列法：基本思想，使用两个散列函数来确定地址，探查时从地址d开始，首先探查T[d],再探查T[d+h1(d)],T[d+2*h1(d)]...
链接法：将所有关键字为同义词的节点链接在同一个单链表中，若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组，凡是散列地址为i的节点均插入到头指针为i的单链表中。
21、对各种内部排序的概括与总结？
排序：是指把一个任意元素的序列排列成一个按关键字key有序的序列。内部排序包括：插入排序、选择排序、交换排序、归并排序、基数排序。其中插入排序包括：直接插入排序、折半插入排序、希尔排序；选择排序包括：简单选择排序，堆排序；交换排序包括：冒泡排序、快速排序。
（1）直接插入排序（稳定）：基本思想为：将序列分为有序部分和无序部分，从无序部分依次选择元素与有序部分比较找到合适的位置，将原来的元素往后移，将元素插入到相应位置上。时间复杂度为：O（n^2）,空间复杂度为O（1）
（2）折半插入排序（稳定）：基本思想为：设置三个变量low high mid，令mid=(low+high)/2,若a[mid]>key,则令high=mid-1,否则令low=mid+1,直到low>high时停止循环，对序列中的每个元素做以上处理，找到合适位置将其他元素后移进行插入。他的比较次数为O(nlog2n),但是因为要后移，因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是：比较次数大大减少。
（3）希尔排序（不稳定）：基本思想为：先将序列分为若干个子序列，对各子序列进行直接插入排序，等到序列基本有序时再对整个序列进行一次直接插入排序。优点是：让关键字值小的元素能够很快移动到前面，且序列基本有序时进行直接插入排序时间效率会提升很多，空间复杂度为O（1）。
（4）简单选择排序（不稳定）：基本思想为：将序列分为2部分，每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。优点是：实现起来特别简单，缺点是：每一趟只能确定一个元素的位置，时间效率低。时间复杂度为O（n^2），空间复杂度为O（1）。
（5）堆排序（不稳定）：设有一个任意序列，k1,k2,...,kn，当满足下面特点时称之为堆：让此序列排列成完全二叉树，该树具有以下特点，该树中任意节点均大于或小于其左右孩子，此树的根节点为最大值或者最小值。优点是：对大文件效率明显提高，但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。
（6）冒泡排序（稳定）：基本思路为：每一趟都将元素进行两两比较，并且按照“前小后大”的规则进行交换。优点是：每一趟不仅能找到一个最大的元素放到序列后面，而且还把其他元素理顺，如果下一趟排序没有发生交换则可以提前结束排序。时间复杂度为O（n^2）,空间复杂度为O（1）。
（7）快速排序（不稳定）：基本思路为：在序列中任意选择一个元素作为中心，比它大的元素一律向后移动，比它小的元素一律向前移动，形成左右两个子序列，再把子序列按上述操作进行调整，直到所有的子序列中都只有一个元素时序列即为有序。优点是：每一趟不仅能确定一个元素，时间效率较高。时间复杂度为O(nlog2n),空间复杂度为O（log2n）.
（8）归并排序（稳定）：基本思想为：把两个或者两个以上的有序表合并成一个新的有序表。时间复杂度为O（nlogn）,空间复杂度和待排序的元素个数相同。
（9）基数排序：时间复杂度为：对于n个记录进行链式基数排序的时间复杂度为O（d(n+rd)）,其中每一趟分配的时间复杂度为O(n),回收的时间复杂度为O（rd）。
各种排序的总结表格如下：
数据结构部分更新完毕~
