算法分析复习题(含答案).pdfVIP

一、选择题 1、衡量一个算法好坏的标准是（ C ）。 （A）运行速度快 （B）占用空间少 （C）时间复杂度低 （D）代码短 2、记号 O 的定义正确的是（ A）。 （A）O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有： 0 f(n) cg(n) } ； （B）O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有： 0 cg(n) f(n) } ； （C）O(g(n)) = { f(n) | 对于任何正常数 c0 ，存在正数和 n0 0 使得对所有 n n0 有： 0 f(n)cg(n) } ； （D）O(g(n)) = { f(n) | 对于任何正常数 c0 ，存在正数和 n0 0 使得对所有 n n0 有： 0 cg(n) f(n) } ； 3、二分有哪些信誉好的足球投注网站算法是利用（ A ）实现的算法。 （A）分治策略 （B）动态规划法 （C）贪心法 （D）回溯法 4、使用分治法求解不需要满足的条件是（ A ）。 （A）子问题必须是一样的 （B）子问题不能够重复 （C）子问题的解可以合并 （D）原问题和子问题使用相同的方法解 5、合并排序算法是利用（ A ）实现的算法。 （A）分治策略 （B）动态规划法 （C）贪心法 （D）回溯法 6、实现大整数的乘法是利用（ C ）的算法。 （A）贪心法 （B）动态规划法 （C）分治策略 （D）回溯法 7、以下不可以使用分治法求解的是（ D ）。 （A）棋盘覆盖问题 （B）选择问题 （C）归并排序 （D） 0/1 背包问题 8、实现循环赛日程表利用的算法是（ A ）。 （A）分治策略 （B）动态规划法 （C）贪心法 （D）回溯法 9、实现棋盘覆盖算法利用的算法是（ A ）。 （A）分治法 （B）动态规划法 （C）贪心法 （D）回溯法 10、矩阵连乘问题的算法可由（ B ）设计实现。 （A）分支界限算法 （B）动态规划算法 （C）贪心算法 （D）回溯算法 11、实现大整数的乘法是利用的算法（ C ）。 （A）贪心法 （B）动态规划法 （C）分治策略 （D）回溯法 12、最长公共子序列算法利用的算法是（ B ）。 （A）分支界限法 （B）动态规划法 （C ）贪心法 （D）回溯法 13、下列算法中通常以自底向上的方式求解最优解的是（ B ）。 （A）备忘录法 （B）动态规划法 （C）贪心法 （D）回溯法 14、下列是动态规划算法基本要素的是（ D ）。 （A）定义最优解 （B）构造最优解 （C）算出最优解 （D）子问题重叠性质 15、下列不是动态规划算法基本步骤的是（ A ）。 （A）找出最优解的解空间 （B）构造最优解 （C）算出最优解 （D）定义最优解 16、能采用贪心算法求最优解的问题，一般具有的重要性质为： （ A ） （A）最优子结