大学MOOC 算法设计与分析(浙江海洋大学)1452098207 最新慕课完整章节测试答案
第一周算法概述及复杂性理论
单元测验1
1、单选题：
n个整数，采用选择排序算法进行排序的时间复杂度是：
选项：
A: O(
)
B: O(
)
C: O(
)
D: O(n)
答案: 【 O()】
2、单选题：
以下程序的时间复杂度为：void prime(int n)
{ int i=2;
while((n%i)!=0&&i*0.1<=sqrt(n))
i++;
if(i*1.0>sqrt(n))
printf("%d is a prime.n",n);
else
printf("%d is not a prime.n",n);
}
选项：
A: O(n)
B: O(
)
C: O(n/2)
D: O(
)
答案: 【 O()】
3、判断题：
和
具有相同的增长速度
选项：
A: 正确
B: 错误
答案: 【 错误】
4、填空题：
衡量、比较算法优劣的主要指标有：空间复杂度和
答案: 【 时间复杂度】
第二周算法分析方法
单元测验2
1、单选题：
通过概率分析方法可以分析一个算法：
选项：
A: 在最好情况下的运行时间
B: 在最坏情况下的运行时间
C: 所有实例的情况下的平均运行时间
D: 以上说法都不对
答案: 【 以上说法都不对】
2、单选题：
势能方法的思想是：将预先支付的代价视为潜在能量（势能），能够为__________的操作支付能量。
选项：
A: 过去的
B: 未来的
C: 现在的
D: 以上所有的
答案: 【 未来的】
3、多选题：
算法的分析方法有：概率分析、____________、____________、____________、____________。
选项：
A: 合计方法
B: 记账方法
C: 势能方法
D: 实验分析
答案: 【 合计方法;
记账方法;
势能方法;
实验分析】
4、判断题：
算法分析中的合计方法需要考虑各种案例出现的概率。
选项：
A: 正确
B: 错误
答案: 【 错误】
5、判断题：
解决一个问题，“实际花费的时间之和”要小于等于“分摊分析的时间之和”。
选项：
A: 正确
B: 错误
答案: 【 正确】
6、判断题：
为了不同的操作分配不同的费用，其中某些操作的费用高于或低于实际费用。对一项业务收取的额外费用称为“摊余代价”
选项：
A: 正确
B: 错误
答案: 【 正确】
7、判断题：
使用相同的测试集，如果A算法得到结果的速度比B算法快，说明A算法优于B算法。
选项：
A: 正确
B: 错误
答案: 【 错误】
第三周递归
单元测验3
1、单选题：
对于时间复杂度公式为： T(n)=aT(n/b)+f(n) 的递归算法。（其中n为问题规模，可以被划分为a个规模为n/b的子问题，解决每个子问题所需时间为T(n/b)，划分原问题和合并子问题的解所需要的的时间由f(n)决定）。则该算法的时间复杂度T(n)=
选项：
A: 
B: 
C: 
D: 以上答案都有可能
答案: 【 以上答案都有可能】
2、填空题：
（注意：本题要在英文输入法下回答，直接英文就输入，不要用公式输入格式。）对于时间复杂度公式为： T(n)=3T(n/3)+n 的递归算法。 其时间复杂度为:
答案: 【 nlg(n)##%_YZPRLFH_%##n lg(n)##%_YZPRLFH_%##nlgn##%_YZPRLFH_%##n lgn##%_YZPRLFH_%##n lg n】
第四周分治上
单元测验4
1、单选题：
快速排序的平均时间复杂度为：
选项：
A: