《《算法分析与设计》期末试题及参考答案》由会员分享，可在线阅读，更多相关《《算法分析与设计》期末试题及参考答案（14页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计期末试题及参考答案、简要回答下列问题 ：1. 算法重要特性是什么？1. 确定性、可行性、输入、输出、有穷性2.2. 算法分析的目的是什么？2. 分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。3.3. 算法的时间复杂性与问题的什么因素相关？3. 算法的时间复杂性与问题的规模相关，是问题大小 n 的函数。4. 算法的渐进时间复杂性的含义？4当问题的规模 n 趋向无穷大时，影响算法效率的重要因素是T(n) 的数量级，而其他因素仅是使时间复杂度相差常数倍， 因此可以用 T(n) 的数量级 (阶)评价算法。 时间复杂 度 T(n) 的数量级 ( 阶 ) 称为渐进时
2、间复杂性。5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？5. 最坏情况下的时间复杂性和平均时间复杂性考察的是 n 固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n , I) , I Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=刀 P(I)T(n ,1) I Dn6. 简述二分检索(折半查找)算法的基本过程。6. 设输入是一个按非降次序排列的元素表Ai : j和x,选取A(i+j)/2 与x比较，如果 A(i+j)/2=x ,则返回 (i+j)/2 ,如果 A(i+j)/2x ,则 A
3、i ： (i+j)/2-1 找 x, 否则在A (i+j)/2+1: j找x。上述过程被反复递归调用。7. 背包问题的目标函数和贪心算法最优化量度相同吗？7. 不相同。目标函数：获得最大利润。最优量度：最大利润 /重量比。8. 采用回溯法求解的问题,其解如何表示？有什么规定？8. 问题的解可以表示为 n 元组：( x 1,x 2,xn), xiSi, S i 为有穷集合,xiSi,(X1,X2,”Xn)具备完备性，即(xi,x2,Xn)是合理的，则(xi,X2,”xj(in)定合理。9. 回溯法的搜索特点是什么？9. 在解空间树上跳跃式地深度优先搜索,即用判定函数考察xk 的取值,如果 xk是
4、合理的就搜索 xk 为根节点的子树,如果 xk 取完了所有的值,便回溯到 xk-1 。10. n 皇后问题回溯算法的判别函数 place 的基本流程是什么？10. 将第 K 行的皇后分别与前 k-1 行的皇后比较， 看是否与它们相容， 如果不相容就返 回 false ，测试完毕则返回 true 。11. 为什么用分治法设计的算法一般有递归调用？11 . 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。12. 为什么要分析最坏情况下的算法时间复杂性？ 、12 最坏情况下的时间复杂性决定算法的优劣， 并且最坏情况下的时间复杂性较平均时 间复杂性游可操作性。13. 简述渐进时间复
5、杂性上界的定义。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 个输入排序， 依次选择输入量加入部分解中。 如果当前这
6、个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。17. 回溯法的解( x1,x 2, , xn )的隐约束一般指什么？17回溯法的解(X1,X2, , Xn)的隐约束一般指个元素之间应满足的某种关系。18. 阐述归并排序的分治思路。18. 讲数组一分为二， 分别对每个集合单独排序， 然后将已排序的两个序列归并成一个 含 n 个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。19. 快速排序的基本思想是什么。19. 快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后， 数据序列被此记录分成两部分。 所有关键字比该记录关键字小的放在前一
7、部分， 所 有比它大的放置在后一部分， 并把该记录排在这两部分的中间， 这个过程称作一次快速排序。 之后重复上述过程，直到每一部分内只有一个记录为止。20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？20. 在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数 Q, Q又调用P,这个称为间接递归。消除递归一般要用到栈这种数据结构。21. 什么是哈密顿环问题？21. 哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。22. 用回溯法求解哈密顿环，如何定义判定函数？22
8、. 当前选择的节点 Xk是从未到过的节点，即Xk丰Xi(i=1,2, ,k-1)，且C(Xk-1, Xk) ms,如果 k=-1，贝y C(Xk, X1)工。23. 请写出prim算法的基本思想。23. 思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T,根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。二、复杂性分析1、MERGESORT(lo,high)if lowhigh ;then midJ (low , high)/2 ;MERGESORT(low ,
9、 mid);MERGESORT(mid+1 , high);MERGE(low , mid, high);en dif二、复杂性分析end MERGESORTT(ri) = 2(2T(n / 4)+绅 / 2)十绅=4T(n 4) + 2cn解递归方程:2、procedure S1(P,W M X , n)i J1; a J 0while i M then return endif a j a+i i j i+1 ;repeat endi*-1 : sO 时间为：0 (1) vhile i,W n do 循环 n 次 循环体内所用时间为0(1) 所以总时间为：T(n)=0(l)+ 边二 0(n
10、)3. procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)v jA(m);i j mlooploop i j i+1 un til A(i) v repeatloop p j p-1 until A(p)w v repeatif ipthe n call INTERCHANGE(A(i),A(p)else exiten difrepeatA(m)j A(p);A(p)j vEnd PARTITION3解：、最多的查找次数是 p-m+1次4. procedure F1( n)if n1时F1(n)的时间复杂度与 F2(2,n,1,1)的时间
11、复杂度相同即为为5. procedure MAX(A, n,j)xmaxj A(1);j j 1for ij 2 to n doif A(i)xmax the n xmax repeat end MAX答案5 、xmaxj A(1);j J1for ij 2 to n do所以总时间为：T( n)=0(1)+ (n-1)0(1)= O( n)J A(i); jj i;e ndif时间为：0(1)循环最多n-1次6. procedure BINSRCH(A, n,x,j)in teger low,high,mid,j, n;low j 1;high j n while low high domi
12、dj |_(low+high)/2 case:xA(mid):low j mid+1:else:jj mid; returnendcaserepeatj J 0end BINSRCH答案6 、log 2n+1三、算法理解C(1,2)=3， C(1,3)=5C(2,6)=8，C(2,7)=4C(5,8)=4， C(6,8)=5 答案：，C(1,4)=2，C(3,5)=5，C(3,6)=4， C(4,5)=2 ，C(4,6)=1，C(7,8)=61、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。1、Cost(4,8)=0Cost(3,7)= C(7,8)+0=6, D5=8Cos
13、t(3,6)= C(6, 8)+0=5, D6=8Cost(3,5)= C(5,8)+0=4 D7=8,5)+ Cost(3,5),7)+ Cost(3,7)Cost(2,4)= minC(4, 6)+ Cost(3,6), C(4=mi n1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3, 6)+ Cost(3,6) =mi n4+5=9 D3=5Cost(2,2)= minC(2, 6)+ Cost(3,6), C(2=min 8+5, 4+6=10 D2=7Cost(1,1)= mi nC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,
14、4)+ Cost(2,4)=min 3+10, 5+9,2+6= 8D1=41 t82、写出maxmin算法对下列实例中找最大数和最小数的过程。数组 A=(48,12,61,3,5,19,32,7)答案2、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48 61, 12 3 19 32, 5 74、61 32355、61 33、给出5个数(3,6,9,1,7),M=13 ，用递归树描述 sumofsub算法求和数=M的一个子集 的过程。3、 给岀5个數V, 6亂1, 7)=12用速归树揃
