2020 计算机常用算法(李向新)(昆明理工大学) 最新满分章节测试答案

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

【作业】第一周 基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界 第一周作业

1、 问题:1.什么是算法？
评分规则: 【 参考视频中相关章节并回答
】

2、 问题:2.算法设计与分析包含哪些内容？
评分规则: 【 参考学习视频相关章节内容，简要回答。
】

3、 问题:3. 如何描述算法的复杂度？
评分规则: 【 参考学习视频相关内容，简要回答。
】

4、 问题:4.算法的时间复杂度指的是什么？
评分规则: 【 参考学习视频，简要回单。
】

5、 问题:5.算法的伪码是什么？
评分规则: 【 参考学习视频，简要回答。
】

6、 问题:6.函数渐进的界中O(n^2)的含义是什么？
评分规则: 【 参考学习内容，简要回答。
】

【作业】第二周 基础知识（2）：序列求和方法，递推方程求解 第二周作业

1、 问题:在计算有关迭代过程的算法的时间复杂度时经常用到的计算方法是什么？
评分规则: 【 序列求和的方法。
】

2、 问题:序列求和的基本公式有哪些？
评分规则: 【 1）等比级数 2）等差级数 3）调和级数
】

3、 问题:什么是递推方程？
评分规则: 【 设序列a0,a1,…,an,…, 简记为{an}，一个把an与某些个ai(i】

4、 问题:递推方程的求解方法有哪些？
评分规则: 【 迭代法是求解递推方程的基本方法。另外还有换元迭代法、差消法化简高阶递推法、递归树法、主定理法。
】

5、 问题:迭代法求解递推方程的步骤有哪几步？
评分规则: 【 1）不断用递推方程的右部替代左部2）每次替换，随着n的降低，在和式中多出一项3）直到出现初值停止迭代4）将初值带入并对和式求解 5）可用数学归纳法验证解的正确性
】

6、 问题:什么是换元迭代？
评分规则: 【 递推方程直接迭代比较困难时，我们就要进行换元，把关于n的递推式，转换成对其他变量k的递推式，然后对k的递推是进行迭代，迭代以后得到解后，再把关于k的函数转换成关于n的函数，这就是换元迭代。
】

7、 问题:为什么要使用差消法化简高阶递推方程？
评分规则: 【 对于高阶的递推方程，求解比较麻烦，需要用差消法将高阶的递推方程化简为一阶的方程，然后进行迭代求解。
】

8、 问题:.递归树及其的生成规则是什么？
评分规则: 【 递归数是迭代过程的图形表示。 递归树的生成过程与迭代过程一致。归树的生成规则是用递归方程的右部表达成一个二层的子树来不断替换左部，递归树上的所有项的和就是迭代后方程的解。
】

9、 问题:序列和的估算方法有那些？
评分规则: 【 1）放大法求上界 2）用积分做和式的渐进的界
】

10、 问题:递归树求解递推方程有什么优点？
评分规则: 【 递归树的求解表示，比一般的迭代更加简洁，更加的清晰。
】

【作业】第三周 分治策略（1） 第三周作业

1、 问题:分治策略的基本思想是什么？
评分规则: 【 参考学习视频和课件完成。
】

2、 问题:分治算法的适用条件是什么？
评分规则: 【 参考学习视频和课件完成
】

3、 问题:分治算法包括哪几个步骤？
评分规则: 【 参考视频及课件内容
】

4、 问题:改进分治算法的途径有哪几种？
评分规则: 【 参看视频和课件完成
】

【作业】第四周 分治策略（2） 单元作业

1、 问题:典型的分治算法能应用于些问题？
评分规则: 【 参考学习视频及课件
】

2、 问题:采用分治算法时，选最大最小的时间复杂度W(n)为多少？
评分规则: 【 参考学习视频和课件
】

3、 问题:给定向量 a = (a0, a1, …, an-1) ，b = (b0, b1, …, bn-1)。写出向量和a+b、内积a·b、卷积a*b的计算公式。
评分规则: 【 参考学习视频和课件
】

4、 问题:什么是平面点集的凸包问题？能应用于哪些图形处理问题？
评分规则: 【 参考学习视频和课件
】

5、 问题:用分治算法求解平面点集的凸包分哪几个步骤？
评分规则: 【 参考学习视频和课件
】

【作业】第五周 动态规划（1） 第五周单元作业

1、 问题:什么是最短路径问题？
评分规则: 【 参考视频学习资料
】

2、 问题:动态规划算法的基本思想是什么？适用条件是什么？