算法设计与分析（包翠竹）(浙江工商大学) 中国大学慕课答案2024完整版100分

对应课程:点击查看
起止时间:2020-02-25到2020-07-30
更新状态:已完结

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

1、 考虑下述选择排序算法：最坏情况下该算法做次交换运算，这种情况在下列哪种输入条件下发生？

A:数列元素各不相等且递增有序
B:数列元素各不相等且递减有序
C:数列元素各不相等且无序
D:数列所有元素均相等
E:数列中有相同元素且递增（不减）有序
F:数列中有相同元素且递增（不减）有序
答案: 数列元素各不相等且递减有序

2、 上述算法所执行的加法次数是：

A:
B:
C:
D:
E:
F:
答案:

3、 已知是含有个元素并且从小到大排好序的数组，在中。如果出现在中第个位置的概率是在前一个位置概率的一半，当充分大时，下述查找算法平均情况下的时间复杂度（ ）。（只需给出近似值）

A:2
B:3
C:4
D:1
E:
F:
G:
答案: 2

4、 下列哪个排序算法在最坏情况下的时间复杂度最低？

A:插入排序
B:堆排序
C:冒泡排序
D:快速排序
答案: 堆排序

5、 下列有关阶乘函数的表述错误的是？

A:
B:
C:
D:
E:
答案:

6、 与之间的渐近关系是？

A:
B:
C:
D:无法确定
答案: 无法确定

7、 以下关于函数阶的关系中，哪几项是正确的？

A:
B:
C:
D:
E:
F:
答案: ;
;
;

8、 下表给出组和函数，使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写”“)
答案: 24

9、 下表给出组和函数，使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写”“)
答案: 1235

10、 下表给出组和函数，使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写”“)
答案: 2

第二周 基础知识（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:
B:
C:
D:
E:
F:
答案:

8、 设递推方程给出了算法A在最坏情况下的时间复杂度函数，算法B在最坏情况下的时间复杂度函数满足递推方程，那么要使算法B比算法A具有更高的效率，即时间复杂度的阶低于的阶的最大正整数的值为：
答案: 48

9、 给定个数的数组，其中，为非负整数，求中的最大数. 考虑下述算法A，先把数组从中间划分成两个个数的数组和，在和中用同样的算法通过数之间的比较运算找最大数，如果的最大数是,的最大数是,那么就是问题的解。假设对于个数的数组，在最坏情况下算法A的比较次数是，则的初值是（ ）？
答案: 0

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

第三周 分治策略（1） 作业测验

1、 双Hanoi塔问题是Hanoi塔问题的一种推广，与Hanoi塔的不同点在于：2n个圆盘，分成大小不同的n对，每对圆盘完全相同。初始，这些圆盘按照从大到小的次序从下到上放在A柱上，最终要把它们全部移到C柱，移动的规则与Hanoi塔相同。BiHanoi(A, C, n)的功能是从A移动2n个盘子到C，其中BiMove(A, C)表示从A移动两个盘子到C。下列哪一段代码是利用分治策略给出的正确的移动策略：

A:
B:
C:
D:
答案:

2、 给定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从大到小的次序输出，现有如下算法，算法：调用i次找最大算法Findmax，每次从S中删除一个最大的数。该算法在最坏情况下的时间复杂度是：

A:
B:
C:
D:
E:
答案:

3、 给定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从大到小的次序输出，现有如下算法，算法：对S排序，并输出S中最大的i个数。该算法在最坏情况下的时间复杂度是：

A:
B:
C:
D: