算法设计与分析复习题

算法设计与分析复习题Tag内容描述：<p>1、一。选择题1、二分搜索算法是利用（A ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2、下列不是动态规划算法基本步骤的是（A ）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解3、最大效益优先是（A ）的一搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法4、在下列算法中有时找不到问题解的是（B&。</p><p>2、1 计算机算法设计与分析复习题计算机算法设计与分析复习题 一一、填空填空题题 1、 一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上， 因此算法的复杂性有 时间 复杂性和空间复杂性之分。 2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题 时，这些子问题的规模都大致 相同 。 3、使用二分搜索算法在 n 个有序元素表中搜索一个特定元素，在最佳情况下， 搜索的时间复杂性为 O （1） ， 在最坏情况下， 搜索的时间复杂性为 O （ logn ） 。 4、已知一个分治算法耗费的计算时间 T(n)，T(n)满足。</p><p>3、算法设计与分析复习题1、 一个算法应有哪些主要特征？有限性、确定性、输入、输出、可行性2、 分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？分治法是将一个问题划分成一系列独立的子问题，分别处理后将结果组合以得到原问题的答案。动态规划同样将一个问题划分成一系列子问题进行处理，但当子问题不是互相独立而是互有联系时，动态规划不会重复计算子问题间联系的问题，是更高效的解决办法。3、 试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。贪心算法的思想是通过选择局部最优以求得最优。</p><p>4、一。选择题1、二分搜索算法是利用（A ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2、下列不是动态规划算法基本步骤的是（B ）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解3、最大效益优先是（A ）的一搜索方式。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法4、在下列算法中有时找不到问题解的是（B&#16。</p><p>5、一、填空题（20分）1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。3.某一问题可用动态规划算法求解的显著特征是____________________________________。4.若序列X=B,C,A,D,B,C,D，Y=A,C,B,A,B,D,C,D，请给出序列X和Y的一个最长公共子序列_____________________________。5.用回溯法解问题时，应明确。</p>