24春北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）

1144766066 · 发表于 2024-4-24 20:23:26

北京交通大学远程与继续教育学院

2023- - 2024 4 学年第一学期计算机科学与技术专升本

计算机算法设计与分析课程（B B ）试卷（闭卷）

一. 单选题（共 15 道小题，每题 3 分，共 45 分）

1、以深度优先方式系统搜索问题解的算法称为 ( ) 。

A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法

2、贪心算法与动态规划算法的主要区别是（）。

A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解

3. 采用最大效益优先搜索方式的算法是（）。

A、分支界限法 B、动态规划法 C、贪心法 D、回溯法

4. （）是贪心算法与动态规划算法的共同点。

A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质

5. 矩阵连乘问题的算法可由（）设计实现。

A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法

6. 0-1 背包问题的回溯算法所需的计算时间为（）

A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

7、背包问题的贪心算法所需的计算时间为（）

A、O（n2 n ） B、O（nlogn） C、O（2 n ） D、O（n）

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

A、子问题必须是一样的 B、子问题不能够重复

C、子问题的解可以合并 D、原问题和子问题使用相同的方法解

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

A 、单源最短路径问题 B、 N 皇后问题

C 、最小花费生成树问题 D 、背包问题

10、下列算法中不能解决 0/1 背包问题的是（）

A、贪心法 B、动态规划 C、回溯法 D 、分支限界法

11、回溯法搜索状态空间树是按照（）的顺序。

A、中序遍历 B、广度优先遍历 C、深度优先遍历 D 、层次优先遍历

12、采用广度优先策略搜索的算法是（）。

A、分支界限法 B、动态规划法 C、贪心法 D、回溯法

13、实现合并排序利用的算法是（）。

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

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

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

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

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

二. 填空题（共 5 道小题，每题 3 分，共 15 分）

1、计算一个算法时间复杂度通常可以计算、基本操作的频率或计算

步。

2、回溯法搜索解空间树时，常用的两种剪枝函数为和限界函数

3、解决 0/1 背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序

的是，需要排序的是回溯法，分支限界法。

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

数的界，N皇后问题和 0/1 背包问题正好是两种不同的类型，其中同时使用约束

条件和目标函数的界进行裁剪的是，只使用约束条件进行裁剪的是 N 皇

后问题

5、回溯法是一种既带有又带有跳跃性的搜索算法。

三. 更多资料下载：网（）（共 4 道小题，每题 10 分，共 40 分）

1. 动态规划算法的基本要素包括什么？（10 分）

2. 贪心法求解的问题的特征包括什么?（10分）

3. 合并排序基本思想是什么？合并排序最坏时间复杂度？合并排序平均时间复

杂度？快速排序最坏时间复杂度？快速排序时间复杂度？（10分）

4. 动态规划算法的步骤是什么？（10分）

24春北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）

本帖子中包含更多资源

天涯海角也要找到Ni：24春北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）

QQ微信同步：1144766066。

服务

网站

战略合作

24春 北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）

本帖子中包含更多资源

天涯海角也要找到Ni：24春 北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）

QQ微信同步：1144766066。

服务

网站

战略合作

24春北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）

天涯海角也要找到Ni：24春北京交通大学远程与继续教育学院《计算机算法设计与分析》课考试题（b）