《算法分析与设计》期末试题及参考答案.doc
《《算法分析与设计》期末试题及参考答案.doc》由会员分享,可在线阅读,更多相关《《算法分析与设计》期末试题及参考答案.doc(14页珍藏版)》请在装配图网上搜索。
算法分析与设计期末试题及参考答案一、简要回答下列问题 :1. 算法重要特性是什么? 1. 确定性、可行性、输入、输出、有穷性2.2. 算法分析的目的是什么?2. 分析算法占用计算机资源的情况,对算法做出比较和评价,设计出额更好的算法。3.3. 算法的时间复杂性与问题的什么因素相关?3. 算法的时间复杂性与问题的规模相关,是问题大小n的函数。4. 算法的渐进时间复杂性的含义?4当问题的规模n趋向无穷大时,影响算法效率的重要因素是T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同?5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时,不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度:W(n) = max T(n,I) , IDn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和:A(n) =P(I)T(n,I) IDn6. 简述二分检索(折半查找)算法的基本过程。6. 设输入是一个按非降次序排列的元素表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. 背包问题的目标函数和贪心算法最优化量度相同吗?7. 不相同。目标函数:获得最大利润。最优量度:最大利润/重量比。8. 采用回溯法求解的问题,其解如何表示?有什么规定?8. 问题的解可以表示为n元组:(x1,x2,xn),xiSi, Si为有穷集合,xiSi, (x1,x2,xn)具备完备性,即(x1,x2,xn)是合理的,则(x1,x2,xi)(in)一定合理。9. 回溯法的搜索特点是什么? 9. 在解空间树上跳跃式地深度优先搜索,即用判定函数考察xk的取值,如果xk是合理的就搜索xk为根节点的子树,如果xk取完了所有的值,便回溯到xk-1。10. n皇后问题回溯算法的判别函数place的基本流程是什么?10. 将第K行的皇后分别与前k-1行的皇后比较,看是否与它们相容,如果不相容就返回false,测试完毕则返回true。11. 为什么用分治法设计的算法一般有递归调用?11 . 子问题的规模还很大时,必须继续使用分治法,反复分治,必然要用到递归。12. 为什么要分析最坏情况下的算法时间复杂性? 、12 最坏情况下的时间复杂性决定算法的优劣,并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。 13. 简述渐进时间复杂性上界的定义。13 .T(n)是某算法的时间复杂性函数,f(n)是一简单函数,存在正整数No和C,nNo,有T(n)f(n),这种关系记作T(n)=O(f(n)。14. 二分检索算法最多的比较次数?14 .二分检索算法的最多的比较次数为 log n 。15. 快速排序算法最坏情况下需要多少次比较运算?15.最坏情况下快速排序退化成冒泡排序,需要比较n2次。16. 贪心算法的基本思想?16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是:首先根据题意,选取一种量度标准;然后按这种量度标准对这n个输入排序,依次选择输入量加入部分解中。如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。17. 回溯法的解(x1,x2,xn)的隐约束一般指什么?17回溯法的解(x1,x2,xn)的隐约束一般指个元素之间应满足的某种关系。 18. 阐述归并排序的分治思路。18. 讲数组一分为二,分别对每个集合单独排序,然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大,则继续分治,直到一个元素。19. 快速排序的基本思想是什么。 19.快速排序的基本思想是在待排序的N个记录中任意取一个记录,把该记录放在最终位置后,数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分,所有比它大的放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一次快速排序。之后重复上述过程,直到每一部分内只有一个记录为止。 20. 什么是直接递归和间接递归?消除递归一般要用到什么数据结构?20.在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分,既调用它自己本身,这称为直接递归。如果过程或者函数P调用过程或者函数Q,Q又调用P,这个称为间接递归。消除递归一般要用到栈这种数据结构。21. 什么是哈密顿环问题?21. 哈密顿环是指一条沿着图G的N条边环行的路径,它的访问每个节点一次并且返回它的开始位置。22. 用回溯法求解哈密顿环,如何定义判定函数?22.当前选择的节点Xk是从未到过的节点,即XkXi(i=1,2,k-1),且C(Xk-1, Xk),如果k=-1,则C(Xk, X1) 。23. 请写出prim算法的基本思想。23. 思路是:最初生成树T为空,依次向内加入与树有最小邻接边的n-1条边。处理过程:首先加入最小代价的一条边到T,根据各节点到T的邻接边排序,选择最小边加入,新边加入后,修改由于新边所改变的邻接边排序,再选择下一条边加入,直至加入n-1条边。二、复杂性分析1、 MERGESORT(low,high) if lowM then return endif aa+i ii+1 ; repeat end 解:3.procedure PARTITION(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) v End PARTITION 3解:、最多的查找次数是p-m+1次 4.procedure F1(n) if n1时F1(n)的时间复杂度与F2(2,n,1,1)的时间复杂度相同即为为 O(n) 5.procedure MAX(A,n,j) xmaxA(1);j1 for i2 to n do if A(i)xmax then xmaxA(i); ji;endif repeatend MAX答案 5、 xmaxA(1);j1 时间为:O(1) for i2 to n do 循环最多n-1次 所以 总时间为:T(n)=O(1)+ (n-1)O(1)= O(n)6.procedure BINSRCH(A,n,x,j) integer 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答案 6、log2n+1三、算法理解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 ,C(7,8)=6答案: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(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=(48,12,61,3,5,19,32,7) 答案 2、 写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=() 1、 48,12,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=13,用递归树描述sumofsub算法求和数=M的一个子集的过程。4、 快速排序算法对下列实例排序,算法执行过程中,写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2)5、 归并排序算法对下列实例排序,写出算法执行过程。 A=(48,12,61,3,5,19,32,7)5、 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、 写出图着色问题的回溯算法的判断Xk是否合理的过程。6、i0while ik do if Gk,i=1 and Xk= Xi then return false ii+1repeat if i= k then return true7、 对于下图,写出图着色算法得出一种着色方案的过程。2314 7、K1X1 1 , 返回 trueX21,返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回false;X4X4+1=3, 返回 true找到一个解 (1,2,3,3)8、 写出第7题的状态空间树。9、 写出归并排序算法对下列实例排序的过程。(6,2,9,3,5,1,8,7)9、 调用第一层次 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, 8,9 排序结束,返回主函数10、 写出用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) W=(12,10,8,3) M=2510、实例符合P(i)/W(i)P(i+1)/W(i+1)的顺序。 CU25,X0 W1 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、使用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;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的值是多少并写出详细过程。 K的值是514、McCathy函数定义如下:当x100时 m(x)=x-10;当x100) return(x-100);else y=m(x+11); return (m(y); 15、 设计一个算法在一个向量A中找出最大数和最小数的元素。解Void maxmin(A,n)Vector A;int n;int max,min,i; max=A0;min=A0;for(i=0;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 4. 设计只求一个哈密顿环的回溯算法。Hamiltonian(n)k1; xk 0; While k0 do xk xk+1; while B(k)=false and xkn do xk 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) do 2) 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- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法分析与设计 算法 分析 设计 期末 试题 参考答案
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文