2021 算法分析与设计(西南科技大学)1465494465 最新满分章节测试答案

分类：每周周末更新, 网课答案
标签： MOOC答案, 网课小帮手, 网课答案

第一章算法及问题求解过程第一章单元测试
【作业】第一章算法及问题求解过程第一章单元作业
第二章算法效率分析基础第二章单元测验
【作业】第二章算法效率分析基础第二章单元作业
第三章蛮力法第三章单元测验
【作业】第三章蛮力法第三章单元作业
第四章减治法第四章单元测试
【作业】第四章减治法第四章单元作业
第五章分治法第五章单元测验
第六章变治法第六章单元测试
第七章时空权衡第七章单元测试
第八章动态规划第八章单元测验
第九章第九章单元测验
第十章第十章单元测验
第十一章第十一章单元测验

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

第一章算法及问题求解过程第一章单元测试

1、问题:下面哪一个不是算法的特性？（）
选项：
A:输入
B:正确性
C:有穷性
D:及时性
答案: 【及时性】

2、问题:利用欧几里得算法计算12、8的最大公约数，只需要循环多少次？（）
选项：
A: 1次
B:2次
C: 3次
D:4次
答案: 【2次】

3、问题:下面为代码的描述，哪一个是错误的？（）
选项：
A: if a≠b
B: for(i=0;i<n;i++)
C:while i<n do
D:bß12
答案: 【 for(i=0;i<n;i++)】

4、问题:下面为代码的描述，哪一个是错误的？（）
选项：
A:if a=b
B:A[i]=j
C: for pß2 to n do
D: while b!=12
答案: 【 while b!=12】

5、问题:对算法运行速度的效率分析主要是指（）
选项：
A:时间效率分析
B:空间效率分析
C:简单性分析
D:一般性分析
答案: 【时间效率分析】

【作业】第一章算法及问题求解过程第一章单元作业

1、问题: 请估算一下用欧几里得算法求gcd(31415,14142)是用连续整数检测法的多少倍？
评分规则: 【 gcd(31415,14142) = gcd(14142,3131) = gcd(3131,1618) = gcd(1618,1513) = gcd(1513,105) = gcd(1513,105) = gcd(105,43) = gcd(43,19) = gcd(19,5) = gcd(5,4) = gcd(4,1) = gcd(1,0) = 1可见，欧几里得算法共做了11次除法，最大公约数是1。而连续整数检测法需要做14142次迭代，在迭代过程中做了114142次和214142次除法，因此欧几里得算法大概快了114142/111300倍，和214142/112600倍。
】

2、问题:请用伪代码写一个算法来求取方程ax^2+bx+c=0的实根，a，b，c是任意实系数。
评分规则: 【 Algorithm Quadratic(a,b,c)//The algorithm finds real roots of equation ax^2 + bx + c = 0//Input: Real coefficients a,b,c//Output: The real roots of the equation or a message about their absence if a 0 D bb-4ac if D > 0 temp 2a x1 (-b+sqer(D))/temp x2 (-b-sqer(D))/temp return x1,x2 else if D = 0 return -b/(2*a) else return ‘no real roots’else // a = 0 if b 0 return -c/b else //a=b=0 if c = 0 return ‘all real numnbers’ else return ‘no real roots’
】

3、问题:请用伪代码写出将十进制转换为二进制整数的标准算法。
评分规则: 【 ALgorithm Binary(n)//The algorithm implements the standard method for finding //the binary expansion of a positive decimal integer//Input: A positive decimal integer n//Output: The list bk bk-1 … b1 b0 of n’s binary digitsk←0while n!=0 bk ← mod 2 n ← [n/2] k ← k +1
】

第二章算法效率分析基础第二章单元测验

1、问题:算法分析中，算法运行时间的度量单位是：
选项：
A:秒
B:分
C:小时
D:基本操作被执行的次数
答案: 【基本操作被执行的次数】

2、问题:下列对算法效率的描述错误的是：
选项：
A:最优效率是指输入为n时，算法在最优情况的效率。
B:平均效率是指输入为n时，算法在随机获典型输入情况的效率。
C:平均效率是指输入为n时，算法在最坏情况的效率。
D:最差效率是指输入为n时，算法在最坏情况的效率。
答案: 【平均效率是指输入为n时，算法在最坏情况的效率。】

