2022年11月18日 gebilaowang

算法设计与分析(北京航空航天大学) mooc慕课答案2026年版满分测试

01 算法绪论篇第1章单元测验

1、函数用记号可表示为______

答案:

2、函数用记号可表示为______

答案:

3、函数用记号可表示为______

答案:

4、函数用记号可表示为______

答案:

5、函数用记号可表示为______

答案:

6、函数用记号可表示为______

答案:

7、下述伪代码希望求出数组中数字出现的次数，则伪代码空白处应填入__输入：数组，数字输出：在数组中出现的次数for to if then ______ endendreturn

答案:

8、函数用记号可表示为______

答案: ;
;

9、函数用记号可表示为______

答案: ;
;
;

10、函数用记号可表示为______

答案: ;

02 分而治之篇I 第2章单元测验

1、在归并排序算法中，若每次分解将长度为 n 的数组分为两段，长度分别为 n-1 和 1，此时归并排序算法的时间复杂度为____

答案:

2、在归并排序算法中，若每次分解将长度为 n 的数组分为四段长度为 n/4 的子数组进行递归，此时归并排序算法的时间复杂度为____

答案:

3、归并排序的最好情况时间复杂度为____

答案:

4、的解为=——

答案:

5、的解为 ____

答案:

6、的解为____

答案:

7、的解为____

答案:

8、的解为____

答案:

9、在最大子数组问题的优化枚举算法中，每次计算子数组 X[i..j] 之和的时间复杂度为____

答案:

10、在最大子数组问题的分治算法中，若可以用 O(1) 的时间求得跨越中点的最大子数组，则该算法的时间复杂度为

答案:

03 分而治之篇II 第3章单元测验

1、数组中的逆序对个数为____

答案: 5

2、长度为的数组中逆序对个数最多为____

答案:

3、快速排序算法的最坏情况时间复杂度为____

答案:

4、在快速排序算法中，假定存在一个神奇的黑盒可以在O(1)的时间内给出最好的主元（也就是中位数），那么使用此神奇黑盒的快速排序算法最差运行时间为____（请选择最准确的答案）

答案:

5、随机化快速排序算法的最坏情况时间复杂度为____（请选择最准确的答案）

答案:

6、随机化快速排序算法的期望时间复杂度为____（请选择最准确的答案）

答案:

7、快速排序算法的关键为数组的划分，下面给出了一种划分数组的方法，其中空白处应填入____输入：数组，起始位置，终止位置输出：划分位置 while dowhile and do endif then endwhile and do endif then endendreturn

答案:

8、下面给出了计算Fibonacci数列第项的伪代码，该算法的时间复杂度为____（请选择最准确的答案）输入：数字输出：Fibonacci数列的第项 if or then return else return end

答案:

9、随机化次序选择算法的最坏情况时间复杂度为____（请选择最准确的答案）

答案:

10、随机化次序选择算法的期望时间复杂度为____（请选择最准确的答案）

答案:

04 动态规划篇I 第4章单元测验

小提示:本节包含奇怪的同名章节内容

1、在0-1背包问题中，若背包容量为20,5个物品的体积分别为，价格分别为。则该背包能容纳物品的最大总价格为____

答案: 25

2、在商品个数为、背包容量为的0-1背包问题中，蛮力枚举算法和动态规划算法的时间复杂度分别为____

答案:

3、 0-1背包问题中的递推式为____

答案:

4、下面给出了0-1背包问题的动态规划算法伪代码，其中空白处应分别填入____输入：商品数量 ,各商品价值，各商品体积，背包容量输出：商品价格的最大值，最优解方案创建二维数组for do endfor do endfor do for do if then end else end end end for do if then print 选择商品 end else print 不选择商品 endendreturn ,

答案:

5、设计动态规划算法的一般步骤为____

答案: 问题结构分析→递推关系建立→自底向上计算→最优方案追踪

6、最大子数组问题的分治算法和动态规划算法的时间复杂度分别为____ （请选择最准确的答案）

答案:

7、在最大子数组问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入____输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和//初始化

答案:

8、在最大子数组问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入__ _输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化//动态规划for do if then end else endend

答案:

9、在最大子数组问题的动态规划算法中，给出查找解部分的伪代码如下，空白处应填入__ _输入：数组，数组长度输出：最大子数组和，子数组起止位置新建一维数组和对初始化计算数组和数组//查找解 for do if then endendreturn

答案:

10、对于包含个正数元素的数组，我们希望找出数组中的一些元素，使得这些元素在数组中互不相邻并且元素之和最大。例如在数组中，应当选择和，元素之和为。给出该问题的解决算法如下，空白处应填入____输入：正数数组，元素个数输出：选择的元素，最大不相邻元素之和创建数组，表示数组中的最大不相邻元素之和创建数组记录选择方案if then endelse endfor do if then end else endendreturn

答案:

11、在最大子数组问题的动态规划算法中，给出查找解部分的伪代码如下，空白处应填入__ _

输入：数组，数组长度
输出：最大子数组和，子数组起止位置
新建一维数组和
对初始化
计算数组和数组
//查找解

for     do
    if  then



    end
end
return

答案:

05 动态规划篇II 第5章单元测验

1、给定两个序列分别为“algorithm”和“glorhythm”。则以下分别为两序列的最长公共子序列和最长公共子串的选项是____

答案: gorthm thm

2、在最长公共子序列问题中，我们用表示序列和序列的最长公共子序列长度，则递推式应为____

答案:

