算法分析与设计考试复习题及参考复习资料.docx

《算法分析与设计考试复习题及参考复习资料.docx》由会员分享，可在线阅读，更多相关《算法分析与设计考试复习题及参考复习资料.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、简要答复下列问题 ：1. 算法重要特性是什么？ 2. 算法分析的目的是什么？3. 算法的时间困难性及问题的什么因素相关？4. 算法的渐进时间困难性的含义？5. 最坏状况下的时间困难性和平均时间困难性有什么不同？6. 简述二分检索（折半查找）算法的根本过程。7. 背包问题的目的函数和贪心算法最优化量度一样吗？8. 采纳回溯法求解的问题，其解如何表示？有什么规定？9. 回溯法的搜寻特点是什么？ 10. n皇后问题回溯算法的判别函数place的根本流程是什么？11. 为什么用分治法设计的算法一般有递归调用？12. 为什么要分析最坏状况下的算法时间困难性？ 13. 简述渐进时间困难性上界的定义。1

2、4. 二分检索算法最多的比拟次数？15. 快速排序算法最坏状况下须要多少次比拟运算？16. 贪心算法的根本思想？17. 回溯法的解（x1,x2,xn）的隐隐束一般指什么？18. 阐述归并排序的分治思路。19. 快速排序的根本思想是什么。20. 什么是干脆递归和间接递归？消退递归一般要用到什么数据构造？21. 什么是哈密顿环问题？22. 用回溯法求解哈密顿环，如何定义断定函数？23. 请写出prim算法的根本思想。二、困难性分析1、 MERGESORT(low，high) if lowM then return endif aa+i ii+1 ; repeat end 3.procedure P

3、ARTITION(m,p)Integer m,p,i;global A(m:p-1) vA(m);im looploop ii+1 until A(i) v repeatloop pp-1 until A(p) v repeat if ip then call INTERCHANGE(A(i),A(p) else exit endif repeat A(m) A(p);A(p) vEnd PARTITION 4.procedure F1(n)if nxmax then xmaxA(i); ji;endif repeatend MAX6.procedure BINSRCH(A,n,x,j) in

4、teger low,high,mid,j,n; low1;highn while lowhigh do mid|_(low+high)/2_|case :xA(mid):lowmid+1:else:jmid; return endcase repeat j0 end BINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。52863174各边的代价如下：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)=1C(5,8)=4， C(6,8)=

5、5 ，C(7,8)=62、 写出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、 写出图着色问题的回溯算法的推断Xk是否合理的过程。7、 对于下图，写出图着色算法得出一种着色方案的过程。23

6、148、 写出第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的一棵最小生成树。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1

7、;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函数说明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函数定义如下：当x100时 m(x)=x-10;当x=100时 m(x)=m(m(x+11);编写一个递归函数计算给定x的m(x)值。15、 设计一个算法在一个向量A中找出最大数和最小数的元素。四、设计算法 1.设有n项独立的作业1,2, n,由m台一样的机器加工处理。作业i所须要的处理时间为t

8、i。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并探讨是否可获最优解。2. 设有n种面值为:d1d2dn的钱币，须要找零钱M，如何选择钱币dk，的数目Xk，满意 d1XidnXn=M ，使得XiXn 最小 请选择贪心策略，并设计贪心算法。3.有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包涵积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并探讨是否可获最优解。4.

9、 设计只求一个哈密顿环的回溯算法。5利用对称性设计算法，求n为偶数的皇后问题全部解。参考答案一、简要答复下列问题 ：1. 确定性、可实现性、输入、输出、有穷性2. 分析算法占用计算机资源的状况，对算法做出比拟和评价，设计出额更好的算法。3. 算法的时间困难性及问题的规模相关，是问题大小n的函数。4当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间困难度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间困难度T(n)的数量级(阶)称为渐进时间困难性。5. 最坏状况下的时间困难性和平均时间困难性考察的是n固定时，不同输入实例下的算法所耗时间。最坏状况

10、下的时间困难性取的输入实例中最大的时间困难度：W(n) = max T(n，I) , IDn平均时间困难性是全部输入实例的处理时间及各自概率的乘积和：A(n) =P(I)T(n，I) IDn6. 设输入是一个按非降次序排列的元素表Ai：j 和x，选取A(i+j)/2及x比拟，假如A(i+j)/2=x，则返回(i+j)/2，假如A(i+j)/2x，则Ai：(i+j)/2-1找x，否则在A (i+j)/2+1：j 找x。上述过程被反复递归调用。回溯法的搜寻特点是什么7. 不一样。目的函数：获得最大利润。最优量度：最大利润/重量比。8. 问题的解可以表示为n元组：（x1,x2,xn），xiSi, S

11、i为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（x1,x2,xi）(in)肯定合理。9. 在解空间树上跳动式地深度优先搜寻，即用断定函数考察xk的取值，假如xk是合理的就搜寻xk为根节点的子树，假如xk取完了全部的值，便回溯到xk-1。10. 将第K行的皇后分别及前k-1行的皇后比拟，看是否及它们相容，假如不相容就返回false，测试完毕则返回true。11. 子问题的规模还很大时，必需接着运用分治法，反复分治，必定要用到递归。12 最坏状况下的时间困难性确定算法的优劣，并且最坏状况下的时间困难性较平均时间困难性游可操作性。 13 .T(n)是某算

12、法的时间困难性函数，f(n)是一简洁函数，存在正整数No和C，nNo，有T(n)1时F1(n)的时间困难度及F2(2,n,1,1)的时间困难度一样即为为 O(n) 5、 xmaxA(1);j1 时间为：O(1) for i2 to n do 循环最多n-1次 所以 总时间为:T(n)=O(1)+ (n-1)O(1)= O(n) 6、log2n+1三、算法理解1、 Cost(4,8)=0Cost(3,7)= C(7,8)+0=6 ，D5=8Cost(3,6)= C(6，8)+0=5, D6=8Cost(3,5)= C(5，8)+0=4 D7=8Cost(2,4)=minC(4，6)+ Cost(

13、3,6), C(4，5)+ Cost(3,5) =min1+5,2+4=6 D4=6Cost(2,3)=minC(3，6)+ Cost(3,6) =min4+5=9 D3=5Cost(2,2)=minC(2，6)+ Cost(3,6), C(2，7)+ Cost(3,7) =min8+5,4+6=10 D2=7Cost(1,1)=minC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4) =min3+10,5+9,2+6= 8D1=414682、 写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=() 1、 48,12,

