时间复杂度
通常采用算法中基本运算的频度来分析算法的时间复杂度，一个语句的频度是指该语句在算法中被重复执行的次数，算法中最深层循环内的语句频度就是我们所说的时间复杂度。
空间复杂度
一个程序在执行时除了需要存储空间来存储本身所用的指令、常数、变量和输入数据外，还需要一些辅助空间来实现，这个辅助空间的大小就是空间复杂度的大小。
什么是算法？算法的性质有哪些。
算法是由若干条指令组成的有穷序列。
性质：
（1）输入：具有0个或多个输入
（2）输出：至少产生一个输出
（3）有穷性：每一条指令的执行次数必须是有限的
（4）确定性：每条指令的含义必须是明确，无二含义
（5）可行性：每条指令的执行时间都是有限的
数的存储
（1）顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
（2）链式存储。不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存储。
（3）索引存储。在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字、地址）。其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多的时间。
（4）散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。其优点是检索，增加和删除节点的操作都很快；缺点是若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
顺序表和链表的区别
（1）存取方式
顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取元素。例如在第i个位置上执行存或取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次。
（2）逻辑结构与物理结构
采用顺序存储时，逻辑上相邻的元素，对应的物力存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置则不一定相邻，对应的逻辑关系是通过指针链接来表示的。
（3）查找、插入和删除操作
对于按值查找，顺序表无序时，两者的时间复杂度均为O(n);顺序表有序时，可采用折半查找，此时的时间复杂度为O(log2n)。
对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1)，而链表的平均复杂度为O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域，故而存储密度不够大。
（4）空间分配
顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率低下，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。
栈和队列的区别？
- 队列是允许在一端进行插入另一端进行删除的线性表。队列顾名思义就像排队一样，对于进入队列的元素按“先进先出”的规则处理，在删除表头进行删除在表尾进行插入。由于队列要进行频繁的插入和删除。
- 栈是只能在表尾进行插入和删除操作的线性表。对于插入到栈的元素按“后进先出”的规则处理，插入和删除操作都在栈顶进行，与队列类似一般用定长数组存储栈元素。由于进栈和出栈都是在栈顶进行。
如何区分循环队列是队空还是队满？
普通情况下，循环队列队空和队满的判定条件是一样的，都是Q.front==Q.rear。
队头指针指向第一个数，队尾指针指向最后一个数的下一个位置，即将要入队的位置。
方法一：牺牲一个单元来区分队空和队满，这个时候(Q.rear+1)%MaxSize=Q.front才是队满的标志。
方法二：类型中增设表示元素个数的数据成员。这样，队空的条件为Q.size=0，队满的条件为Q.size=MaxSize编译如何实现“括号配对检查”
1）出现的凡是“左括号”，则进栈；
2）出现的是“有括号”，首先检查栈是否空？若栈空，则表明该“右括号”多余，否则和栈顶元素比较，若相匹配，则栈顶“左括号”出栈，否则表明不匹配。
3）表达式检验结束时，若栈空，则表明表达式中匹配正确；否则表明“左括号”有余。栈在通过后缀表达式求值的算法思想？
1）顺序扫描表达式的每一项，然后根据它的类型做如下相应操作：
2）若该项是操作数，则将其压入栈中，
3）若该项是操作符，则连续从栈中退出两个操作数y和x，形成运算指令XY，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理后，栈顶存放的就是最后的计算结果。快速排序什么情况下效率最高，什么情况下效率最低？
在数据基本无序情况下效率最高；在数据基本有序情况下效率最低；
因为在基本有序情况下会向基准元素的左边或右边进行高深度递归。什么是递归算法？
递归算法是指一种通过将问题分解为同类的子问题而解决问题的方法。什么是NP问题？
np问题是指一个复杂问题不能确定在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。堆的特性是什么？如何利用堆进行排序？
特性：
（1）堆是完全二叉树；
（2）堆的每个节点大于等于他的两个子节点我们把它称为大根堆，堆的每个节点小于等于他的两个子节点我们把它称为小根堆；
排序：
若堆为大根堆，排序为从小到大排序，堆存储在R[1]到R[n]中
（1）交换R[1],R[n]的值，将R[1],R[n##1]重新建成大根堆。
（2）交换R[1],R[n##1]的值，将R[1],R[n##2]重新建成大根堆。
（3）重复上面操作。贪心算法的思想是什么？能得到最佳结果吗？
基本思想：
（1）将求解的问题分成若干子问题
（2）对于每个子问题求解，得到子问题的局部最优解
（3）把子问题的局部最优解合成原问题的解
不能简述用非递归求解递归方法
递归是一种自顶向下的方法，需要一个线性的空间开销，并需要不断的压栈和出栈。
反过来非递归求解递归算法时需要采用自底向上的方法。对链表设置头结点有什么好处？
（1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域。
（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表和非空表的处理都是一样的。头指针和头结点的区别？
头指针：是指向第一个节点存储位置的指针，具有标识作用，头指针是链表的必要元素，无论链表是否为空，头指针都存在。
头结点：是放在第一个元素节点之前，便于在第一个元素节点之前进行插入和删除的操作，头结点不是链表的必须元素，可有可无，头结点的数据域也可以不存储任何信息分治法的基本思想是什么？为什么采用递归关系进行分治算法的时间复杂度分析？
基本思想：将一个规模为N的问题分解成K个子问题，这些子问题相互独立且与原问题的性质相同，递归的求解这些子问题，然后合并其结果得到原问题的解。
因为分治法的子问题是相互独立的。树和图之间的区别
（1）树是一种特殊的图，它永远不会有多个路径。 从A到B总是有一种方法;图是一种具有多种方法来从任何点A到达任何其他点B的系统。
（2）树必须连接树;图可能未连接图形。
（3）树由于它已连接，所以我们可以从一个特定节点到达所有其他节点， 这种搜索称为遍历；遍历始终不适用于图形，因为图形可能未连接。
（4）树不包含回路，电路；图可能包含自循环，循环。
（5）树中必须有一个根节点；图中没有这种根节点；最小生成树和最短路径
普利姆算法：用来求最小生成树。从一个连通图中从某一顶点出发，选择与它关联的最小权值的边，将其顶点加入到顶点集S中，此后就从一个顶点在S集中，另一个顶点不在S集中的左右顶点中选择出权值最小的边，把对应顶点加入到S集中，直到所有的顶点都加入到S集中为止。
克鲁斯卡尔算法：用来求最小生成树，其基本思想为：设有一个有N个顶点的连通网中，选出权值最小的边且该边的两个端点不在一个连通分支中，则把该边加入到树中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个连通分支中为止。
迪杰斯特拉算法：迪杰斯特拉算法是经典的单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心层层向外扩展，直到扩展的终点为止，迪杰斯特拉算法要求边的权值不能为负权。
弗洛伊德算法：弗洛伊德算法是经典的求任一顶点之间的最短路径，其边的权值可为负权，该算法的时间复杂度为O(n3)，空间复杂度为O(n2)
图的遍历
图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历比树的遍历要复杂的多，因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组visited[]来标记顶点是否被访问过。
图的遍历算法主要有两种：广度优先搜索和深度优先搜索。
（1）广度优先搜索
类似于二叉树的层次遍历算法。基本思想：首先访问起始顶点V，接着由V出发，一次访问V的各个未访问过的邻接顶点W1,W2,…Wn，然后依次访问W1,W2…Wn的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为初始点，重复上述过程。Dijkstra源最短路径算法和Prim最小生成树算法也应用了类似的思想。
（2）深度优先搜索
它的基本思想如下：首先访问图中某一起始顶点V，然后由V出发，访问与V邻接且未被访问的任一顶点W1，再访问与W1邻接且未被访问的任一顶点W2…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
对各种查找方法的概括？
查找分为静态查找表和动态查找表，静态查找表包括：顺序查找、折半查找、分块查找；动态查找包括：二叉排序树和平衡二叉树。
（1）顺序查找：把待查关键字Key放入哨兵位置(i=0)，再从后往前依次把表中元素和key比较，如果返回值为0则查找失败，表中没有这个key值，如果返回值为元素的位置i，则查找成功，设置哨兵的位置是为了加快执行速度。他的时间效率为O(n)，其特点是：结构简单，对顺序结构和链式结构都适用，但是查找效率太低。
（2）折半查找：要求查找表为顺序存储结构并且有序，若关键字在表中则返回关键字的位置，若关键字不在表中时停止查找的典型标志是：查找范围的上界<=查找范围的下界。
（3）分块查找：先把查找表分为若干子表，要求每个子表的元素都要比他后面的子表的元素小，也就是保证块间是有序的，把各子表中的最大关键字构成一张索引表，表中还包含各子表的起始地址。他的特点是：块间有序，块内无序，查找时块间进行索引查找，块内进行顺序查找。
(4)二叉排序树：二叉排序树的定义为：或者是一颗空树，或者是一颗具有如下特点的树：如果该树有左子树，则其左子树的所有结点值小于根的值；若该树有右子树，则其右子树的所有结点值均大于根的值；其左右子树也分别为二叉排序树。在查找时可以进行动态的插入，插入结点要符合二叉排序树的定义，这也是动态查找和静态查找的区别，静态查找不能进行动态插入。
（5）平衡二叉树：平衡二叉树又称AVL树，它或者是一棵空树或者具有如下特点：他的左子树和右子树的高度差的绝对值不能大于1，且他的左右子树也都是平衡二叉树。
B树和B+树：
（1）B树，又称多路平衡二叉树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：
1> 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
2> 若根结点不是终端结点，则至少有两棵子树。
3> 除根结点外的所有非叶结点至少有m/2棵子树，即至少含有m/2-1个关键字。
4> 所有的叶结点都出现在同一层次上，并且不带信息。
B树是所有结点的平衡因子均等于0的多路平衡二叉树。
（2）B+树是应数据库所需而出现的一种B树的变形树。
一棵m阶的B+树需满足下列条件：
1> 每个分支结点最多有m棵子树。
2> 非叶根结点至少有两棵子树，其他每个分支结点至少有m/2棵子树。
3> 结点的子树个数与关键字个数相等。
4> 所有叶结点包含全部关键字及指向响应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
5> 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
m阶的B+树与m阶的B树的主要差异如下：
1> 在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有n+1棵子树。
2> 在B+树中，每个结点的关键字个数n的范围是m/2<=n<=m;在B树中，每个结点的关键字个数n的范围是m/2-1<=n<=m-1.
3> 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4> 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。
对各种内部排序的概括与总结？
排序：是指把一个任一元素的序列排列成一个按关键字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(nlog2n)，空间复杂度和待排序的元素个数相同。
（9）基数排序（稳定）：时间复杂度为：对于n各记录进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n)，回收的时间复杂度为为O(rd)。
总结：直接插入排序、冒泡排序和简单选择排序是最基本的排序方法，他们主要用于元素个数n不是很大的情形。
对于中等规模的元素序列，希尔排序是一种很好的选择。
对于元素个数n很大的情况，可以采用快排、堆排序、归并排序或基数排序，其中快排和堆排序都是不稳定的，而归并排序和基数排序是稳定的排序算法。