大学MOOC 算法设计与分析(武汉设计工程学院)1449997188 最新慕课完整章节测试答案

作业测验

1、单选题：

‏考虑下述选择排序算法：

‌

‏

‌

‏最坏情况下该算法做次交换运算，这种情况在下列哪种输入条件下发生？

‌

‏

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

2、单选题：

​

​

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

​选项：
A:
B:
C:
D:
E:
F:
答案: 【 】

3、单选题：
‎下列有关阶乘函数的表述错误的是？‍
选项：
A:
B:
C:
D:
E:
答案: 【 】

4、单选题：
‌算法是由若干条指令组成的有穷序列，而且满足的性质有________。‌(1)输入：有1个或多个输入‌(2)输出：可以有0个输出‌(3)确定性：指令清晰，无歧义‌(4)有限性：指令执行次数有限，而且执行时间有限‌
选项：
A:

  

B:

C:

   

D:

答案: 【 
】

5、单选题：
函数32n+10nlogn的渐进表达式是     。 ‌
选项：
A:

B:
C:
D:
答案: 【 】

6、多选题：
‍以下关于函数阶的关系中，哪几项是正确的？‍
选项：
A:
B:
C:
D:
E:
F:
答案: 【 ;
;
;
】

7、填空题：

‎下表给出组和函数，

使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")

‎答案: 【 24】

8、填空题：

​下表给出组和函数，

使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")

‌答案: 【 1235】

9、填空题：

‏下表给出组和函数，

使得成立的组号（从小到大排列）是：(请直接填写数字序号，例如顺序为，则填写"")

​答案: 【 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、填空题：

把插入排序算法加以改进，可以得到二分插入排序算法。设输入数组是