计算机算法设计与分析期末考试复习题

.

1、二分搜寻算法是利用（

A ）实现的算法。

A、分治策略

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

A

D 、回溯法

2、以下不是动向规划算法基本步骤的是（ A、找出最优解的性质 3、最大效益优先是（ A、分支界线法

）。

B 、结构最优解 A

C 、算出最优解 ）的一搜寻方式。

C 、贪心法 B

D 、定义最优解

B 、动向规划法 D 、回溯法 ）。

D、回溯法

4、最长公共子序列算法利用的算法是（ A、分支界线法

B、动向规划法

A

C、贪心法

）。

5. 回溯法解 TSP问题时的解空间树是（ A、子集树

B、排列树

C、深度优先生成树

B

D、广度优先生成树

）。

6．以下算法中平常以自底向上的方式求解最优解的是（ A、备忘录法

B、动向规划法

C、贪心法

D、回溯法

7、权衡一个算法利害的标准是（ A 运行速度快

B

占用空间少

C ）。 C

时间复杂度低 D D ）。

合并排序 D 0/1

代码短

8、以下不能够使用分治法求解的是（ A 棋盘覆盖问题

B

选择问题

C

背包问题

）。

9. 实现循环赛日程表利用的算法是（ A、分治策略

A

C、贪心法

B

B、动向规划法 D、回溯法

）。

D、回溯法

）。

D、深度优先

10、实现最长公共子序列利用的算法是（ A、分治策略

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

D

C、最大效益优先

11．下面不是分支界线法搜寻方式的是（ A、广度优先

B、最小耗资优先

12．以下算法中平常以深度优先方式系统搜寻问题解的是（ A、备忘录法

D）。

D 、回溯法

B、动向规划法

C、贪心法

13. 一个问题可用动向规划算法或贪心算法求解的重点特点是问题的

（

B

）。

A、重叠子问题

B、最优子结构性质

A

B 、动向规划法

C、贪心选择性质 D 、定义最优解

）的一搜寻方式。

14．广度优先是（

A、分支界线法

C 、贪心法

B

）。

D 、回溯法

15．背包问题的贪心算法所需的计算时间为（

;..

.

A、 O（ n2n） B、 O（nlogn ）

C、 O（ 2n）

B

C、贪心法 A

C、贪心法

C

D、O（ n）

16．实现最大子段和利用的算法是（ A、分治策略

）。

B、动向规划法 D、回溯法

）。

17．实现棋盘覆盖算法利用的算法是（ A、分治法

B、动向规划法

D、回溯法

）。

18. 下面是贪心算法的基本要素的是（ A、重叠子问题

B、结构最优解

C、贪心选择性质 D

）

D、定义最优解

19. 回溯法的效率不依靠于以下哪些要素（ A. 知足显拘束的值的个数 C. 计算限界函数的时间

B. 计算拘束函数的时间 D. 确定解空间的时间

B

20. 下面哪一种函数是回溯法中为防范无效搜寻采用的策略（ A．递归函数

B. 剪枝函数

C。随机数函数

( D )

）

D. 搜寻函数

。

D 、回溯算法 ）。

D、定义最优解

）。

21、以深度优先方式系统搜寻问题解的算法称为 A、分支界线算法

B 、概率算法

C 、贪心算法 B

C、结构最优解 A

C、贪心法

22、贪心算法与动向规划算法的主要差异是（ A、最优子结构

B、贪心选择性质

23. 采用最大效益优先搜寻方式的算法是（ A、分支界线法 24. （

B、动向规划法 D、回溯法

D

B、结构最优解

）是贪心算法与动向规划算法的共同点。

C、贪心选择性质

A、重叠子问题

D、最优子结构性质

25. 矩阵连乘问题的算法可由（ A、分支界线算法

B）设计实现。 C 、贪心算法 A

C、 O（2n） B

）

D、 O（ n）

B 、动向规划算法 D、回溯算法

）

D、O（ n）

26. 0-1 背包问题的回溯算法所需的计算时间为（ A、 O（ n2n）

B、 O（nlogn ）

27、背包问题的贪心算法所需的计算时间为（ A、 O（ n2n）

B 、 O（ nlogn ）

C 、 O（ 2n） A ）。

