MOOC 算法设计与分析(北京航空航天大学)1449777166 最新慕课完整章节测试答案
01 算法绪论篇
文章目录
第1章单元测验
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、单选题：
函数
用
记号可表示为______
选项：
A: 
B: 
C: 
D: 
答案: 【 】
7、单选题：
下述伪代码希望求出数组
中数字
出现的次数，则伪代码空白处应填入______
输入：数组
，数字
输出：
在数组
中出现的次数
for 
to 
if 
then
________
end
end
return 
选项：
A: 
B: 
C: 
D: 
答案: 【 】
8、多选题：
函数
用
记号可表示为______
选项：
A: 
B: 
C: 
D: 
答案: 【 ;;】
9、多选题：
函数
用
记号可表示为______
选项：
A: 
B: 
C: 
D: 
答案: 【 ;;;】
10、多选题：
函数
用
记号可表示为______
选项：
A: 
B: 
C: 
D: 
答案: 【 ;】
02 分而治之篇I
第2章单元测验
1、单选题：
在归并排序算法中，若每次分解将长度为 n 的数组分为两段，长度分别为 n-1 和 1，此时归并排序算法的时间复杂度为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
2、单选题：
在归并排序算法中，若每次分解将长度为 n 的数组分为四段长度为 n/4 的子数组进行递归，此时归并排序算法的时间复杂度为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
3、单选题：
归并排序的最好情况时间复杂度为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
4、单选题：
的解为
=——
选项：
A: 
B: 
C: 
D: 
答案: 【 】
5、单选题：
的解为
____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
6、单选题：
的解为
____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
7、单选题：
的解为
____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
8、单选题：
的解为
____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
9、单选题：
在最大子数组问题的优化枚举算法中，每次计算子数组 X[i..j] 之和的时间复杂度为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
10、单选题：
在最大子数组问题的分治算法中，若可以用 O(1) 的时间求得跨越中点的最大子数组，则该算法的时间复杂度为
选项：
A: 
B: 
C: 
D: 
答案: 【 】
03 分而治之篇II
第3章单元测验
1、单选题：
数组
中的逆序对个数为____
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 5】
2、单选题：
长度为
的数组中逆序对个数最多为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
3、单选题：
快速排序算法的最坏情况时间复杂度为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
4、单选题：
在快速排序算法中，假定存在一个神奇的黑盒可以在O(1)的时间内给出最好的主元（也就是中位数），那么使用此神奇黑盒的快速排序算法最差运行时间为____（请选择最准确的答案）
选项：
A: 
B: 
C: 
D: 
答案: 【 】
5、单选题：
随机化快速排序算法的最坏情况时间复杂度为____（请选择最准确的答案）
选项：
A: 
B: 
C: 
D: 
答案: 【 】
6、单选题：
随机化快速排序算法的期望时间复杂度为____（请选择最准确的答案）
选项：
A: 
B: 
C: 
D: 
答案: 【 】
7、单选题：
快速排序算法的关键为数组的划分，下面给出了一种划分数组的方法，其中空白处应填入____
输入：数组
，起始位置
，终止位置
输出：划分位置
while 
do
while 
and 
do
end
if 
then
end
while 
and 
do
end
if 
then
end
end
return 
选项：
A: 
B: 
C: 
D: 
答案: 【 】
8、单选题：
下面给出了计算Fibonacci数列第
项的伪代码，该算法的时间复杂度为____（请选择最准确的答案）
输入：数字
输出：Fibonacci数列的第
项
if 
or 
then
return 
else
return 
end
选项：
A: 
B: 
C: 
D: 
答案: 【 】
9、单选题：
随机化次序选择算法的最坏情况时间复杂度为____（请选择最准确的答案）
选项：
A: 
B: 
C: 
D: 
答案: 【 】
10、单选题：
随机化次序选择算法的期望时间复杂度为____（请选择最准确的答案）
选项：
A: 
B: 
C: 
D: 
答案: 【 】
04 动态规划篇I
第4章单元测验
1、单选题：
在0-1背包问题中，若背包容量为20,5个物品的体积分别为
，价格分别为
。则该背包能容纳物品的最大总价格为____
选项：
A: 22
B: 23
C: 25
D: 26
答案: 【 25】
2、单选题：
在商品个数为
、背包容量为
的0-1背包问题中，蛮力枚举算法和动态规划算法的时间复杂度分别为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
3、单选题：
0-1背包问题中的递推式为____
选项：
A: 
B: 
C: 
D: 
答案: 【 】
4、单选题：
下面给出了0-1背包问题的动态规划算法伪代码，其中空白处应分别填入____
输入：商品数量 
,各商品价值
，各商品体积
，背包容量
输出：商品价格的最大值，最优解方案
创建二维数组
for 
do
end
for 
do
end
for 
do
for do
if 
then
end
else
end
end
end
for do
if 
then
print 选择商品
end
else
print 不选择商品
end
end
return 
,
选项：
A: 
B: 
C: 
D: 
答案: 【 】
5、单选题：
设计动态规划算法的一般步骤为____
选项：
A: 递推关系建立→问题结构分析→自上向下计算→最优方案追踪
B: 递推关系建立→问题结构分析→自底向上计算→最优方案追踪
C: 问题结构分析→递推关系建立→自上向下计算→最优方案追踪
D: 问题结构分析→递推关系建立→自底向上计算→最优方案追踪
答案: 【 问题结构分析→递推关系建立→自底向上计算→最优方案追踪 】
6、单选题：
最大子数组问题的分治算法和动态规划算法的时间复杂度分别为____ （请选择最准确的答案）
选项：
A: 
B: 
C: 
D: 
答案: 【 】
7、单选题：
在最大子数组问题的动态规划算法中，给出初始化部分的伪代码如下，空白处应填入____
输入：数组 
，数组长度
输出：最大子数组和
，子数组起止位置
新建一维数组
和
//初始化
选项：
A: 
B: 
C: 
D: 
答案: 【 】
8、单选题：
在最大子数组问题的动态规划算法中，给出计算部分的伪代码如下，空白处应填入__ _
输入：数组 ，数组长度
输出：最大子数组和，子数组起止位置
新建一维数组和
对
初始化
//动态规划
for do