大学MOOC 算法设计与分析(广西科技大学启迪数字学院)1457916172 最新慕课完整章节测试答案
第二周 基础知识（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: