算法分析与设计期末复习题目 一、
选择题
1．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法
B、动态规划法
C、贪心法
D、回溯法
2、衡量一个算法好坏的标准是（C ）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 3、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 4．下列是动态规划算法基本要素的是（ D ）。 A、定义最优解 重叠性质
5．采用广度优先策略搜索的算法是（ A ）。 A、分支界限法
B、动态规划法
C、贪心法
D、回溯法
B、构造最优解
C、算出最优解
D、子问题
6、合并排序算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7、下列不属于影响程序执行时间的因素有哪些？ （ C ） A．算法设计的策略 B．问题的规模
C．编译程序产生的机器代码质量 D．计算机执行指令的速度 8、使用分治法求解不需要满足的条件是（A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并
D 原问题和子问题使用相同的方法解
9、下面问题（B ）不能使用贪心法解决。 A 单源最短路径问题 C 最小花费生成树问题
B N皇后问题 D 背包问题
10. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题
11. 以深度优先方式系统搜索问题解的算法称为 ( D ) 。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法
12. 实现最长公共子序列利用的算法是（ B ）。 A、分治策略
B、动态规划法
C、贪心法
D、回溯法
B、最优子结构性质
C、贪心选择性质 D、定义最优解
13．下列算法具有最优子结构的算法是 （D）
A．概率算法 B．回溯法 C．分支限界法 D．动态规划法
14.算法分析是（ C）
A.将算法用某种程序设计语言恰当地表示出来
B.在抽象数据集合上执行程序,以确定是否会产生错误的结果 C.对算法需要多少计算时间和存储空间作定量分析 D.证明算法对所有可能的合法输入都能算出正确的答案
15 衡量一个算法好坏的标准是（C ）
A.运行速度快 B. 占用空间少 C.时间复杂度低 D. 代码短
16.二分搜索算法是利用（A）实现的算法。 A.分治法 B.动态规划法 C.贪心法 D.回溯法
17．用贪心法设计算法的关键是（ B ）。 A.将问题分解为多个子问题来分别处理 B.选好最优量度标准
C.获取各阶段间的递推关系式 D.满足最优性原理
18.找最小生成树的算法Kruskal的时间复杂度为（ D ）（其中n为无向图的结点数，m为边数）
A．O(n2) B．O(mlogn) C．O(nlogm) D．O(mlogm)
19.回溯法搜索状态空间树是按照（C ）的顺序。 A.中序遍历 B.广度优先遍历 C.深度优先遍历 D.层次优先遍历
20.采用广度优先策略搜索的算法是（ A ）。 A.分支界限法 B.动态规划法 C.贪心法 D.回溯法
21.函数32n+10nlogn的渐进表达式是( B ).
A.O( 2n) B. O( 32n) C. O( nlogn ) D. O( 10nlogn)
22.二分搜索算法的时间复杂性为（ C ）。
2A.O(n) B.O(n) C.O(logn) D. O(nlogn)
23、快速排序算法的时间复杂性为（ D ）。
2A.O(n) B.O(n) C.O(logn) D. O(nlogn)
24、算法是由若干条指令组成的有穷序列，而且满足以下性质（ D ） A.输入：有0个或多个输入 B.输出：至少有一个输出
C. 确定性：指令清晰，无歧义 D.有限性：指令执行次数有限，而且执行时间有限
A. (1)(2)(3) B. (1)(2)(4) C. (1)(3)(4) D.(1) (2)(3)(4)
25、背包问题的贪心算法所需的计算时间为（ B ）
A. O（n2n） B. O（nlogn） C.O（2n） D.O（n）
26.下列算法中不能解决0/1背包问题的是（ A ） A 贪心法 B 动态规划 C 回溯法 D 分支限界法
27. 在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面 (D) 答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准
D．以上皆可行。但不同方法，算法复杂度上界可能不同