MOOC 算法设计与分析(青岛大学)1460628161 最新慕课完整章节测试答案
第一章 算法概论
第一章 单元测试
1、单选题：
下面列出了算法的四个性质，哪个性质是程序不一定具备的？
选项：
A: 有输入
B: 有输出
C: 确定性
D: 有穷性
答案: 【 有穷性】
2、单选题：
在算法设计与分析过程中，有算法设计，算法的正确性证明，算法的复杂性分析,程序设计等几个重要步骤，下面哪种顺序是正确的？
选项：
A: 算法的正确性证明->算法设计->算法的复杂性分析->程序设计
B: 算法的正确性证明->算法的复杂性分析->算法设计->程序设计
C: 算法设计->算法的正确性证明->算法的复杂性分析->程序设计
D: 算法设计->算法的复杂性分析->算法的正确性证明->程序设计
答案: 【 算法设计->算法的正确性证明->算法的复杂性分析->程序设计】
3、单选题：
下面哪些内容不是算法设计之前要完成的内容?
选项：
A: 是求精确解还是近似解
B: 确定合适的数据结构
C: 确定合适的算法策略
D: 使用何种计算机语言设计程序
答案: 【 使用何种计算机语言设计程序】
4、单选题：
下面是快速幂算法求
的代码，这里n≥0, a是实数。对该算法的时间复杂性描述不准确的是哪个？
doule exp2(double a, int n)
{
int i;
double b, s=1.0；
i=n；b=a;
while（i>0）
{
if(i%2) s*=b；
i/=2; b*=b;
}
return s;
}
选项：
A: 
B: 
C: 
D: 
答案: 【 】
5、单选题：
下面哪个算法在最坏情况下的时间复杂性最低
选项：
A: 归并排序
B: 插入排序
C: 快速排序
D: 冒泡排序
答案: 【 归并排序】
6、单选题：
有时间复杂性
,时间复杂性从低到高的顺序是？
选项：
A: 
B: 
C: 
D: 
答案: 【 】
7、单选题：
有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是?
选项：
A: 
B: 
C: 
D: 
答案: 【 】
8、单选题：
有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是？
选项：
A: 
B: 
C: 
D: 
答案: 【 】
9、单选题：
有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是？
选项：
A: 
B: 
C: 
D: 
答案: 【 】
10、单选题：
有一个算法， 它的时间复杂性T(n)的递归定义如下， 问T（n）是?
选项：
A: 
B: 
C: 
D: 
答案: 【 】
11、单选题：
A公司处理器速度是B公司的100倍。对于复杂性为O(
)的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时内能处理的问题规模是多少？
选项：
A: n
B: 10n
C: 100n
D: 
答案: 【 10n】
12、多选题：
关于算法的正确性，下面哪些说法是正确的？
选项：
A: 若算法是正确的， 则算法一定能结束（运行时间是有限的）
B: 若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。
C: 对于问题的一个实例，如果算法能够获得正确的结果，就证明算法是正确的。
D: 对于问题的一个实例， 如果算法不能获得正确的结果， 就证明算法是不正确的。
答案: 【 若算法是正确的， 则算法一定能结束（运行时间是有限的）;
若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。;
对于问题的一个实例， 如果算法不能获得正确的结果， 就证明算法是不正确的。】
13、判断题：
解决同一个问题的算法策略可能有多个，使用不同算法策略设计的算法，其算法时间复杂性可能有显著差异。
选项：
A: 正确
B: 错误
答案: 【 正确】
14、判断题：
学习主定理和递归树等求解递归方程方法，主要目的是解决求递归算法的时间复杂性问题
选项：
A: 正确
B: 错误
答案: 【 正确】
15、判断题：
自然语言、伪代码都可以描述算法，而流程图不能描述算法
选项：
A: 正确
B: 错误
答案: 【 错误】
第二章 分治法
第二章 单元测试
1、单选题：
分治法解决问题分为三步走，即分、治、合。下面列出了几种操作， 请按分、治、合顺序选择正确的表述。（1）将各个子问题的解合并为原问题的解，（2）将问题分解为各自独立的多个子问题，（3）将多个子问题合并为原问题。（4）求各个子问题的解，（5）将问题分解为可重复的多个子问题。
选项：
A: (5)(4)(1)
B: (2)(4)(1)
C: (2)(1)(3)
D: (5)(1)(3)
答案: 【 (2)(4)(1)】
2、单选题：
分治法的时间复杂性分析，通常是通过分析得到一个关于时间复杂性T(n)的一个递归方程， 然后解此方程可得T(n)的结果。T(n)的递归定义如下：
关于该定义中k，n/m, f(n)的解释准确的是
选项：
A: k是常系数；n/m是规模为n的问题分为m个子问题；f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和。
B: k是子问题个数，n/m是子问题的规模，f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和
C: k是子问题个数，n/m是子问题的规模，f(n)是规模为n的问题分解为子问题的时间复杂性
D: k是常系数，n/m是规模为n的问题分为m个子问题，f(n)是将子问题的解合并为问题的解的时间复杂性。
答案: 【 k是子问题个数，n/m是子问题的规模，f(n)是分解为子问题的时间复杂性与合并子问题的解的时间复杂性之和】
3、单选题：
已知斐波那契数列中第n个斐波那契数F(n)=F(n-1)+F(n-2),问能不能使用分治策略求第n个斐波那契数，从下面选项中选取答案。
选项：
A: 能，因为它满足分治法的四个适应条件
B: 能，因为它可以用分、治、合三个步骤完成计算
C: 不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）
D: 不能，因为它不可以用分、治、合三个步骤完成计算
答案: 【 不能，因为它不满足分治法的第四个适应条件（子问题是相互独立的，也就是没有重复子问题）】
4、单选题：
快速幂算法求
， 其时间复杂性为O(logn)，a是实数，n为非负整数。下面是一同学用c语言编写的求的代码
double exp2(double a,int n)
{ if(a==0) return 0;
if (n==0) return 1;
else
{
if(n%2) return a* exp2(a,n/2)* exp2(a,n/2);
else return exp2(a,n/2)* exp2(a,n/2);
}
}
对该同学的算法评价正确的是？
选项：
A: 运行结果正确，时间复杂性为O(logn)
B: 运行结果错误，时间复杂性为O(n)
C: 运行结果正确，时间复杂性为O(n)
D: 运行结果错误，时间复杂性为O(logn)
答案: 【 运行结果正确，时间复杂性为O(n)】
5、单选题：
快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(
), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？
选项：
A: 这是因为归并排序把问题划分为子问题时的时间复杂性是O(1)，而快速排序划分为子问题是使用partition()函数，其时间复杂性是O（n）。
B: 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)
C: 归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和
D: 因为快速排序将问题划分为子问题的个数比归并排序要多
答案: 【 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为原问题规模n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n) 】
6、单选题：
猜数游戏：随机选择一个0~100内的整数，让你猜。 猜对了，你赢了，游戏结束。如果没有猜对，会告诉你猜大了，还是猜小了。当然，越早猜对越好。 问最少需要猜多少次，就能保证一定能猜对？
选项：
A: 6
B: 7
C: 51
D: 101
答案: 【 7】
7、单选题：
对于一个采用字符数组存放的长度为n的字符串str，下面是用分治策略的递归算法去判断字符串str是否为回文，如是回文，函数返回true，否则返回false。比如：“abcba”、“abba”是回文，“abc”则不是回文。bool isPal( char *str, int n){&n