2020 算法设计与分析(新疆农业大学) 最新满分章节测试答案

文章目录[隐藏]

【作业】第一周基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界实验习题
第二周基础知识（2）：序列求和方法，递推方程求解作业测验
【作业】第二周基础知识（2）：序列求和方法，递推方程求解实验习题
【作业】第四周分治策略（2）实验项目
第七周贪心法（1）作业测验
【作业】第七周贪心法（1）实验项目

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

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

1、问题:问题描述：一张单据上有一个5位数的编码，因为保管不善，其万位数字和百位数已经变得模糊不清。但是知道这个5位数是57和67的倍数。现在要设计一个算法，输出所有满足这些条件的5位数，并统计这样的数的个数。
评分规则: 【写出能想到的任何方法。对于不同方法求得其消耗时间。上传文件必须为压缩包格式。
】

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

1、问题:递归方程的解的精确值是：
选项：
A:
B:
C:
D:
E:
F:
答案: 【】

2、问题:，的阶是：
选项：
A:
B:
C:
D:
E:
F:
答案: 【】

3、问题:请用主定理确定递归式的渐近的界：
选项：
A:
B:
C:
D:
E:
答案: 【】

4、问题:给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。假设对于个数的数组，在最坏情况下算法A的比较次数是，该算法在最坏情况下的递推方程是：
选项：
A:
B:
C:
D:
E:
F:
答案: 【】

5、问题:给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。假设对于个数的数组，在最坏情况下算法A的比较次数是，则的精确值是？
选项：
A:
B:
C:
D:
E:
F:
答案: 【】

6、问题:把插入排序算法加以改进，可以得到二分插入排序算法。设输入数组是，插入排序算法的基本操作是：假定的前个数已经排好，将插入。插入时从开始，顺序检查，直到找到插入的合适的位置，将它插入。改进插入排序算法的步骤是：插入的操作不是在中从后向前顺序检索，而是采用二分检索方法找到插入的正确位置。如果输入规模是，该算法在最坏情况下的比较次数是，那么该算法在最坏情况下的递推方程是
选项：
A:
B:
C:
D:
E:
答案: 【】

7、问题:在算法分析中，以下关于渐近符号的性质正确的是：
选项：
A:f(n) = (g(n)),g(n) = (h(n))f(n) = (h(n))
B:f(n) = O(g(n)),g(n) = O(h(n))h(n) = Of(n)
C:O(h(n))+ O(g(n)) = O(min{f(n),g(n)})
D:f(n) = O(g(n)) g(n) = O(f(n))