中国大学算法设计与分析_11期末答案(慕课2023课后作业答案)

中国大学算法设计与分析_11期末答案(慕课2023课后作业答案)

点击查看答案

第一章 算法设计基础

“算法设计基础”单元测验

1、中国作业下列关于算法的大学答案答案说法中正确的有（）。
A、算法设计求解某一类问题的分析算法是唯一的
B、算法必须在有限步操作之后停止
C、期末算法的慕课每一步操作必须是明确的，不能有歧义或含义模糊
D、课后算法执行后一定产生确定的中国作业结果

2、以下哪些是大学答案答案算法的基本特点（）。
A、算法设计至少有1个输入和1个输出
B、分析有穷性
C、期末确定性
D、慕课可行性

“算法设计基础”算法实现题

1、课后Smith数问题

2、中国作业最接近数问题

第二章 算法分析基础

“算法分析基础”测试题

1、以下关于渐近记号的性质，正确的有（ ）
A、
B、
C、
D、

2、以下关于记号的定义，正确的是（ ）
A、存在正常数和使得对所有有：
B、存在正常数和使得对所有有：
C、对于任何正常数，存在正数和使得对所有有：
D、对于任何正常数，存在正数和使得对所有有：

3、若一个算法的递归方程为，则其时间复杂度为（ ）
A、
B、
C、
D、

4、表示当输入规模为时的算法效率，以下算法效率最优的是（ ）
A、
B、
C、
D、

第三章 分治法

“分治法”单元测试

1、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。
A、问题规模相同，问题性质相同
B、问题规模相同，问题性质不同
C、问题规模不同，问题性质相同
D、问题规模不同，问题性质不同

2、在寻找 n 个元素中第 k 小元素问题中，如快速排序算法思想，运用分治算法对 n个元素进行划分，如何选择划分基准？下面（ ）答案解释最合理。
A、随机选择一个元素作为划分基准
B、取子序列的第一个元素作为划分基准
C、用中位数的中位数方法寻找划分基准
D、以上皆可行。但不同方法，算法复杂度上界可能不同

3、减少子问题个数，就是减少时间复杂度函数T(n)=aT(n/b)+f(n) 中的（ ）值。
A、n
B、a
C、b
D、f(n)

4、使用分治法求解不需要满足的条件是（ ）。
A、子问题不能够重复
B、子问题必须具有相同的性质
C、子问题的解可以合并
D、原问题和子问题使用相同的方法求解

5、改进分治算法的方法有（ ）。
A、减少子问题的个数
B、减少合并的时间
C、减少问题的规模
D、改进分治的均衡度

6、阅读以下代码: int Fun(int n) { if(n <= 1) return 1; int First = Fun(n-1); int Second = Fun(n-2); int iSum = First + Second; return iSum; } 调用该函数，假设输入参数n值为5，当程序第二次执行语句 iSum = First + Second时，iSum的值为（ ）。

“分治法”算法实现题

1、循环左移问题

2、逆序数问题

第四章 动态规划法

“动态规划法”算法实现题

1、拦截导弹问题

2、新水果取名

3、机器人路径规划

第五章 回溯法

“回溯法”算法实现题

1、求解最小机器重量设计问题

2、求解部分和问题

第六章 分枝限界法

“分枝限界法”算法实现题

1、迷宫问题

第七章 贪心法

“贪心法”算法实现题

1、求解畜栏问题

2、求解区间覆盖问题

算法考试题

2020年算法设计与分析考试试卷

1、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ ）。
A、问题规模相同，问题性质相同
B、问题规模相同，问题性质不同
C、问题规模不同，问题性质相同
D、问题规模不同，问题性质不同

2、下面问题（ ）不能使用贪心法解决。
A、单源最短路径问题
B、n皇后问题
C、最小生成树问题
D、背包问题

3、对于 0－1 背包问题和背包问题的解法，下面（ ）答案解释正确。
A、0－1 背包问题和背包问题都可用贪心算法求得最优解
B、0－1 背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
C、0－1 背包问题不能用贪心算法求最优解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
D、因为 0－1 背包问题不具有最优子结构性质，所以不能用贪心算法求解

4、常见的两种分支限界法为（ ）。
A、广度优先分支限界法与深度优先分支限界法
B、队列式（FIFO）分支限界法与堆栈式分支限界法
C、排列树法与子集树法
D、队列式（FIFO）分支限界法与优先队列式分支限界法

5、T(n)表示当输入规模为 n 时的算法效率，以下算法效率最优的是（ ）。
A、
B、
C、
D、

6、算法分析中，记号Θ表示（ ）。
A、渐近下界
B、渐近上界
C、非紧上界
D、渐近紧界

7、采用最大效益优先搜索方式的算法是（ ）。
A、分支限界法
B、动态规划法
C、贪心法
D、回溯法

8、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n个元素进行划分，如何选择划分基准？下面（ ）答案解释最合理。
A、随机选择一个元素作为划分基准
B、取子序列的第一个元素作为划分基准
C、用中位数作为划分基准
D、以上皆可行。但不同方法，算法复杂度上界可能不同

9、回溯法在问题的解空间树中，按（ ）策略，从根结点出发搜索解空间树。
A、广度优先
B、活结点优先
C、扩展结点优先
D、深度优先

10、优先队列式分支限界法选取扩展结点的原则是（ ）。
A、先进先出
B、后进先出
C、结点的优先级
D、随机

11、归并排序算法是利用（ ）实现的算法。
A、分治策略
B、动态规划法
C、贪心法
D、回溯法

12、（ ）是回溯法中为避免无效搜索采取的策略。
A、递归函数
B、剪枝函数
C、随机数函数
D、限界函数

13、找n个元素的中位数的分治算法的时间复杂度为( )。
A、
B、
C、
D、

14、回溯法的算法框架按照问题的解空间一般分为子集树算法框架与（ ）算法框架。
A、深度优先生成树
B、二叉树
C、广度优先生成树
D、排列树

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

16、算法是由若干条指令组成的有穷序列，而且满足以下性质（ ）。
A、输入：有 0 个或多个输入
B、输出：至少有一个输出
C、确定性：指令清晰，无歧义
D、有限性：指令执行次数有限，而且执行时间有限

17、求解递归方程使用的方法有（ ）。
A、迭代法
B、代入法
C、主定理
D、递归树

18、分治法所能解决的问题一般具有（ ）特征。
A、问题可以分解为规模较小的子问题
B、子问题可合并为原问题的解
C、小规模子问题可解
D、子问题不相互独立

19、回溯法的效率依赖于下列哪些因素（ ）。
A、满足显式约束的值的个数
B、计算限界函数的时间
C、确定解空间的时间
D、计算约束函数的时间

20、改进分治算法的方法有（ ）。
A、改进分治的均衡度
B、减少合并的时间
C、减少子问题的个数
D、减少问题的规模

21、无论在何种情况下，分治法总能产生效率最高的算法。

22、一个算法是正确的，那么它就是有效的。

23、重叠子问题保证了动态规划算法的正确性。

24、同一个问题，其动态规划算法的效率一定比分治法设计的算法高。

25、如果问题的最优解中也包含着其子问题的最优解，则该问题具有最优子结构性质。