笔试部分
一．简答题(40分)
1.算法的基本概念、性质及其与程序的联系与区别
算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。 算法性质：输入---有零个或者多个外部量作为算法的输入； 输出---算法产生至少一个量最为输出；
确定性：组成算法的每条指令是清晰的、无歧义的； 有限性：算法中指令的执行次数有限和执行的时间有限。
程序：是算法用某种设计语言的具体实现，程序可以不满足算法的有限性。
2.大O表示法的含义和渐进时间复杂度（要会计算复杂度）
大O表示法：称一个函数g(n)是O(f(n))，当且仅当存在常数c>0和n0>=1，对一切n>n0均有|g(n)|<=c|f(n)|成立，也称函数g(n)以f(n)为界或者称g(n)囿于f(n)。记作g(n)=O(f(n))。 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
3.分治法的基本思想是什么
分治法的基本思想是：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
4.回溯算法的基本思想及其一般模式（子集树+排列树）
基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
搜索子集树的一般模式：
void search(int m) {
if(m>n) //递归结束条件
output(); //相应的处理(输出结果) else {
a[m]=0; //设置状态：0表示不要该物品 search(m+1); //递归搜索：继续确定下一个物品 a[m]=1; //设置状态：1表示要该物品
search(m+1); //递归搜索：继续确定下一个物品 } }
搜索排列树的一般模式：
void search(int m) {
if(m>n) //递归结束条件
output(); //相应的处理(输出结果) else
for(i=m;i<=n;i++) {
swap(m,i); //交换a[m]和a[i] if()
if(canplace(m)) //如果m处可放置 search(m+1); //搜索下一层
swap(m,i); //交换a[m]和a[i](换回来) } }
5.动态规划的基本思想、基本步骤、基本要素是什么
基本思想：将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
基本步骤：①找出最优解的性质，并刻画其结构特征； ②递归地定义最优值；
③以自底向上的方式计算出最优值；
④根据计算最优值时得到的信息，构造最优解。 基本要素：最优子结构性质和子问题重叠问题
6.什么是最优子结构性质和子问题重叠性质
最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，则称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
子问题重叠性质：指在用递归演算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
7.分治法与动态规划的联系与区别
联系：基本思想相同，即将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
区别：适用于动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。分治法子问题被重复计算多次，而动态规划子问题可用一个表来记录已解决子问题的答案，避免了子问题重复计算的问题。
8.动态规划的变形（备忘录方法）与动态规划的联系与区别
联系：都用表格保存已解决的子问题的答案
区别：备忘录方法的递归方式是自顶向下的，而动态规划的递归方式是自底向上的。
9.分支限界法（广度优先搜索）的基本思想是什么
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展节点。活结点一旦成为扩展节点，就一次性产生所有儿子节点。在这些儿子节点中，导致不可行解或导致非最优解的儿子节点被舍弃，其余儿子节点被加入活结点表中。此后，从活结点表中取下一节点成为当前扩展节点，并重复上述节点扩展过程，这个过程一直持续到找到所需的解或活结点表为空时为止。
10.分支限界法与回溯法的区别
1.搜索方式不同：分支限界法使用广度优先或最小消耗优先搜索，而回溯法使用深度优先搜索。
2.主要区别：在于它们对当前扩展节点所采用的扩展方式不同。 分支限界法：每个节点只有一次成为活结点的机会
回溯法：活结点的所有可行子节点被遍历后才被从栈中弹出
11.搜索算法的一般模式
搜索算法关键要解决好状态判重的问题：
void search() {
open表初始化为空; 起点加入到open表; while( open表非空 ) {
取open表中的一个结点u; 从open表中删除u;
for( 对扩展结点u得到的每个新结点vi ) {
if(vi是目标结点) 输出结果并返回; If(notused(vi)) vi进入open表; } }
}
12.贪心算法的基本思想、基本步骤及基本要素
基本思想：贪心算法总是做出在当前看来是最好的选择，即贪心算法并不从整体最优上加以考虑，所做的选择只是在某种意义上的局部最优选择，即贪心选择。
基本步骤：①从问题的某个初始解出发；
②采用循环语句，当可以向求解目标前进一步时，就根据局部最 优策略，得到一个局部最优解缩小问题的规模；
③将所有局部最优解综合起来，得到原问题的解。
基本要素：①贪心选择性质：指所求问题的整体最优解可以通过一系列的局
部最优的选择，即贪心选择来达到。贪心选择策略必须具备无后效 性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
②最优子结构性质：一个问题的最优解包含其子问题的最优解。
13.贪心算法与动态规划算法联系与区别
联系：都要求问题具有最优子结构性质，即一个问题的最优解包含其子问题的最优解。 区别：①在动态规划算法中，每步所做的选择往往是依赖于相关子问题的解，因而只有在解出相关子问题后，才能做出选择。而在贪心算法中，仅在当前状态下做出最好的选择，即局部最优选择，然后再去解做出这个选择后产生的相应的子问题。
②动态规划算法通常以自底向上方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式做出相机的贪心选择以简化问题规模。
二．设计题（60分---写出核心代码或伪代码和相关的变量声明） 1.用二分查找算法查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。
最直接的做法就是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏的情况下需要n次比较。一般来说，若没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况都需要n次比较。
考虑最简单的情况，该线性表为有序表，设其按照主键的递增顺序从小到大排列。 核心伪代码：function BinarySearch(L,a,b,x) begin
if a>b then return -1
else begin
m=(a+b)div 2;
if x=L[m] then return (m)
else if x>L[m]
then return BinarySearch(L,m+1,b,x);
else
return BinarySearch(L,a,m-1,x);
end; end;
2.请采用快速排序算法为下列数字排序，并写出最终结果（21 25 49 25* 16 08）
快速排序的基本思想:选定一个基准值元素，对带排序的序列进行分割，分割之后的序列一部分小于基准值元素，另一部分大于基准值元素，再对这两个分割好的子序列进行上述的过程。
void swap(int a,int b){int t;t =a ;a =b ;b =t ;} int Partition(int [] arr,int low,int high) {
int pivot=arr[low];//采用子序列的第一个元素作为基准元素 while (low < high) {
//从后往前在后半部分中寻找第一个小于基准元素的元素 while (low < high && arr[high] >= pivot) {
--high;
