数据结构复习
1、数组和链表的区别？
从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表与数组相反，它能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。
从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是连式存储结构，它的存储空间可以是任意的，因此链表的访问必须从前往后依次进行，访问效率较数组来说比较低。
2、单链表结构和顺序存储结构的区别？
存储分配方式：顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。
时间性能：当进行插入和删除操作时，顺序存储结构每次都需要移动元素，总的时间复杂度为O（n^2），而单链表在确定i位置的指针后，其时间复杂度仅为O（1）。
空间性能：由于顺序存储结构需要进行预分配存储空间，所以容易造成空间浪费或者溢出。链式存储结构不需要预分配存储空间，元素个数不受限制。
3、头指针和头结点的区别？
头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。
头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息。
4、逻辑结构和物理结构
数据的逻辑结构包括4种：集合、线性结构、树形结构、图状结构
物理结构包括四种：顺序存储、链式存储、索引存储、散列存储
5、邻接矩阵与邻接表的区别？
邻接矩阵表示：无向图的邻接矩阵是对称的，矩阵的行或列的有效元素的个数之和是节点的度。有向图的邻接矩阵不一定对称，矩阵中行的有效元素的个数之和是节点的出度，列的有效元素的个数之和是节点的入度。
邻接表表示：无向图的每条边在邻接表中存储两次，若想知道节点的度，只需要求出对应链表中节点的个数即可。有向图的边在邻接表中仅存储一次，若想知道节点的出度，则需要遍历对应的链表，若要求节点的入度则还需要遍历其他的链表。
6、栈和队列的区别？
队列是允许在一段进行插入另一端进行删除的线性表。队列顾名思义就像排队一样，对于进入队列的元素按“先进先出”的规则处理，在表头进行删除在表尾进行插入。由于队列要进行频繁的插入和删除，一般为了高效，选择用定长数组来存储队列元素，在对队列进行操作之前要判断队列是否为空或是否已满。
栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行，与队列类似一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行，因此要有一个size变量来记录当前栈的大小，当进栈时size不能超过数组长度，size+1，出栈时栈不为空，size-1。
7、算法的特点？
算法的五大特性：确定性、有穷性、可行性，有0个或多个输入、有1个或多个输出
8、树与二叉树的相关概念？
树是非线性结构，其元素之间有明显的层次关系。在树的结构中，每个节点都只有一个前件称为父节点，没有前件的节点为树的根节点，简称为树的根；每个节点可以有多个后件成为节点的子节点，没有后件的节点称为叶子节点。
在树的结构中，一个节点所拥有的子节点个数称为该节点的度，树中最大的节点的度为树的度，树的最大的层次称为树的深度
二叉树：在二叉树中只有一个根节点，一个节点最多只能有两个子节点，称为左子树和右子树。
满二叉树：满二叉树是指除了最后一层外其他节点均有两颗子树，第k层有2（k-1）个节点，深度为m的树共有2m-1个节点
完全二叉树：完全二叉树是指除了最后一层外，其他任何一层的节点数均达到最大值，且最后一层也只是在最右侧缺少节点
二叉树的存储：二叉树可以用链式存储结构来存储，满二叉树和完全二叉树可以用顺序存储结构来存储
二叉树的遍历：二叉树有先序遍历（根左右），中序遍历（左根右）和后续遍历（左右根）
9、图的相关概念？
图的表示：G=（V,E）=（顶点，边）；无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边
迪杰斯特拉（dijkstra）算法：单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心层层向外扩展，直到扩展的终点为止，迪杰斯特拉算法要求边的权值不能为负权。
洛伊德（Floyd）算法：求任意顶点之间的最短路径，其边的权值可为负权
10、深度优先搜索步骤？
（1）访问起始点v
（2）若v的第一个邻接点没有被访问过，则深度遍历该邻接点；
（3）若v的第一个邻接点已经被访问，则访问其第二个邻接点，进行深度遍历；重复以上步骤直到所有节点都被访问过为止
11、广度优先搜索的步骤？
（1）访问起始点v
（2）依次遍历v的所有未访问过得邻接点
（3）再依次访问下一层中未被访问过得邻接点；重复以上步骤，直到所有的顶点都被访问过为止
12、拓扑排序的步骤：
（1）在有向图中任意选择一个没有前驱的节点输出
（2）从图中删去该节点以及与他相连的边
（3）重复以上步骤，直到所有的顶点都输出或者当前图中不存在无前驱的顶点为止，后者代表该图是有环图，所以可以通过拓扑排序来判断一个图是否存在环。
13、关键路径的相关概念？
AOE网是一种以顶点为事件，弧为活动，权为活动的持续时间的带权有向无环图，通常AOE网用来估算工程的完成时间。
关键路径：在AOE网中，从起始点到终点的最大路径长度的路径为关键活动。最大路径长度是指：该路径上的活动持续时间之和最大。
关键活动：关键路径上的活动为关键路径，关键活动的最早开始时间等于最晚开始时间。由于AOE网中的某些活动是可以同时发生的，所以完成整个工程的时间应该是从始点到终点的最大路径长度，关键路径长度即为工程的最短完成时间。
14、对各种查找方法的概括？
（1）顺序查找：把待查关键字key放入哨兵位置（i=0），再从后往前依次把表中元素和key比较，如果返回值为0则查找失败，表中没有这个key值，如果返回值为元素的位置i（i!=0）则查找成功，设置哨兵的位置是为了加快执行速度。他的时间效率为O（n）
（2）折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时则查找左右子部分，停止查找的典型标志是：查找范围的上界 <= 查找范围的下界
（3）二叉排序树：或者是一棵空树，或者是一棵具有如下特点的树：如果该树有左子树，则其左子树的所有节点值小于根的值；若该树有右子树，则其右子树的所有节点值均大于根的值；其左右子树也分别为二叉排序树。
（4）平衡二叉树：它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。 如果再一个平衡二叉树中插入一个节点可能造成失衡，这时就要进行树结构的调整，即平衡旋转。包括4中情况：在左子树的左子树上插入节点时向右进行单向旋转；在右子树的右子树上插入节点时向左进行单向旋转；在左子树的右子树插入节点时先向左旋转再向右旋转；在右子树的左子树插入节点时先向右旋转再向左旋转。
15、对各种内部排序的概括与总结？
（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）