3、给出最长公共子序列问题的部分伪代码如下，其中空白处应分别填入____输入：两个序列输出：的最长公共子序列分别代表的序列长度//初始化新建二维数组for do endfor do endfor do for do if then end else if then end else end endend

答案:

4、在最长公共子串问题的递推式中，表示____

答案: 和中以和结尾的最长公共子串的长度

5、最长公共子串问题的递推式为

答案:

6、给定两个字符串,需要判断中有多少个子序列与相等。例如：则和两个子序列都与相等。思考该问题，可以用表示的子序列中与相等的个数，如上例。则对应的递推式为___

答案:

7、在支持插入、删除、替换三种操作的最小编辑距离问题中，我们用表示字符串变为的最小编辑距离，则递推式应为

答案:

8、在支持插入、删除、替换三种操作的最小编辑距离问题中，用数组来记录编辑方案。则数组中的”L”,”U”,”LU”分别代表哪种操作___

答案: 插入删除替换/空操作

9、字符串“algorithm”到字符串“altruistic”的最小编辑距离为___

答案: 6

10、下面给出了最长公共子序列问题中输出最长公共子序列的函数Print-LCS()伪代码，其中空白处应分别填入____输入：追踪数组，序列，当前位置和输出：的最长公共子序列if then return endif then Print-LCS(,, , ) print else if then Print-LCS(,,,)endelse Print-LCS(,,,)end

答案:

06 动态规划篇III 第6章单元测验

1、在钢条切割问题中，若钢条长度为，且长度从到的钢条价格分别为。则切割后钢条的最大总收益为____

答案:

2、在矩阵链乘法问题中，矩阵链中矩阵的规模分别为。则该矩阵链所需标量乘法的最小次数为____次

答案:

3、在钢条切割问题中，表示切割长度为的钢条可得最大总收益，表示长度为的钢条的价格，则递推式为____

答案:

4、下面给出了钢条切割问题的动态规划算法的部分伪代码，其中空白处应分别填入____输入：钢条价格表，钢条长度输出：最大收益，钢条切割方案//初始化创建一维数组 for do for do if then end end end输出最优方案return

答案:

5、下面给出了钢条切割问题的动态规划算法中追踪最优方案部分的伪代码，其中空白处应分别填入____//输出最优方案while do print end

答案:

6、在矩阵链乘法问题中，表示计算矩阵链所需标量乘法的最小次数，则该问题的递推式为____

答案:

7、在矩阵链乘法问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入___ 输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和//初始化 for then end

答案:

8、在矩阵链乘法问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入输入：矩阵维度数组，矩阵个数输出：最小标量乘法次数，分割方式追踪数组新建二维数组和初始化//动态规划for do for do for do if then end end endendreturn

答案:

9、在矩阵链乘法问题的动态规划算法中，给出追踪最优方案部分的伪代码如下，空白处应填入____Print-Matrix-Chain()输入：矩阵链,追踪数组,位置索引和输出：矩阵链加括号方式if then print returnendprint “(”Print-Matrix-Chain(,, , )print “)(”Print-Matrix-Chain(,, , )print “)”return

答案:

10、对某仅包含左右括号的字符串而言，若其中左括号和右括号可以正确的匹配，那么称其为均衡字符串。例如，字符串“(())”和“()()”都是均衡字符串，但是“())(()”不是均衡字符串。给定一个长度为n的仅包含左右括号的字符串S，请求出字符串S的最长均衡子序列。换言之，请从S中挑选出尽量多的字符按顺序组成新字符串S’，使得S’是一个均衡字符串。例如，对字符串“())(()”而言，我们可以挑选其中第1，2，5，6个字符构成一个长度为的均衡字符串“()()”。我们用表示字符串的最长均衡子序列长度，则其递推式应为____

答案:

07 贪心策略篇第7章单元测验

1、在部分背包问题中，若背包容量为，有个物品可供选择。每个物品价格分别为，体积分别为。则该背包可容纳物品最大总价格为___ _

答案:

2、下面给出了部分背包问题的贪心算法的伪代码，其中空白处应分别填入输入：商品数量,各商品的价值,各商品的体积，背包容量输出：商品价格的最大值计算商品性价比并按降序排序// 分别表示性价比第大的商品的性价比、价格和体积//根据贪心策略求解while do if then 选择商品 end else 选择体积的商品 end endreturn

答案:

3、给出共5个字符，其出现频数(千次)分别为。按照课程中所讲左0右1，左小右大的规则建树编码，则字符串的霍夫曼编码应为____

答案:

4、下面给出了霍夫曼编码问题的算法的伪代码，其中空白处应分别填入___ 输入：各字符频数，字符数输出：霍夫曼编码树//预处理将递增排序新建结点数组for do endfor do 新建结点 endreturn

答案:

5、在活动选择问题中，给出6个活动其时间分别为,则最多能安排活动数为____

答案:

6、下面给出了活动选择问题的算法的伪代码，其中空白处应分别填入____ 输入：活动集合 ,每个活动的起止时间输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动for do if then endendreturn

答案:

7、在加权活动选择问题中，给出个活动其时间分别为 ,权重分别为,则安排权重最大和为___

答案:

8、在加权活动选择问题中有个活动组成的集合，令表示集合中不冲突活动最大权重和，为以活动开始前最后结束的活动，为活动的权重。则递推式为____

答案:

9、给出加权活动选择问题部分伪代码如下，空白处应填入__ _输入：活动集合,每个活动的起止时间，权重输出：不冲突活动的最大子集将活动按照结束时间升序排序，使表示结束时间第小的活动for do 二分查找求解end新建数组 //动态规划for do if then end else endendreturn