算法分析与设计考试复习题及参考答案.pdf
《算法分析与设计考试复习题及参考答案.pdf》由会员分享,可在线阅读,更多相关《算法分析与设计考试复习题及参考答案.pdf(13页珍藏版)》请在三一文库上搜索。
1、一、简要回答下列问题: 1.算法重要特性是什么? 2.算法分析的目的是什么? 3.算法的时间复杂性与问题的什么因素相关? 4.算法的渐进时间复杂性的含义? 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同? 6.简述二分检索(折半查找)算法的基本过程。 7.背包问题的目标函数和贪心算法最优化量度相同吗? 8.采用回溯法求解的问题,其解如何表示?有什么规定? 9.回溯法的搜索特点是什么? 10. n 皇后问题回溯算法的判别函数place 的基本流程是什么? 11. 为什么用分治法设计的算法一般有递归调用? 12. 为什么要分析最坏情况下的算法时间复杂性? 13. 简述渐进时间复杂性上界的定义
2、。 14. 二分检索算法最多的比较次数? 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
3、 end 3.procedure PARTITION(m,p) Integer m,p,i;global A(m:p-1) vA(m);i m loop loop ii+1 until A(i) v repeat loop p p-1 until A(p) v repeat if ixmax then xmaxA(i); ji;endif repeat end MAX 6.procedure BINSRCH(A,n,x,j) integer low,high,mid,j,n; low1;high n while lowhigh do mid|_ (low+high)/2_| case :xA(
4、mid):lowmid+1 :else:j mid; return endcase repeat j0 end BINSRCH 三、算法理解 1、写出多段图最短路经动态规划算法求解下列实例的过程,并求出最优值。 各边的代价如下: 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、出 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、 对于下图,写出图着色算法得出一种着色方案的过程。 8、 写出第 7 题的状态空间树。 9、 写出归并排序算法对下列实例排序的过程。 (6,2,9,3,5,1,8,7) 10、 写出
6、用背包问题贪心算法解决下列实例的过程。 P=(18,12,4,1) 5 1 3 4 2 6 7 8 1 3 4 2 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的一棵最小生成树。 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)=
7、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 函数定义如下: 当 x100 时 m(x)=x-10; 当 x1 时 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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 考试 复习题 参考答案
链接地址:https://www.31doc.com/p-5521856.html