2021 算法设计与分析(青岛大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2021-03-01到2021-07-31

第一章 算法概论 第一章 单元测试

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

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:错误
答案: 【错误】

12、 问题:描述算法只能使用二种方法：伪代码或自然语言
选项：
A:正确
B:错误
答案: 【错误】

13、 问题:下面哪个算法在最坏情况下的时间复杂性最低
选项：
A:归并排序
B:插入排序 
C:快速排序 
D:冒泡排序
答案: 【归并排序】

14、 问题:  A公司处理器速度是B公司的100倍。对于复杂性为O()的算法，B公司的计算机可以在1小时内处理规模为n的问题，A公司的计算机在1小时内能处理的问题规模是多少？
选项：
A:n
B:10n
C:100n
D:
答案: 【10n】

15、 问题:关于算法的正确性，下面哪些说法是正确的？
选项：
A:若算法是正确的， 则算法一定能结束（运行时间是有限的）
B:若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。
C:对于问题的一个实例，如果算法能够获得正确的结果，就证明算法是正确的。
D:对于问题的一个实例， 如果算法不能获得正确的结果， 就证明算法是不正确的。
答案: 【若算法是正确的， 则算法一定能结束（运行时间是有限的）;
若算法是正确的，则对于问题的任何实例，算法都能得到正确的结果。;
对于问题的一个实例， 如果算法不能获得正确的结果， 就证明算法是不正确的。】

16、 问题:解决同一个问题的算法策略可能有多个，使用不同算法策略设计的算法，其算法时间复杂性可能有显著差异。
选项：
A:正确
B:错误
答案: 【正确】

17、 问题:学习主定理和递归树等求解递归方程方法，主要目的是解决求递归算法的时间复杂性问题
选项：
A:正确
B:错误
答案: 【正确】

18、 问题:自然语言、伪代码都可以描述算法，而流程图不能描述算法
选项：
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:这是因为归并排序把问题划分为子问题时的时间复杂性低，而快速排序划分为子问题是使用partition()函数，划分为子问题的时间复杂性高。
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