选择 2* 10个
填空2* 10个
简答 3* 4个
程序分析填空 4* 4个
综合（代码）8* 4个
1.算法的定义
算法就是解决问题的方法，是解决某一特定问题的一组有穷指令的序列，是完成一个任务所需要的具体步骤和方法
2.算法的特征
-
有限性 一个算法总是在执行了有穷步的运算之后终止
-
确定性：算法的每种运算必须要有确切的定义，不能有二义性。
-
输入：每个算法有0个或多个输入。所谓0个输入是指算法本身定出了初始条件。
-
输出：一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量
-
可行性：算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成。（实数的算术运算是“不能行”的）
3.计算过程
只满足确定性、能行性、输入、输出四个特性但不一定能终止的一组规则
4.算法的有穷性意味着不是所有的计算机程序都是算法
5.算法正确性证明
数学归纳法，反例：能够使算法运行失败的输入实例
6.算法的好坏：
通过数学方法进行分析，时间复杂度，空间复杂度，循环次数（归并，快排，贪心的复杂度）
7.算法运行中主要影响运行时间的语句是基本操作，即占有最多比例的语句
8.时间复杂度分析：
1）确定用来表示问题规模的变量；
2）确定算法的基本操作；
3）写出基本操作执行次数的函数（运行时间函数）；
4）如果函数依赖输入实例，则分情况考虑：最坏情况、最好情况、平均情况；
5）只考虑问题的规模充分大时函数的增长率，用渐近符号O 、Θ、Ω 、o 来表示。
6）常用O和Θ
9.基本操作
算法中的某个初等操作，基本操作的选择，必须反映出该操作随着输入规模的增加而变化的情况
1.递归
若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。
分为直接递归和间接递归
2.特点
（1）将问题分解成为形式上更加简单的子问题来进行求解，递归过程一般通过函数或子过程来实现
（2）问题求解规模缩小,把问题转化为规模缩小了的同类问题的子问题
（3）相邻两次重复之间有紧密的联系
（4）是否收敛，即终止条件
3.使用递归的三种情况
- 问题的定义
- 数据结构
- 问题求解的过程
4.递归模型
递归边界（递归的终止条件）和递归体
5.过程
先将整个问题划分为若干个子问题,通过分别求解子问题,最后获得整个问题的解。这种自上而下将问题分解、求解,再自下而上引用、合并,求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。
6.二分查找
7.阶乘：
8.斐波那契：
9.汉诺塔：
10.顺序表最大值：
11.辗转相除法：
12.函数调用
- 将返回地址、所有实参等信息传递给被调用函数保存；
- 为被调用函数的局部变量分配存储区；
- 将控制转移到被调用函数的入口。
13.函数返回
- 保存被调函数的计算结果；
- 释放被调函数保存局部变量的数据区；
- 依照被调函数保存的返回地址将控制转移到调用函数。
14.优点
- 结构清晰
- 程序易读
- 容易证明
15.缺点
- 时间效率低
- 空间开销大
- 不容易优化
1.分治法
将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并，得到原问题的解
2.三个步骤
划分，解决，合并
3.采用平衡(balancing)子问题的思想
影响复杂性的主要因素：子问题个数，合并开销函数。
4.使用条件
（1）缩小规模可以解决
（2）具有最优子结构性质
（3）子问题解可以合并
（4）子问题相互独立
5.二分搜索算法（logn）：
6.合并排序（辅助空间O(n)）
7.快速排序 优化：三平均分区
8.大整数乘法
快速傅利叶变换O(nlogn)
9.平面最接近点对问题
给定平面上n个点，在n个点组成的所有点对中，找出其中相互距离最小的一对点。
10.循环赛日程表
设有n=2k个运动员要进行羽毛球循环赛，现要设计一个满足以下要求的比赛日程表：
（1）每个选手必须与其它n-1个选手各赛一次；
（2）每个选手一天只能比赛一次；
（3）循环赛一共需要进行n-1天。
1.最优化问题
求一个问题的可行解（符合条件的解决方案）和最优解（使优化函数取得最佳值的可行解，可以是多个）的问题
2.贪心法采用逐步构造最优解的方法向给定的目标前进
3.在每个局部阶段，都做出一个看上去最优的决策(即某种意义下的、或某个标准下的局部最优解)，并期望通过每次所做的局部最优选择产生出一个全局最优解。
4.做出贪心决策的依据称为贪心准则(策略)
5.贪心算法不能对所有问题都得到整体最优解，它所作出的选择只是在某种意义上的局部最优选择,贪心法一般需要对原始数据预处理（排序）
6.最优化度量的选择是贪心算法的关键
7.最优子结构
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质（动态规划、贪心的关键）
8.贪心算法通常以自顶向下的方式进行，是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解
9.一般可以通过对算法步数的归纳或通过对问题规模的归纳来证明贪心法的正确性
10.活动安排问题：早完成的活动先安排（按结束时间增序排列）
11.背包问题（背包问题可以用贪心算法求解，而0-1背包问题不行）
（5） 算法的计算时间上界为O(nlogn)
12.最优装载问题
有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。
13.多机调度问题（贪心算法得到其近似解,不一定最优）
调度时间最短—贪心选择作业执行时间大者，将其调度到可最早开始加工它的机器上
一共三台机器
时间复杂性分析：O(nlogn+nlogm)
多机问题不一定得到最优解：不具有贪心选择性质和最优子结构。
14.旅行商问题（贪心不保证求得旅行商问题的精确解，只能得到问题地近似解）
表格为两点之间距离（连接矩阵）
问题归结为在(n-1)!个回路中选取最小回路
图用连接矩阵W[i][j]给出，即W[i][j]为结点i到结点j的权重。
Path[]记录依次连接的城市，p记录当前到达的最后一个顶点，cost为当前路径长度。
如果节点k已经到达，则arrived[k]=true。
从节点1出发：
Path=<1,2,5,3,4,1> ;cost=14;
从节点2出发：
Path=<2,1,3,4,5,2> ;cost=10;
且此为最优解！
算法复杂度O(),改进算法则从每个节点计算一遍，找到最小值，复杂度O()
15.最小生成树
Prim算法的做法：在保证连通的前提下依次选出权重较小的n – 1条边（在实现中体现为n个顶点的选择）（减边）
- Prim算法为两重循环，外层循环为n次，内层循环为O(n)，因此其复杂性为O(n2)。
- Kruskal算法中，设边数为e，则边排序的时间为O(eloge)，最多对e条边各扫描一次，每次确定边的时间为O(loge)，所以整个时间复杂性为O(eloge)。
- 当e = Ω()时，Kruskal算法要比Prim算法差；
- 当e = ο()时，Kruskal算法比Prim算法好得多。
16.单源最短路径
时间复杂度为 O()
但没有给出最短通路
17.哈夫曼编码
算法复杂度O(nlogn)
1.动态规划是用来解决多阶段决策过程最优化的一种数量方法
2.多阶段决策问题
是动态决策问题的一种特殊形式，每个阶段都要进行决策
3.动态规划方法的关键
基本的递推关系式和恰当的边界条件（简称基本方程）
4.最优化原理
一个最优策略的子策略也是最优的
5.最优子结构
问题的最优解包含着其子问题的最优解
同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快
6.子问题的重叠性质
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次
7.动态规划基本步骤
找出最优解的性质，并刻划其结构特征。
递归地定义最优值。
以自底向上的方式计算出最优值。
根据计算最优值时得到的信息，构造最优解。
8.数字三角形
9.投资分配问题
求只有工厂一时候利润
10.0/1背包问题
如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。
如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；
11.最长公共子序列
状态矩阵：相同为1走左上，左面大是2，上面大是3，从右下角画路径，经过的"1"的对应行列即为选择的字母的下标，
12.最优二叉查找树（二叉排序树）
设一个二维表C[n+1][n+1]，其中C[i][j]表示二叉查找树T(i, j)的平均比较次数。注意到在式3中，当k=1时，求C[i][j]需要用到C[i][0]，当k=n时，求C[i][j]需要用到C[n+1][j]，所以，二维表C[n+1][n+1]行下标的范围为1～n+1，列下标的范围为0～n。
为了在求出由{r1, r2, …, rn}构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表R[n+1][n+1]，其下标范围与二维表C相同，R[i][j]表示二叉查找树T(i, j)的根结点的序号
1.回溯和分枝限界法是比较常用的对候选解进行系统检查两种方法.通常能够用来求解规模很大的问题
具有限界函数的深度优先生成法称为回溯法
2.结点
- 扩展结点（E-结点,Expansion Node）
一个正在产生儿子的结点称为扩展结点 - 活结点（L-结点,Live Node）
一个自身已生成但其儿子还没有全部生成的节点称做活结点 - 死结点（D-结点,Dead Node）
一个所有儿子已经产生的结点称做死结点
3. 解空间
对于问题的一个实例，解向量满足显式约束条件的所有多元组，至少包含问题的一个（最优）解同一问题可有多种表示
4.基本步骤
(1)针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
5.剪枝函数
用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。
在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷
6.空间复杂性
- 在任何时刻，算法只保存从根结点到当前扩展结点的路径。
- 如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。
- 显式地存储整个解空间则需要O(2h(n）)或O(h(n)!)内存空间。
7.三要素
- 解空间
- 约束条件
- 状态树
8.0-1背包
代码
9.n皇后问题
在一个n*n的国际象棋棋盘上放置n个皇后，使得它们中任意2个之间都不互相“攻击”，即任意2个皇后不可在同行、同列、同斜线上。
输出N，⑴求N皇后问题的一种放法；
⑵求N皇后问题的所有放法
状态树
代码
10.装载问题
11.批处理作业调度
12.着色问题
13.推销员问题
走到每一个叶节点，比较得到最小值（如果在路上已经比当前最优解大，直接返回上一节点）
整个算法的计算时间复杂性为O(n!)。
14.代码框架
递归
迭代（非递归）
子集树
从n个元素的集合S中找出S满足某种性质的子集，相应的解空间称为子集树。通常有2n个叶结点，结点总数为2n+1-1。需Ω(2n)计算时间。
如n个物品的0-1背包问题的解空间是一棵子集树。
排列树
当所给问题的确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。因此遍历排列树需要Ω(n!)计算时间。
TSP(旅行售货员问题)的解空间是一棵排列树。
效率影响因素
(1)产生x[k]的时间；
(2)满足显约束的x[k]值的个数；
(3)计算约束函数constraint的时间；
(4)计算限界函数bound的时间；
(5)满足约束函数和上界函数的所有x[k]的个数。
1.定义
分支限界算法=广度优先搜索+剪枝策略
- 将根结点加入队列中
- 接着从队列中取出首结点，使其成为当前扩展结点，一次性生成它的所有孩子结点，判断孩子结点是舍弃还是保存。舍弃那些不可能导致可行解或最优解的孩子结点，其余的结点则保存在队列中
- 重复上述扩展过程，直到找到问题的解或队列为空时为止。
每一个活结点最多只有一次机会成为扩展结点。
2.分类（根据活结点表的维护方式）
队列式分支限界法
优先队列式分支限界法
3.步骤
- 定义问题的解空间
- 确定问题的解空间组织结构（树或图）
- 搜索解空间。搜索前要定义判断标准（约束函数或限界函数），如果选用优先队列式分支限界法，则必须确定优先级。
4.关键问题
（1）如何确定合适的限界函数
（2）如何组织待处理结点表
（3）如何确定最优解中的各个分量
5.0-1背包问题
考虑实例n=4，w=[3,5,2,1]，v=[9,10,7,4]，C=7。
cp初始值为0；rp初始值为所有物品的价值之和；bestp表示当前最优解，初始值为0。
当cp>bestp时，更新bestp为cp。
一层一层更新
6. 旅行售货员问题
队列式分支限界法
优先队列式分支限界法
优先级：活结点所对应的已经走过的路径长度cl，长度越短，优先级越高。
7.布线问题
8.与回溯法比较
相同点
-
均需要先定义问题的解空间，确定的解空间组织结构一般都是树或图。
-
在问题的解空间树上搜索问题解。
-
搜索前均需确定判断条件，该判断条件用于判断扩展生成的结点是否为可行结点。