2020 算法设计与分析(浙江海洋大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-02-24到2020-07-05
本篇答案更新状态:已完结

第一周 算法概述及复杂性理论 单元测验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&&i0.1<=sqrt(n))
i++;
if(i1.0>sqrt(n))
printf(“%d is a prime.”,n);
else
printf(“%d is not a prime.”,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:错误
答案: 【错误】
分析：【测试集相同，但运行的硬件环境不同，没法根据算法运行的快慢来判断算法的好坏。有时，即便硬件条件相同，不同的测试集选择也会影响算法的比较结果。】

【作业】第二周 算法分析方法 单元作业2

1、 问题:1. 对某个数据结构执行一个具有n个运算的序列。如果i为2的整数幂，则第i个运算的费用为i否则为1.使用合计方法确定每次运算的分摊费用。
评分规则: 【 答案正确
】

2、 问题:2. 用势能方法分析上题。
评分规则: 【 答案正确
】

第三周 递归 单元测验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);
n lg(n);
nlgn;
n lgn;
n lg n】

【作业】第三周 递归 单元作业3

1、 问题:1. 将插入排序算法更改为递归形式，并分析时间复杂度。
评分规则: 【 使用递归实现
递归出口正确
】

2、 问题:2. 修改Perm1使得生成子序列按照字典序排列。
评分规则: 【 以字典序生成结果
进入递归前，不需要每次都排序
】

3、 问题:公式法求解以下递归方程：（1）T(n)=4T(n/2)+n。(2)T(n)=4T(n/2)+n^2。(3)T(n)=4T(n/2)+n^3。
评分规则: 【 1题正确
2题正确
3题正确
】

【作业】第四周 分治（上） 单元作业4

1、 问题:给定有序数组A以及一个元素x，设计一个寻找x的分治算法并分析其时间复杂度，要求返回x在数组中的位置。回答可以用C语言或JAVA语言等具体语言的程序，也可以用伪代码。
评分规则: 【 程序正确、思路清晰、条理清楚、问题分析透彻、语言逻辑性强。
】

2、 问题:给定n个整数的数组A以及一个数x，设计一个分治算法，求出x在数组中出现的次数，并分析时间复杂度。（提示：统计x出现次数的变量可以定义为全局变量。）回答可以用C语言或JAVA语言等具体语言的程序，也可以用伪代码。
评分规则: 【 使用分治算法
程序正确，边界条件处理正确。思路清晰、条理清楚、问题分析透彻、语言逻辑性强。
】

【作业】第一周 算法概述及复杂性理论 单元作业1

1、 问题:1. 给定一个算法，其输入是一个整数集S和一个整数m，输出是和为m的所有S的子集，算法步骤如下：（1）列出S的全部子集，求他们的和。（2）逐个查看步骤（1）列出的子集，把每个和等于m的子集输出。上述算法是否满足算法特点？说明理由。
评分规则: 【 回答满足算法特点
确定性
可行性
有穷性
】

2、 问题:2. 利用循环不变量证明下述计算a^n算法的正确性：Exp(a,n)1 i<-12 pow<-13 while i<=n do4 pow<-pow*a5 i<-i+16 return pow
评分规则: 【 初始步证明考虑n==0的情况
初始步证明考虑n==1的情况
证明过程清楚
】

3、 问题:3. 设有两个在同一机器上实现的算法，运行时间分别为100n^2和2^n。当n取何值时，前者比后者快？
评分规则: 【 答案正确
】

第四周 分治（上） 单元测验4

1、 问题:快速排序的平均时间复杂度为：
选项：
A:
B:
C:
D:
答案: 【】

2、 问题:冒泡排序的平均时间复杂度为：
选项：
A:
B:
C:
D:
答案: 【】

3、 问题:归并排序的平均时间复杂度是：
选项：
A:
B:
C:
D:
答案: 【】

4、 问题:归并排序在最坏情况下的时间复杂度为：