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

同学情

北京交通大学远程与继续教育学院
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、回溯法是一种既带有 又带有 跳跃性 的搜索算法。
三. 更多资料下载：谋学网（www.mouxue.com）（共 4 道小题， 每题 10 分， 共 40 分）
1. 动态规划算法的基本要素包括什么？（10 分）
2. 贪心法求解的问题的特征包括什么?（10分）
3. 合并排序基本思想是什么？合并排序 最坏时间复杂度？合并排序 平均时间复
杂度？快速排序 最坏时间复杂度？快速排序时间复杂度？（10分）
4. 动态规划算法的步骤是什么？（10分）

孙牡外

谋学网还可以！

中书令

下次优惠点

luciebkuox7

一直都在用谋学网，不错！