2020 算法分析设计与提高(桂林电子科技大学信息科技学院) 最新满分章节测试答案

分类：已完结, 网课答案
标签： MOOC答案, 网课小帮手, 网课答案

【作业】第1章算法设计基础单元作业1
【作业】第2章算法分析基础单元作业2-1 时间复杂度分析基础
【作业】第2章算法分析基础单元作业2-2 非递归与递归的时间分析
【作业】第3章蛮力法（枚举法）单元作业1
【作业】第3章蛮力法（枚举法）单元作业2
【作业】第4章分治法分治法单元作业
【作业】第5章减治法减治法作业-矩阵搜索问题

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

【作业】第1章算法设计基础单元作业1

1、问题:以下是短除法求最大公约数的伪代码：输入：两个自然数m和n输出：m和n的最大公约数1.factor=1;2.循环变量 i 从2 ~ min{m,n}，执行下列操作： 2.1 while(i是 m 和 n 的公因子)： 2.1.1 factor=factor * i 2.1.2 m=m/i; n=n/i; 2.2 i = i + 1;3.输出factor; 根据上述伪代码，若输入为m=180，n=72, 写出算法执行过程中factor, i, m,n四个变量值的变化。（约定：写出每次执行完语句2.1.2之后四个变量的值）factor i m n? ? ? ?? ? ? ?……
评分规则: 【 factor i m n2 2 90 36 （10分）4 2 45 18 （10分）12 3 15 6 （10分）36 3 5 2 （10分）
】

2、问题:给定欧几里德算法求两个数m和n的最大公约数的伪代码表示如下：输入：正整数 m, n输出：m 与 n 的最大公约数1. while n>0 do2. r m mod n3. m n4. n r5. return m 现给定一输入实例m=31415，n = 14142, 请写出循环体每执行完一遍之后m和n的值，并说明最终输出的最大公约数是多少。m n? ?? ?……最大公约数是？
评分规则: 【
】

3、问题:如果使用第1题中的短除法来计算第2题中的输入实例的话（m=31415，n = 14142），第1题伪代码中的外层循环会执行多少次？对于这个实例，你觉得上述两个算法哪个更好？
评分规则: 【外层循环会执行14141次。（10分）因为循环变量i是从2自增到m和n中比较小的一个，即2到14142；而在循环体内，由于所有的i都不是m和n的公因子，所以m和n的值不会变小。因此是 14142-2+1 = 14141 次。第2题中的欧几里德算法更好。（10分）
】

【作业】第2章算法分析基础单元作业2-1 时间复杂度分析基础

1、问题:给定以下两个算法：算法A：for(int i = 0; i < N; i++) for(int j = 0; j< N; j++) { S; }算法B：for(int i = 0; i < N; i++) for(int j = i; j< N; j++) { S; }其中N是一个比较大的自然数，S是有若干基本语句组成的程序段。1）在相同的计算机上，算法A比算法B运行速度慢？2）算法A的时间复杂度比算法B要高？请判断以上两个命题是否正确？并说明理由。
评分规则: 【参考答案：1）正确，因为算法A执行S的次数比算法B要多，因此运行速度较慢。2）错误，算法复杂度的表示是最坏情况下关键操作执行次数的渐进阶，而不是算法执行的具体时间。此题算法A和算法B的渐进阶相同，因此，其复杂度也相同。评分标准：对于每一小题：结论正确，且论述理由充分，则得15分；对于每一小题：结论正确，且论述理由不充分，则得10分；对于每一小题：结论不正确，则得0分；
】

2、问题:阅读下面的算法后回答问题。算法 Secret(A[0..n-1]) minval A[0] maxval A[0] for i 1 to n-1 do if A[i] A[i] if A[i]>maxval, then maxval A[i] return maxval – minvala）该算法求的是什么？b）它的基本操作（基本语言）是什么？c）该基本操作执行了多少次？d）如何用大O符号表示该算法的效率？
评分规则: 【 (a) 求输入的数组中最大值与最小值的差（10分）(b) A[i]maxval, 这两个比较操作是每次循环一定会执行的，所以是基本语句。（10分）(c) n – 1 次 (10分)(d) O(n) (10分)
】

