复习题目

一 选择题

1、一个算法应该包含如下几条性质，除了 。 （A）二义性 性

2、当输入规模为n时，算法增长率最小的是 。 （A）5n

（B）20log2n

（C）2n2 （D）3nlog3n

（B）有限性

（C） 正确性

（D）可终止

3 当输入规模为n时，算法增长率最大的是 。A A． 5n

B．20log2n

C．2n2 D．3nlog3n

4 在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准？下面 答案解释最合理。D

A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准

D． 以上皆可行。但不同方法，算法复杂度上界可能不同 5 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。C

A．问题规模相同，问题性质相同 B．问题规模相同，问题性质不同 B．

问题规模不同，问题性质相同 D．问题规模不同，问

题性质不同

6对于含有n个元素的子集树问题，最坏情况下其解空间的叶结点数目为 。B

A．n! B．2 C．2

n

n+1

-1 D．?n!/i!

i?1n7 下列哪些问题不能用贪心法求解？ （ ）

A) 霍夫曼编码问题 C) 0-1背包问题

B) 单源最短路径问题 D) 最小生成树问题

8 二分搜索算法是利用（ ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9 回溯法解旅行售货员问题时的解空间树是（ ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树

6．下列算法中通常以自底向上的方式求解最优解的是（ ）。

A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（ ）。

A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 9. 实现循环赛日程表利用的算法是（ ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法

10．下列算法中通常以深度优先方式系统搜索问题解的是（ ）。

A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11．哈弗曼编码的贪心算法所需的计算时间为（ ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 12.下面是贪心算法的基本要素的是（ ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 定义最优解

13.下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）

A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数

14. 矩阵连乘问题的算法可由（ ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法

15、使用分治法求解不需要满足的条件是（）。

A 子问题必须是一样的 B 子问题不能够重复C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 16、下列算法中不能解决0/1背包问题的是（） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 17．实现合并排序利用的算法是（ ）。

A、分治策略 B、动态规划法 C、贪心法 D、回溯法

18．下列是动态规划算法基本要素的是（ ）。

D、

A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质

19．下列算法中通常以自底向下的方式求解最优解的是（ ）。 A、分治法 D、回溯法

20实现大整数的乘法是利用的算法（ ）。 A、贪心法 B、动态规划法 C、分治策略 D、回溯法 二 填空题：

1回溯算法的基本思想是 在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝） 。 2．动态规划和分治法在分解子问题方面的不同点是 前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的

。

3．选择排序、插入排序和归并排序算法中， 归并排序 算法是分治算法。

4、一个直接或间接调用自身的算法称为 递归 算法。 5 出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致 相同 。

6使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳

B、动态规划法 C、贪心法

情况下，搜索的时间复杂性为O（ 1 ），在最坏情况下，搜索的时间复杂性为O（logn ）。

7动态规划算法的基本要素是最优子结构性质 和 子问题重叠性质

8贪心算法的基本要素是 贪心选择性质和最优子结构性质。 9四后问题的搜索空间为（ 排列 ）树；0-1背包问题的搜索空间为（ 子集 ）树；巡回售货员问题的搜索空间为（ 满m叉 ）树。

10 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。

i

1 1 4

2 3 5

3 0 6

4 5 7

5 3 8

6 5 9

7 6 10

8 8 11

9 8 12

10 2 13

11 12 14

S[i] f[i]

11 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。

12 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。

三 简答题

本文来源：https://www.bwwdw.com/article/265d.html