算法分析作业详解.doc

算法分析练习题（一） 一、选择题 1、二分有哪些信誉好的足球投注网站算法是利用（???A????? ）实现的算法。 A、分治策略?? B、动态规划法?? C、贪心法??? D、回溯法 2、下列不是动态规划算法基本步骤的是（???A??? ）。 A、找出最优解的性质?? B、构造最优解?? C、算出最优解?? D、定义最优解 3．下列算法中通常以自底向上的方式求解最优解的是（???B????? ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 4、衡量一个算法好坏的标准是（C ）。A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短5、以下不可以使用分治法求解的是（D ）。A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题6. 实现循环赛日程表利用的算法是（????A????? ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 8．最长公共子序列算法利用的算法是（????B?????? ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 9．实现棋盘覆盖算法利用的算法是（?????A????? ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 10. 矩阵连乘问题的算法可由（??????????B）设计实现。 A、分支界限算法????? B、动态规划算法??? C、贪心算法??? D、回溯算法 11、Strassen矩阵乘法是利用（????A???? ）实现的算法。 A、分治策略?? B、动态规划法?? C、贪心法??? D、回溯法 12、使用分治法求解不需要满足的条件是（A ）。A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解13、下列算法中不能解决0/1背包问题的是（A ）A 贪心法 B 动态规划 C 回溯法 D 分支限界法14．实现合并排序利用的算法是（?????A??? ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 15．下列是动态规划算法基本要素的是（??D???? ）。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 16．下列算法中通常以自底向下的方式求解最优???的是（????B???? ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 17、合并排序算法是利用（???A????? ）实现的算法。 A、分治策略?? B、动态规划法?? C、贪心法??? D、回溯法 18．实现大整数的乘法是利用的算法（??????C?? ）。 A、贪心法 B、动态规划法 C、分治策略 D、回溯法 19. 实现最大子段和利用的算法是（?????B????? ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 20. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（???B????????? ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解 21. 实现最长公共子序列利用的算法是（?????B????? ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 二、填空题 1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。 2、程序是 ?算法???用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。 4.矩阵连乘问题的算法可由 动态规划 设计实现。 5、算法是指解决问题的 一种方法 或 一个过程 。 6、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。 7、矩阵连乘问题的算法可由 动态规划 设计实现。 8. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这些 子问题 的解得到原问题的解。 9.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。 10、大整数乘积算法是用 分治法 来设计的。 11.快速排序算法是基于 分治策略 的一种排序算法。 12.动态规划算法的两个基本要素是. 性质和 性质 。 13.任何可用计算机求解的问题所需的时间都与其 规模 有关。 14.快速排序算法的性能取决于 划分的对称性 。 15、出自