当前位置:首页 > 算法分析与设计考试复习题及参考答案
一、简要回答下列问题 :
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×XnM ,使得 Xi+……Xn 最小 请选择贪心策略,并设计贪心算法。 3. 有n个物品,已知n=7, 利润为P=(10,5,15,7,6,18,3),重量W=(2,3,5,7,1,4,1),背包容积M=15,物品只能选择全部装入背包或不装入背包,设计贪心算法,并讨论是否可获
共分享92篇相关文档