一、简要回答下列问题 ：
1. 算法重要特性是什么？ 2. 算法分析的目的是什么？
3. 算法的时间复杂性与问题的什么因素相关？ 4. 算法的渐进时间复杂性的含义？
5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 6. 简述二分检索（折半查找）算法的基本过程。
7. 背包问题的目标函数和贪心算法最优化量度相同吗？ 8. 采用回溯法求解的问题，其解如何表示？有什么规定？ 9. 回溯法的搜索特点是什么？
10. n皇后问题回溯算法的判别函数place的基本流程是什么？ 11. 为什么用分治法设计的算法一般有递归调用？ 12. 为什么要分析最坏情况下的算法时间复杂性？ 13. 简述渐进时间复杂性上界的定义。 14. 二分检索算法最多的比较次数？
15. 快速排序算法最坏情况下需要多少次比较运算？ 16. 贪心算法的基本思想？
17. 回溯法的解（x1,x2,……xn）的隐约束一般指什么？ 18. 阐述归并排序的分治思路。
19. 快速排序的基本思想是什么。
20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 21. 什么是哈密顿环问题？
22. 用回溯法求解哈密顿环，如何定义判定函数？ 23. 请写出prim算法的基本思想。
二、复杂性分析
1、 MERGESORT(low，high) if low endif end MERGESORT 2、 procedure S1(P，W，M，X，n) i←1; a←0 while i≤ n do if W(i)>M then return endif a←a+i i←i+1 ; repeat end 3.procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) v←A(m);i←m loop loop i←i+1 until A(i) ≥v repeat loop p←p-1 until A(p) ≤v repeat if i then call INTERCHANGE(A(i),A(p)) else exit endif repeat A(m) ←A(p);A(p) ←v End PARTITION 4.procedure F1(n) if n<2 then return(1) else return(F2(2,n,1,1)) endif end F1 procedure F2(i,n,x,y) if i≤n then call F2(i+1,n,y,x+y) endif return(y) end F2 5.procedure MAX(A,n,j) xmax←A(1);j←1 for i←2 to n do if A(i)>xmax then xmax←A(i); j←i;endif repeat end MAX 6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low←1;high←n while low≤high do mid←|_(low+high)/2_| case :x :x>A(mid):low←mid+1 :else:j←mid; return endcase repeat j←0 end BINSRCH 三、算法理解 1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 2 5 1 3 6 8 4 7 各边的代价如下： C(1,2)=3， C(1,3)=5 ，C(1,4)=2 C(2,6)=8 ，C(2,7)=4 ，C(3,5)=5 ，C(3,6)=4， C(4,5)=2，C(4,6)=1 C(5,8)=4， C(6,8)=5 ，C(7,8)=6 2、 写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=(48,12,61,3,5,19,32,7) 3、 给出5个数(3,6,9,1,7),M=13，用递归树描述sumofsub算法求和数=M的一个子集 的过程。 4、 快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2) 5、 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7) 6、 写出图着色问题的回溯算法的判断X[k]是否合理的过程。 7、 对于下图，写出图着色算法得出一种着色方案的过程。 2 3 1 4 8、 写出第7题的状态空间树。 9、 写出归并排序算法对下列实例排序的过程。 (6,2,9,3,5,1,8,7) 10、 写出用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) W=(12,10,8,3) M=25 11、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。 12、使用prim算法构造出如下图G的一棵最小生成树。 1 2 3 4 5 6 dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 13、有如下函数说明 int f(int x,int y) { f=x Mod y +1; } 已知a=10,b=4,c=5 则执行k=f(f(a+c,b),f(b,c))后，k的值是多少并写出详细过程。 14、McCathy函数定义如下： 当x>100时 m(x)=x-10; 当x<=100时 m(x)=m(m(x+11)); 编写一个递归函数计算给定x的m(x)值。 15、 设计一个算法在一个向量A中找出最大数和最小数的元素。 四、设计算法 1. 设有n项独立的作业{1,2,…, n},由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。 多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。 2. 设有n种面值为: d1≥d2≥……≥dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足 d1×Xi＋……dn×Xn?M ，使得 Xi＋……Xn 最小 请选择贪心策略，并设计贪心算法。 3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获 最优解。 4. 设计只求一个哈密顿环的回溯算法。 5．利用对称性设计算法，求n为偶数的皇后问题所有解。 参考答案 一、简要回答下列问题 ： 1. 确定性、可实现性、输入、输出、有穷性 2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2] 7. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。 8. 问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i 9. 在解空间树上跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。 10. 将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。 11 . 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。 12 最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。 13 .T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n) 14 .二分检索算法的最多的比较次数为 log n 。 2 15．.最坏情况下快速排序退化成冒泡排序，需要比较n次。 16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 17．回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。 18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。 19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终
算法分析与设计考试复习题及参考答案讲课讲稿
