《《算法分析与设计》期末试题及参考答案.doc》由会员分享，可在线阅读，更多相关《《算法分析与设计》期末试题及参考答案.doc（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计期末试题及参考答案算法分析与设计期末试题及参考答案一、简要回答下列问题 ：1. 算法重要特性是什么？2. 算法分析的目的是什么？3. 算法的时间复杂性与问题的什么因素相关？4. 算法的渐进时间复杂性的含义？5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？6. 简述二分检索（折半查找）算法的基本过程。7. 背包问题的目标函数和贪心算法最优化量度相同吗？8. 采用回溯法求解的问题，其解如何表示？有什么规定？9. 回溯法的搜索特点是什么？10. n皇后问题回溯算法的判别函数place的基本流程是什么？11. 为什么用分治法设计的算法一般有递归调用？12. 为什么要分析最坏情况下
2、的算法时间复杂性？13. 简述渐进时间复杂性上界的定义。14. 二分检索算法最多的比较次数？15. 快速排序算法最坏情况下需要多少次比较运算？16. 贪心算法的基本思想？17. 回溯法的解（x1,x2,xn）的隐约束一般指什么？18. 阐述归并排序的分治思路。19. 快速排序的基本思想是什么。20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21. 什么是哈密顿环问题？22. 用回溯法求解哈密顿环，如何定义判定函数？23. 请写出prim算法的基本思想。 二、复杂性分析1、 MERGESORT(low，high)if low<high；then mid(low，high)
3、/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifend MERGESORT2、 procedure S1(P，W，M，X，n)i1; a0while i n doif W(i)>M then return endifaa+iii+1 ; repeatend 3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)vA(m);imlooploop ii+1 until A(i) v repeatloop pp-1 until A(p) v repe
4、atif i<pthen call INTERCHANGE(A(i),A(p) else exitendifrepeatA(m) A(p);A(p) vEnd PARTITION 4.procedure F1(n)if n<2 then return(1)else return(F2(2,n,1,1)endifend F1procedure F2(i,n,x,y)if inthen call F2(i+1,n,y,x+y)endifreturn(y)end F2 5.procedure MAX(A,n,j)xmaxA(1);j1for i2 to n doif A(i)>xm
5、ax then xmaxA(i); ji;endif repeatend MAX 6.procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low1;highnwhile lowhigh domid|_(low+high)/2_|case:x<A(mid):highmid-1:x>A(mid):lowmid+1 :else:jmid; returnendcaserepeatj0end BINSRCH 三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。 各边的代价如下：C(1,2)=3， C(1,3)=5
6、，C(1,4)=2C(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 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、 归并排序算法对下列实例排序，写出算法执行过程。
7、A=(48,12,61,3,5,19,32,7)6、 写出图着色问题的回溯算法的判断Xk是否合理的过程。7、 对于下图，写出图着色算法得出一种着色方案的过程。 8、 写出第7题的状态空间树。9、 写出归并排序算法对下列实例排序的过程。(6,2,9,3,5,1,8,7)10、 写出用背包问题贪心算法解决下列实例的过程。P=(18,12,4,1)W=(12,10,8,3)M=2511、有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当使用二分查找值为82的结点时，经过多少次比较后查找成功并给出过程。12、使用prim算法构造出如下图G的一棵最小生成树。 di
8、st(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的值是多少并写出详细过程。14、McCathy函数定义如下：当x>100时 m(x)=x-10;当x<=100时 m(x)=m(m(x+11);编写一个递归函数计算给定x的m(x)值。15、
9、设计一个算法在一个向量A中找出最大数和最小数的元素。 四、设计算法1. 设有n项独立的作业1,2, n,由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能短的时间内由m台机器处理完。设计算法，并讨论是否可获最优解。 2. 设有n种面值为:d1d2dn的钱币，需要找零钱M，如何选择钱币dk，的数目Xk，满足d1XidnXn=M ，使得XiXn 最小请选择贪心策略，并设计贪心算法。3. 有n个物品，已知n=7, 利润为P=(10,5,15,
10、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)的数量级(阶)评价
11、算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：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)/2<x，则Ai：(i+j)/2-1找x，否则在A (i+j)/2+1：j 找x。上述过程被反复
12、递归调用。回溯法的搜索特点是什么7. 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。8. 问题的解可以表示为n元组：（x1,x2,xn），xiSi, Si为有穷集合，xiSi, （x1,x2,xn）具备完备性，即（x1,x2,xn）是合理的，则（x1,x2,xi）(i<n)一定合理。9. 在解空间树上跳跃式地深度优先搜索，即用判定函数考察xk的取值，如果xk是合理的就搜索xk为根节点的子树，如果xk取完了所有的值，便回溯到xk-1。10. 将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。11 . 子问题的规模还
13、很大时，必须继续使用分治法，反复分治，必然要用到递归。 12 最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。13 .T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，nNo，有T(n)<f(n)，这种关系记作T(n)=O(f(n)。14 .二分检索算法的最多的比较次数为 log n 。 15.最坏情况下快速排序退化成冒泡排序，需要比较n次。16. 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入
14、量的加入，不满足约束条件，则不把此输入加到这部分解中。17回溯法的解（x1,x2,xn）的隐约束一般指个元素之间应满足的某种关系。18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。19.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分 时间为：O(1)while i n do
15、循环n次循环体因为in时要递归调用F2，一共是n-2次当n1时F1(n)的时间为 O(1) 当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=8 Cost(2,4)= minC(4
16、，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=7 Cost(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算法对下列实例中找最大数和最小数的
17、过程。数组 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=12，用递归树描述sumofsub算法求和数=M的一个子集的过程。 4、第一个分割元素为65 (1) (2) (3) (4) (5) (6) (7) (8) i p 65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6 55 70 75 80 85 65 50 2 5、48,12,61,3 5,19,32,748,
18、12 61,3 5,19 32,712,48 3,61 5,19 7,323, 12, 48, 61 5, 7, 19，323,5, 7,12，19，32，48,616、i0while i<k doif Gk,i=1 and Xk= Xi thenreturn falseii+1repeatif i= k then return true7、K1X1 1 , 返回 trueX21,返回false; X2X2+1=2, 返回 trueX31 ,返回false; X3X3+1=2, 返回false;X3X3+1=3, 返回 true X41, 返回false; X4X4+1=2, 返回fal
19、se;X4X4+1=3, 返回 true 找到一个解 （1，2，3，3） 8、 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(i)/W(i)P(i+1)/W(i+1)的顺序。CU25,X0W1< CU: x1
20、1; CUCU-W1=13;W2< CU: x21; CUCU-W2=3;W3>CU: 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的一棵最小生成树。 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)
21、=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的值是多少并写出详细过程。K的值是5 14.McCathy函数定义如下：当x>100时 m(x)=x-10; 当x<=100时 m(x)=m(m(x+11);编写一个递归函数计算给定x的m(x)值。int m(int x)int y;if(x>100) return(x-100);elsey=m(x+11);return (m(y);15 设计一个算法在一个向量A
22、中找出最大数和最小数的元素。Void maxmin(A,n)Vector A;int n;int max,min,i;max=A1;min=A1;for(i=2;i<=n;i+)if(Ai>max)max=Ai;else if(Ai<min)min=Ai;printf(“max=%d,min=%dn”,max,min);四、设计算法1. 设有n项独立的作业1,2, n,由m台相同的机器加工处理。作业i所需要的处理时间为ti。约定：任何一项作业可在任何一台机器上处理，但未完工前不准中断处理；任何作业不能拆分更小的子作业。多机调度问题要求给出一种调度方案，使所给的n个作业在尽可能
23、短的时间最小请选择贪心策略，并设计贪心算法。3. 有n个物品，已知n=7, 利润为P=(10,5,15,7,6,18,3)，重量W=(2,3,5,7,1,4,1)，背包容积M=15,物品只能选择全部装入背包或不装入背包，设计贪心算法，并讨论是否可获最优解。4. 设计只求一个哈密顿环的回溯算法。k5利用对称性设计算法，求n=2（K为正整数）的皇后问题所有解。 1.解：对于处理机j，用Sj 表示处理机j已有的作业数，用Pj,k表示处理机j的第k个作业的序号 。 1）将作业按照t1t2tn排序2）S1:m清零 j0 /从第一个处理机开始安排3) for i1 to n do /安排n个作业jj mo
24、d m +1 /选下一个处理机SjSj+1;Pj,Sji ；Repeat2.贪心原则：每次选择最大面值硬币。 CUM;i1;X0 / X为解向量While CU0 doXiCU div di / Xi为第i中硬币数CUCU-di*Xiii+1;repeat3、定义结构体数组G，将物品编号、利润、重量作为一个结构体：例如Gk=1,10,2 求最优解，按利润/重量的递减序，有5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1 算法procedure KNAPSACK(P，W，M，X，n)/P(1：n)和W(1；n)分别含有按P(
25、i)/W(i)P(i+1)/W(i+1)排序的n件物品的效益值和重量。M是背包的容量大小，而x(1：n)是解向量/real P(1：n)，W(1：n)，X(1：n)，M，cu；integer i，n；X0 /将解向量初始化为零/cuM /cu是背包剩余容量/for i1 to n doif W(i)>cu then exit endifX(i) 1cucu-W(i)repeatend GREEDY-KNAPSACK根据算法得出的解：X=（1,1,1,1,1,0,0）获利润52， 而解（1,1,1,1, 0, 1,0）可获利润54因此贪心法不一定获得最优解。 4Hamiltonian(n)
26、k1; xk 0;While k>0 do xk xk+1;while B(k)=false and xkn doxk xk+1; repeatIf xkn thenif k=n then print x; returnelse k k+1; xk0; endifelse k k-1endifrepeatend procedure B(k) Gxk-1,xk 1 then return false;for i1 to k-1 doif xi=xk then return false;endifrepeatreturn true;5利用对称性设计算法，求n为偶数的皇后问题所有解。 procedure NQUEENS1(n)a0 /计数器清零X(1)0；k1 /k是当前行；X(k)是当前列/While k>0 do /对所有的行执行以下语句/1) X(k)X(k)+1 /移到下一列/While X(k)n and not PLACE(k) do2) X(k)X(k)十lif X(k)nthen if k=n /thenprint(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