算法设计与分析综合练习题.doc

算法设计与分析综合练习题一填空题1. 算法是指解决问题的一种方法和一个过程，它具有如下四条性质：_、_、_、和_。2. 函数3n2+10nlogn的渐近表达式为_；函数3n3+2n的渐近表达式为_。3. 算法的复杂性分两种，分别为_和_。4. 二分搜索算法在最坏情况下的时间复杂性是_；快速排序算法MergeSort在平均情况下的时间复杂性是_。5. 动态规划法的两个基本要素是_和_。6. 动态规划算法的一个变形是_方法，该方法为每个子问题建立一个_，用来保存子问题的解并用于表示子问题是否已求解。7. 能用贪心算法求得最优解的问题应具有的两个重要性质是_和_。8. 贪心算法总是作出在当前看来最好的选择，并不从_最优上加以考虑，只是在某种意义上的_最优选择。9. 回溯法有_之称，它以_的方式搜索包括问题所有解的解空间树。10.从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法，最常见的有以下两种：_分支限界法或_分支限界法。11算法是由若干条指令组成的有穷序列，满足如下四条性质：_、_、_、和_。12. 函数logn2+10nlogn的渐近表达式为_；函数n3logn+2n的渐近表达式为_。13. 算法的复杂性分两种，需要时间资源的量称为_，需要空间资源的量称为_。14. 合并排序算法在最坏情况下的时间复杂性是_；快速排序算法在最坏情况下的时间复杂性是_。15. 可以用动态规划法求解的问题应具有的两个重要性质是_和_。16. 备忘录方法是_算法的一个变形，该方法为每个子问题建立一个_，用来保存子问题的解并用于表示子问题是否已求解。17. 贪心算法的两个基本要素是_和_。18. 使用贪心算法解决活动安排问题时使用了_的贪心选择策略，而在解决汽车加油问题中使用了_的贪心选择策略。19. 通过回溯法解题时，经常遇到两种典型的解空间树，分别为_和_。20. 分支限界法常以_或以_的方式搜索问题的解空间树。21. 算法的复杂性有_和_之分。22. 算法的时间复杂性函数用_表示，其中参数n是指_。23. 已知渐进意义下的记号O,W,Q,判断下列几组函数的关系： f(n)= log2n,g(n)= logn，满足f(n)= _ (g(n)；f(n)= logn2 ,g(n)= logn+5，满足f(n)= _ (g(n)；f(n)= logn2,g(n)= n1/2,满足f(n)= _ (g(n)；f(n)= 10,g(n)= log1010,满足f(n)= _ (g(n)；f(n)= log4n,g(n)= 4logn，满足f(n)= _ (g(n)；f(n)= logn2 ,g(n)= 5logn，满足f(n)= _ (g(n)；f(n)= 1,g(n)= log1010,满足f(n)= _ (g(n)。24. 函数n2+2n/10的渐近表达式为_；函数21+1/n2的渐近表达式为_；函数4n2+2n的渐近表达式为_。25. 可用动态规划法求解的问题应具有的两个重要性质是_和_。26. 贪心算法的两个基本要素是_和_。27. _与分治法的基本思想非常相似，但是与分治法不同，适用该方法的问题，经分解得到的子问题往往不是互相独立的。28. 使用贪心算法解决活动安排问题时使用了_优先的贪心选择策略，而在解决一般背包问题中使用了_优先的贪心选择策略。29. 通过回溯法解题时，经常遇到两种典型的解空间树，分别为_和_。30.分支限界法类似于回溯法，两者对于当前扩展结点所采用的_方式不同。31. 使用贪心算法解决活动安排问题时使用了_优先的贪心选择策略，而在解决一般背包问题中使用了_优先的贪心选择策略。32. 当问题的最优解包含了其子问题的最优解时，称该问题具有_性质。33. 动态规划法与_法的基本思想非常相似，但不同的是适用后者方法的问题，经分解得到的子问题往往是互相独立的。34. 可用动态规划法求解的问题应具有的两个重要性质是最优子结构性质和_。35. 通过回溯法解题时，经常遇到两种典型的解空间树，分别为_和_。36. 分支限界法类似于回溯法，两者对于解空间树的_方式不同。二名词解释和问答题1什么是算法？2算法具有的特性是什么？3时间复杂度、空间复杂度4最优解5递归算法6分治法的基本思想7动态规划的基本要素和解题步骤8贪心算法的基本要素9描述回溯法的基本思想10分析分支限界法与回溯法的异同11分析动态规划与分治法的异同12分别画出回溯法中0-1背包问题和旅行售货员问题的解空间树。13描述二分搜索算法的基本思想。14. 请给出0-1背包问题的形式化描述。15. 请描述使用贪心算法解决活动安排问题的算法思想。三算法复杂度分析题1. 用主定理解以下时间复杂度函数的递归方程，并给出简要计算过程：(1)(2)(3) (4) 2.求解如下递归式，已知T(1)=1，a、b、c均为常数且a=b=c=1。（1）T(n)=aT(n-1)+bn（2）T(n)=aT(n/2)+bnc3. 汉诺塔问题的时间复杂性的递推函数如下，试分析其时间复杂性。四算法设计题1. 现有一批工程，每个工程都具有一定的投资风险，作为一名投资人，请你使用一种算法找出工程中的最大风险值和最小风险值，要求（1）描述算法， (2)进行时间复杂性分析。2. 给定一个有n个元素的数组a0:n-1,试设计一个算法，在最坏情况下用次比较找出数组a0:n-1中元素的最大值和最小值，要求（1）描述算法， (2)进行时间复杂性分析。3. 设计实现二分搜索算法的关键代码(虚线部分)。template int BinarySearch(Type a, const Type& x, int l, int r) 4. 设计实现试补充贪心算法求一般背包问题的关键代码(虚线部分)。void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); for (int i=1;i=n;i+) xi=0; float c=M; 五、算法填空题1. 以下是二分搜索问题的关键代码，请将空白部分补充完整。template int BinarySearch(Type a , const Type& x, int left, int right) while (_) int mid = _; if (x = amid) return _; if (x amid)right = _; else left = _; return -1; /未找到x2请补全以下一般背包问题的贪心算法代码。 void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); /排序 for (int i=1;i=n;i+) xi=_; /初始化数组x float c=M; for (i=1;i c) _; xi=_; c = _; if (i=n) xi= _; 3. 请补全以下回溯法解决装载问题的关键代码。templatevoid Loading:Backtrack(int i) /搜索第i层结点 if(in) if(cwbestw) bestw=_; /更新最优值 return; /搜索当前结点的左右子树 if( _ ) /满足约束进入左分支,xi=1 cw = _; _; cw = cw-wi; Backtrack (_); /进入右分支 六实例求解题1.假定在A1:9中顺序存放着以下九个元素：-15,-6,0,7,9,23,54,82,101,用二分检索算法检索x=101是否在A中，需要比较几次，列出详细过程。2.设有一般背包问题实例, n=4, C=12, w1,w2,w3,w4=4,7,5,3, v1,v2,v3,v4= 6,21,10,12。用贪心算法求这一实例的最优解以及背包最大收益。3.设有0/1背包问题实例, n=4, C=12, w1,w2,w3,w4=4,7,5,3, v1,v2,v3,v4= 5,9,10,8。用动态规划算法求这一实例的最优值和最优解。4.请用快速排序法升序排列实例（3,20,5,9,2,30,25,18,16,3），给出每一趟排序的结果。5.有0/1背包问题如下：n=6，c=20，P=（11,8,15,18,