MOOC 算法设计与分析(成都信息工程大学)1457853183 最新慕课完整章节测试答案
第一周 基础知识(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: