下载文档原格式
一。
选择题1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ B ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（ A ）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（ B ）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（ B ）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题9. 实现循环赛日程表利用的算法是（ A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（ D ）。
A、广度优先B、最小耗费优先C、最大效益优先D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）15．分支限界法解最大团问题时，活结点表的组织形式是（ B ）。
A、最小堆B、最大堆C、栈D、数组16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
算法设计与分析试题A及答案一．填空题：（每题4分，共20分）1.算法是指（解决问题的）一种方法或一个过程，是（若干指令的）有穷序列。
2质。
3. 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择来达到。
4．递归函数的两大基本要素是_递归方程和边界条件_ .5．在回溯法中，一个问题的解空间是指一个大的解决方案可以看作是由若干个小的决策组成。
很多时候它们构成一个决策序列。
解决一个问题的所有可能的决策序列构成该问题的解空间.二．简答题：（每题5分，共20分）1.简述分治法所能解决的问题一般应具有的特征。
1.)该问题的规模缩小到一定的程度就可以容易地解决；2.)该问题具有最优子结构性质；3.)利用该问题分解出的子问题的解可以合并为该问题的解；4.)该问题所分解出的各个子问题是相互独立的。
2．设有待安排的8个活动的开始时间和结束时间如下表。
请采用贪心算法给出活动安排序解：将待安排的8个活动的开始时间和结束时间按结束时间的非减序排列如下：用贪心算法给出活动安排序列：1，3，6，8。
贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
3．请描述分治法的具体过程。
将原问题划分成k 个子问题。
对这k 个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
4. Fibonacci 数列如下定义：10()11(1)(2)1n F n n F n F n n =⎧⎪==⎨⎪-+->⎩1、 请设计一个递归算法，计算F(n)。
2、 分析算法的时间复杂性。
解 1、int fibonacci(int n) { if (n <= 1) return 1;return fibonacci(n-1)+fibonacci(n-2); }2、T(n)=T(n-1)+T(n-2)。
如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n))如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n>= N1，f （n）<=C1s(n)；对所有的n>= N2,g(n) <=C2r(n)所以 f（n）+ g(n) <= C1s(n)+ C2r(n)，f（n）*g(n)<= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1*C2；则：f（n）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))f（n）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n))试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。
一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即零次多项式)来限界，而一个时间为Ο(n2)的算法则由一个二次多项式来限界。
当数据集的规模（即n的取值）很大时，要在现代计算机上运行具有比O（nlog2 n）复杂度还高的算法是很困难的，尤其是指数时间算法，它只有在在n值取得非常小的时候才实用。
例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n^2和nlogn.则N=1024，分别需要1048576和10240次运算。
N=2048：分别需要4194304和22528次运算。
由此，在n加倍的情况下，一个O（n^2)的算法计算时间增长4倍，而一个O（nlogn）算法则只用两倍多一点的时间。
所以数量级的大小对算法的有效性有决定性的影响。
尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n足够大时，n每增加1，1000倍的提速即可瞬间化为乌有。
计算机算法设计五⼤常⽤算法的分析及实例摘要算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。
也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。
如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。
不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。
其中最常见的五中基本算法是递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法。
本⽂通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识关键词：算法，递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法AbstractAlgorithm is the description to the problem solving scheme ,a set of clear instructions to solve the problem and represents the describe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirm import，the Algorithm will find result In a limited time。
If an algorithm is defective or is not suitable for a certain job, it is invalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedy algorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, make readers know more about algorithm , and understand the five algorithms more deeply.Keywords: Algorithm, the recursive and divide and conquer, dynamic programming method, greedy algorithm、backtracking, branch and bound method⽬录1. 前⾔ (4)1.1 论⽂背景 (4)2. 算法详解 (5)2.1 算法与程序 (5)2.2 表达算法的抽象机制 (5)2.3 算法复杂性分析 (5)3．五中常⽤算法的详解及实例 (6)3.1 递归与分治策略 (6)3.1.1 递归与分治策略基本思想 (6)3.1.2 实例——棋盘覆盖 (7)3.2 动态规划 (8)3.2.1 动态规划基本思想 (8)3.2.2 动态规划算法的基本步骤 (9)3.2.3 实例——矩阵连乘 (9)3.3 贪⼼算法 (11)3.3.1 贪⼼算法基本思想 (11)3.3.2 贪⼼算法和动态规划的区别 (12)3.3.3 ⽤贪⼼算法解背包问题的基本步骤： (12)3.4 回溯发 (13)3.4.1 回溯法基本思想 (13)3.3.2 回溯发解题基本步骤 (13)3.3.3 实例——0-1背包问题 (14)3.5 分⽀限界法 (15)3.5.1 分⽀限界法思想 (15)3.5.2 实例——装载问题 (16)总结 (18)参考⽂献 (18)1. 前⾔1.1 论⽂背景算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。
分治法1、二分搜索算法是利用（分治策略）实现的算法。
9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略）。
实现大整数的乘法是利用的算法（分治策略）。
17．实现棋盘覆盖算法利用的算法是（分治法）。
29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。
不可以使用分治法求解的是（0/1背包问题）。
动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。
下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。
（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。
矩阵连乘问题的算法可由（动态规划算法B）设计实现。
实现最大子段和利用的算法是（动态规划法）。
贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。
回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。
分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。
分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
一、选择题1、衡量一个算法好坏的标准是（ ）。
（A ）运行速度快 （B ）占用空间少 (C ）时间复杂度低 （D ）代码短2、函数n n 1032 的渐进表达式是( ）。
（A ）O （23n ） （B)O （3) （C ）O （n 10） （D ）O(2n ）3、以下不可以使用分治法求解的是（ )。
（A ）棋盘覆盖问题 (B ）选择问题 (C ）归并排序 （D) 0/1背包问题4、二分搜索算法是利用( ）实现的算法。
（A)分治策略 （B ）动态规划法 （C)贪心法 （D ）回溯法5、二分搜索算法的时间复杂性为( ）。
（A ）O(2n ） (B ）O （n ) （C ）O （n log ) （D)O （n n log ）6、快速排序算法的时间复杂性为（ ）。
（A ）O （2n ） (B)O （n ） (C ）O(n log ） （D)O(n n log ）7、实现大整数的乘法是利用（ ）的算法.（A ）分治策略 (B)动态规划法 （C)贪心法 （D ）回溯法8、矩阵连乘问题的算法可由（ )设计实现。
（A ）分支界限算法 （B)动态规划算法 （C)贪心算法 (D ）回溯算法9、实现循环赛日程表利用的算法是（ ）。
（A ）分治策略 （B ）动态规划法 （C ）贪心法(D ）回溯法10、下列是动态规划算法基本要素的是（ ）.（A ）定义最优解 （B ）构造最优解 （C ）算出最优解 (D ）子问题重叠性质11、最长公共子序列算法利用的算法是( ）。
(A ）分治法 (B ）动态规划法 （C ）贪心法 （D)回溯法12、下列算法中通常以自底向上的方式求解最优解的是（ ）。
（A)备忘录法 (B ）动态规划法 （C ）贪心法 （D ）回溯法13、以下不可以使用分治法求解的是( ).(A)棋盘覆盖问题 (B ）选择问题 （C ）归并排序 (D ）0/1背包问题14、下列算法中不能解决0/1背包问题的是（ ）（A)贪心法 （B ）动态规划 （C)回溯法 （D)分支限界法15、算法是由若干条指令组成的有穷序列,而且满足以下性质（ ）（A ）输入：有0个或多个输入 （B)输出：至少有一个输出（C ）确定性：指令清晰,无歧义 （D)有限性:指令执行次数有限，而且执行时间有限A (1）（2)(3)B （1）（2)（4）C （1）(3）（4）D （1） (2）（3）（4)16、函数32n +10nlog n 的渐进表达式是( ).A. 2n B 。
算法是满足下述性质的指令序列输入：有零个或多个外部量作为算法的输入。
输出：算法产生至少一个量作为输出。
确定性：组成算法的每条指令清晰、无歧义。
有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限抽象数据类型带给算法设计的好处有:（1）算法顶层设计与底层实现分离；（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。
O的定义：如果存在正的常数C和自然数N0，使得当N≥N0时有f(N)≤Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N))。
即f(N)的阶不高于g(N)的阶。
根据O的定义，容易证明它有如下运算规则：(1)O(f)+O(g)=O(max(f,g))；(2)O(f)+O(g)=O(f+g)；(3)O(f)O(g)=O(fg)；第二章：递归和分治法直接或间接地条用自身的算法称为递归算法。
用函数自身给出的定义的函数称为递归函数。
分治法基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。
1、二分搜索技术(时间复杂度O（logn）)Public static int binarysearch(int []a,intx,int n){// 在a[0] <= a[1] <= ... <= a[n-1] 中搜索x// 找到x时返回其在数组中的位置，否则返回-1int left=0;right=n-1;while(left<=right){int middle=(left+right)/2;if(x==a[middle])return middle;if(x>a[middle])left=middle+1;else right=middle-1;}return -1; // 未找到x}2、棋盘覆盖（复杂O（4的k字方））public void chessBoard(int tr, int tc, int dr, int dc, int size){if (size == 1) return;int t = tile++, // L型骨牌号s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr < tr + s && dc < tc + s)// 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else {// 此棋盘中无特殊方格// 用t 号L型骨牌覆盖右下角board[tr + s - 1][tc + s - 1] = t;// 覆盖其余方格chessBoard(tr, tc, tr+s-1, tc+s-1, s);}// 覆盖右上角子棋盘3、合并排序（时间复杂度O（logn））public static void mergeSort(Comparable a[], int left, int right){if (left<right) {//至少有2个元素int i=(left+right)/2; //取中点mergeSort(a, left, i);mergeSort(a, i+1, right);merge(a, b, left, i, right); //合并到数组bcopy(a, b, left, right); //复制回数组a}}第三章：动态规划动态规划步骤：①找出最优解的性质，并刻划其结构特征②递归地定义最优值。
③以自底向上的方式计算出最优值。
④根据计算最优值时得到的信息，构造最优解。
1、矩阵连乘矩阵连乘的特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。
矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
public static void matrixChain(int [] p, int [][]m, int [][] s){int n=p.length-1;for (int i = 1; i <= n; i++) m[i][i] = 0;for (int r = 2; r <= n; r++)for (int i = 1; i <= n - r+1; i++) {int j=i+r-1;m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];s[i][j] = i;for (int k = i+1; k < j; k++) {int t = m[i][k] + m[k+1][j] +p[i-1]*p[k]*p[j];if (t < m[i][j]) {m[i][j] = t;s[i][j] = k;} }}}算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。
循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。
因此算法的计算时间上界为O(n3)。
算法所占用的空间显然为O(n2)。
2、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。
m⇓0private static int lookupChain(int i, int j){if (m[i][j] > 0) return m[i][j];if (i == j) return 0;int u=lookupChain(i+1,j) + p[i-1]*p[i]*p[j];s[i][j] = i;for (int k = i+1; k < j; k++) {int t=lookupChain(i,k) + lookupChain(k+1,j)+ p[i-1]*p[k]*p[j];if (t < u) {u = t; s[i][j] = k;}}m[i][j] = u;return u;}3、最长公共子序列Algorithm lcsLength(x,y,b)1: m⇓x.length-1;2: n⇓y.length-1;3: c[i][0]=0; c[0][i]=0;4: for (int i = 1; i <= m; i++)5: for (int j = 1; j <= n; j++)6: if (x[i]==y[j])7: c[i][j]=c[i-1][j-1]+1;8: b[i][j]=1;9: else if (c[i-1][j]>=c[i][j-1])10: c[i][j]=c[i-1][j];11: b[i][j]=2;12: else13: c[i][j]=c[i][j-1];14: b[i][j]=3;构造最长公共子序列Algorithm lcs(int i,int j,char [] x,int [][] b){if (i ==0 || j==0) return;if (b[i][j]== 1){lcs(i-1,j-1,x,b);System.out.print(x[i]); }else if (b[i][j]== 2) lcs(i-1,j,x,b);else lcs(i,j-1,x,b); }算法改进：在算法lcsLength和lcs中，可进一步将数组b省去。
事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定。
对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的。
如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。
事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。
因此，用2行的数组空间就可以计算出最长公共子序列的长度。
进一步的分析还可将空间需求减至O(min(m,n))。
第四章、贪心算法贪心算法要素：贪心选择性质和最优子结构性质。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
1、在下面所给出的解活动安排问题的贪心算法greedySelector :•public static int greedySelector(int []s, int [] f, boolean a[])•{int n=s.length-1;•a[1]=true;•int j=1;•int count=1;•for (int i=2;i<=n;i++) {•if (s[i]>=f[j]) {•a[i]=true;•j=i;•count++;}•else a[i]=false;•}return count;}算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。
因此，算法的计算时间上界为O（nlogn）。
当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。
2、最优装载（算法所需的计算时间为O(nlogn)public static float loading(float c, float []w, int [] x){int n=w.length;Element [] d = new Element [n];for (int i = 0; i < n; i++)d[i] = new Element(w[i],i);MergeSort.mergeSort(d);float opt=0;for (int i = 0; i < n; i++) x[i] = 0;for (int i = 0; i < n && d[i].w <= c; i++){x[d[i].i] = 1;opt+=d[i].w;c -= d[i].w;}return opt;}3、哈弗曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