29、使用分治法求解不需要知足的条件是（ A 子问题必定是同样的 用同样的方法解

B 子问题不能够重复

C 子问题的解能够合并 D 原问题和子问题使

30、下面问题（ B ）不能够使用贪心法解决。

;..

.

A 单源最短路径问题

31、以下算法中不能够解决

BN皇后问题 C 最小开支生成树问题

D 背包问题

0/1 背包问题的是（ A ）

分支限界法 C ）的次序。

A 贪心法 B 动向规划 C 回溯法 D 32、回溯法搜寻状态空间树是依照（

A 中序遍历 B 广度优先遍历 C 深度优先遍历 33、采用广度优先策略搜寻的算法是（ A、分支界线法

B、动向规划法

D 层次优先遍历

A

）。

C、贪心法

A

）。

C、贪心法

D

）。

D、回溯法

34．实现合并排序利用的算法是（ A、分治策略

B、动向规划法 D、回溯法

35．以下是动向规划算法基本要素的是（

A、定义最优解

B、结构最优解 C、算出最优解 D、子问题重叠性质

36．以下算法中平常以自底向下的方式求解最优解的是（

B

C、贪心法

）。

A、分治法 二、 填空题 1. 算法的复杂性有

B、动向规划法 D、回溯法

时间 复杂性和 空间 复杂性之分。

2、程序是

算法 用某种程序设计语言的详细实现。

3、算法的“确定性”指的是组成算法的每条

指令

设计实现。

是清楚的，无歧义的。

4. 矩阵连乘问题的算法可由

动向规划 一种方法

5、算法是指解决问题的

或 一个过程

。

。

6、迅速排序算法的性能取决于

区分的对称性

7、从分治法的一般设计模式能够看出，用它设计出的程序一般是

递归算法 。

8、问题的

最优子结构性质 是该问题可用动向规划算法或贪心算法求解的重点特点。

9、以深度优先方式系统搜寻问题解的算法称为 10、任何可用计算机求解的问题所需的时间都与其 11、计算一个算法时间复杂度平常能够计算

回溯法 。

规模

相关。

或计算步。

循环次数 、 基本操作的频次

拘束函数 和

限界函数

12、回溯法搜寻解空间树时，常用的两种剪枝函数为

14、解决 0/1 背包问题能够使用动向规划、 态规划

，需要排序的是

回溯法

回溯法和分支限界法， 其中不需要排序的是 ，分支限界法

。

动

15、使用回溯法进行状态空间树裁剪分支时一般有两个标准：拘束条件和目标函数的界，

N

皇后问题和 0/1 背包问题正好是两种不同样的种类， 其中同时使用拘束条件和目标函数的界进

;..

.

行裁剪的是0/1 背包问题

系统性

，只使用拘束条件进行裁剪的是N

皇后问题 。

17、回溯法是一种既带有 又带有 跳跃性

重叠子问题

的搜寻算法。 性质

18. 动向规划算法的两个基本要素是. 19. 贪心算法的基本要素是

最优子结构性质和

质和

贪心选择 最优子结构

子问题

性质 。

，先求解

21. 动向规划算法的基本思想是将待求解问题分解成若干 问题

，此后从这些

子问题

子

的解获得原问题的解。

算法是由若干条指令组成的有穷序列， 23、迅速排序算法是鉴于

且要知足输入， 输出 、确定性和 有限性 四条性质。

分治策略 的一种排序算法。

24、以广度优先或以最小耗资方式搜寻问题解的算法称为 三、 算法设计题

分支限界法

。

1. 背包问题的贪心算法，

分支限界算法

2. 最大子段和 : 动向规划算法 3. 贪心算法求活动安排问题 5. 迅速排序

6. 多机调动问题 -贪心算法

四、简答题

1 分治法的基本思想

2. 分治法与动向规划法的同样点 3. 分治法与动向规划法的不同样点 4. 分支限界法与回溯法的同样点

5．分治法所能解决的问题一般拥有的几个特点是： 6. 用分支限界法设计算法的步骤

7. 回溯法中常有的两类典型的解空间树是子集

8. 请简述符号 t(n)∈ θ (g(n)),t(n)∈ Ω (g(n)),t(n)∈ Ο (g(n))的含义。 9. 分支限界法的搜寻策略是：

;..