3、问题:针对下面的算法，描述错误的是：（）算法 SequentiaSearch(A[0..n-1],K) iß0 while i<n and A[i] ≠K ißi+1 if i<n return i else return -1
选项：
A:算法的基本操作时比较运算。
B:算法的基本操作时循环最内层的加法。
C:算法在最优情况下只需要做一次元素的比较。
D:算法在查找不成功的情况下，最优需要做n次元素比较。
答案: 【算法的基本操作时循环最内层的加法。】

4、问题:下面哪一个不是时间的渐进符号：
选项：
A:O
B:Ω
C:Y
D:Θ
答案: 【Y】

5、问题:下面那个断言是错误的：
选项：
A:
B:
C:
D:
答案: 【】

6、问题:考虑下面这个式子属于哪一种效率类型：
选项：
A:
B:
C:
D:
答案: 【】

7、问题:以下式子属于哪一种效率类型。
选项：
A:
B:
C:
D:
答案: 【】

【作业】第二章算法效率分析基础第二章单元作业

1、问题:阅读下面的算法后回答问题。算法 Secret(A[0..n-1]) minval ßA[0] maxvalßA[0] for iß1 to n-1 do if A[i]<minval minval ßA[i] if A[i]>maxval maxval ßA[i] return maxval-minvala）该算法求的是什么？b）它的基本操作是什么？c）该基本操作执行了多少次？d）该算法的效率类型是什么？
评分规则: 【 1
】

2、问题:以下算法是某个重要算法的一个版本，阅读后请求出该算法的时间效率，同时分析该算法有哪些重要缺陷，该如何弥补。算法 GE(A[0..n-1,0..n-1]) for iß0 to n-2 do for jßi+1 to n-1 do for kßn downto i do A[j,k]ßA[j,k]-A[I,k]*A[j,i]/A[I,i]
评分规则: 【时间效率是.循环最内层的除法可以放到外一层。
】

3、问题:求解下列递归关系a) x(n)=x(n-1)+5 其中n>1，x(1)=0b) x(n)=3x(n-1) 其中n>1，x(1)=4c) x(n)=x(n-1)+n 其中n>0，x(0)=0d) x(n)=x(n/2)+n 其中n>1，x(1)=1（对于n=2k的情况来解）
评分规则: 【 a) 5(n-1)b) c) d) 2n-1
】

4、问题:考虑下面的递归算法，然后回答问题。算法 Riddle(A[0..n-1]) if n=1 return A[0] else temp ßRiddle(A[0..n-2]) if temp≤A[n-1] return temp else return A[n-1]a) 该算法计算的是什么？b) 建立该算法所做的基本操作次数的递推关系并求解。
评分规则: 【 a)找出所给数组中的最小值。b) C(n)=C(n-1)+1 for n>1, C(1)=0
】

第三章蛮力法第三章单元测验

1、问题:采用蛮力法求解凸包问题的算法复杂度为：()
选项：
A:
B:
C:O(n!)
D:O(n)
答案: 【】

2、问题:用蛮力法思路求解旅行商问题的算法复杂度为：()
选项：
A:O(n!)
B:O(n^3)
C:O(n^2)
D:O(n)
答案: 【O(n!)】

3、问题:用蛮力法思路求解任务分配问题的算法复杂度为:()
选项：
A:
B:
C:O(n!)
D:O(n)
答案: 【O(n!)】

4、问题:以下关于蛮力法的描述中，正确的有()
选项：
A:较为通用，能解决一般领域的问题
B:适用于小规模问题
C:可作为产生其他有效算法的基础
D:可作为其他有效算法的衡量标准
答案: 【较为通用，能解决一般领域的问题;
适用于小规模问题;
可作为产生其他有效算法的基础;
可作为其他有效算法的衡量标准】

5、问题:以下关于深度优先查找的说法，正确的包括：()
选项：
A:数据结构采用栈
B:数据结构采用队列
C:采用邻接矩阵的效率为O(||)
D:采用邻接矩阵的效率为O(|V|+|E|)
答案: 【数据结构采用栈;
采用邻接矩阵的效率为O(||)】