3、问题:当输入规模n非常大时，对下列用大O符号表示的算法时间复杂度渐近结果排序（表示算法执行时间短的排前面）。O() O() O() O() O(nlogn) O(n) O(n!) O(1)
评分规则: 【 O(1) < O() < O(n) < O(nlogn) < O() < O() < O() < O(n!)（按对应位置给分，每个位置的5分，共40分）以2为底的对数输入成O(log2n)或O(logn)均可，指数输入成类似O(2^n)均可
】

【作业】第2章算法分析基础单元作业2-2 非递归与递归的时间分析

1、问题:考虑下面的算法，回答下列问题：(1) 算法完成什么功能？(2) 算法的基本语句是什么？(3) 基本语句执行了多少次？（计算T(n) ）(4) 算法的时间度是多少？（用大O表示）int stery(int n)
{
int s = 0;
for(int i=1; i<=n; i++)
s = s + i*i;
return s;
}
评分规则: 【 (1) 计算1到n的平方和，即 1^2 + 2^2 + 3^2 + …… + n^2； (5分)(2) 基本语句是 s = s + i * i; (5分)(3) 基本语句执行了n次，即 T(n) = n； (5分)(4) 算法的时间度是O(n) (5分)
】

2、问题:考虑下面的算法，回答下列问题：(1) 算法完成什么功能？(2) 算法的基本语句是什么？(3) 基本语句执行了多少次？（列出T(n)的递推式，并扩展求出其关于n的表达式, 默认T(1) = 1 ）(4) 算法的时间度是多少？（用大O表示)int Q(int n)
{
if(n==1)
return 1;
else
return Q(n-1) + 2n – 1;
}
评分规则: 【 (1) 计算 1+3+5+ … + (2n – 1)的和 (5分)(2) 基本语句是 Q(n-1) + 2n – 1; (5分)(3) 关于输入规模n的执行次数的递推式：T(n) = T(n-1) + 1, 且 T(1) = 1; T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = T(n-3) + 1 + 1 + 1 = …… = T(1) + 1 + 1 + … + 1 = n (5分)(4) O(n) (5分)
】

3、问题:分析以下程序段中的 (1)输入规模和基本语句，(2)计算基本语句的执行次数T(n)（要求列出计算公式和过程）, (3)最终用大O表示其时间复杂度。for(i=1; i<=n; i++)
for(j=2i; j<=n; j++)
y=y+ij;
评分规则: 【程序段有两层嵌套，影响循环次数的变量是n，因此：(1) 输入规模是n，基本语句是内层循环体中的y=y+ij. （5分）(2)对每一趟外层循环的执行，计算内层循环的循环次数，然后求和。当i=1时，内层循环j从2到n，共执行n-1次；当i=2时，内层循环j从4到n，共执行n-3次；当i=3时，内层循环j从6到n，共执行n-5次；……当i=时，此时具体的循环次数与n的奇偶性有关：若n是偶数，j=2i等于n，内层循环执行1次；若n是奇数，j=2*i等于n-1, 内层循环执行2次；综上，若n是偶数，T(n) = (n-1) + (n-3) + (n-5) + … + 1, 是一个公差为2，共n/2项的等差数列，对其求和，得到T(n) = 。若n是奇数，T(n) = (n-1) + (n-3) + (n-5) + … + 2, 是一个公差为2，共(n-1)/2项的等差数列，对其求和，得到T(n) = （推导过程和结果满分10分，根据正确的比例酌情给分。）(3)根据T(n), 可得到其时间复杂度为O(n^2); （5分）
】

4、问题:扩展以下某递归算法关于输入规模n的递推关系式，求解出T(n)关于n的表达式, 然后用大O表示该算法的时间复杂度。
评分规则: 【 T(n) = 3T(n-1) + 1 = 3 * (3T(n-2) + 1) + 1 = * T(n-2) + 3 + 1 = * ( 3T(n-3) + 1 ) + 3 + 1 = * T(n-3) + + 3 + 1 …… = * T(1) + + … + + 3 + 1 = + + … + + 3 + 1对以上等比数列求和， T(n) = (3^n – 1) / 2（T(n)的最终结果正确得10分，有推导过程再加5分，若过程和结果不完全正确，按比例酌情给分）时间复杂度为 O(3^n). （大O的结果正确得5分）
】