14、61,3, 5,19,32,72、48,12 61,3 5,19 32,73、 4861, 123 1932，574、 6132 355、 61 33、 给出5个数(3,6,9,1,7),M=12，用递归树描绘sumofsub算法求和数=M的一个子集的过程。1，28，02，25，33，19，34，10，124、第一个分割元素为65(1) (2) (3) (4) (5) (6) (7) (8) i p65 70 75 80 85 55 50 2 2 865 2 75 80 85 55 50 70 3 765 2 50 80 85 55 75 70 4 665 2 50 55 85 80 75 7

15、0 4 655 70 75 80 85 65 50 25、 48,12,61,3 5,19,32,748,12 61,3 5,19 32,712,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,61 6、i0while ik do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return true 7、K1X11 , 返回 trueX21,返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2,返

16、回false;X3X3+1=3, 返回 trueX41,返回false; X4X4+1=2,返回false;X4X4+1=3, 返回 true找到一个解 （1，2，3，3）X1=1X2=2X3=33X4=339、 调用第一层次 6,2,9,3 5,1,8,7 分成两个子问题 调用第二层次 6,2 9,3 5,1 8,7 分成四个子问题 调用第三层次 6 2 9 3 5 1 8 7 分成八个子问题 调用第四层次 只有一个元素返回上一层第三层归并 2 ,6 3, 9 1,5 7,8 返回上一层第二层归并 2 ,3,6, 9 1,5,7,8 返回上一层第一层归并 1, 2 ,3, 5 ,6, 7,

17、8,9 排序完毕，返回主函数10、实例符合P(i)/W(i)P(i+1)/W(i+1)的依次。 CU25,X0W1 CU: x11; CUCU-W1=13;W2CU: x3CU/ W3=3/8;实例的解为：（1，1，3/8，0）11 有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当运用二分查找值为82的结点时，经过多少次比拟后查找胜利并给出过程。一共要要执行四次才能找到值为82的数。12运用普里姆算法构造出如下图G的一棵最小生成树。124356dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,

18、1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=61316136412645126343313.有如下函数说明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的值是多少并写出具体过程。 K的值是514.McCathy函数定义如下：当x100时 m(x)=x-10;当x100) return(x-100);elsey=m(x+11); return (m(y); 15 设计一个算法在一个向量A中找出最大数和最小数的元素。Voi

19、d maxmin(A,n)Vector A;int n;int max,min,i; max=A1;min=A1;for(i=2;imax)max=Ai;else if(Aicu then exit endif X(i) 1 cucu-W(i) repeat end GREEDY-KNAPSACK 根据算法得出的解： X=（1,1,1,1,1,0,0）获利润52， 而解（1,1,1,1, 0, 1,0）可获利润54 因此贪心法不肯定获得最优解。4 Hamiltonian(n)k1; xk 0; While k0 do xk xk+1; while B(k)=false and xkn do x

20、k xk+1; repeat If xkn then if k=n then print x; return else k k+1; xk0; endif else k k-1 endifrepeatendprocedure B(k) Gxk-1,xk 1 then return false; for i1 to k-1 do if xi=xk then return false;endif repeat return true; 5利用对称性设计算法，求n为偶数的皇后问题全部解。procedure NQUEENS1(n)a0 /计数器清零X(1)0；k1 /k是当前行；X(k)是当前列/While k0 do /对全部的行执行以下语句/1) X(k)X(k)+1 /移到下一列/While X(k)n and not PLACE(k) do2) X(k)X(k)十l if X(k)n then if k=n /then print(X)，aa+1 /找到一个解计数器a加1/ if a=n/2 then return / 找到n/2个解算法完毕 3) else kk+1；X(k)0； 4) else kk1 /回溯/end NQUEENS