大学MOOC 算法设计与分析（叶威）(武汉纺织大学)1450296610 最新慕课完整章节测试答案

作业测验

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】

作业测验

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:
E:
F:
答案: 【 】

4、单选题：

有n个砝码（其中n为2的幂，即），每个重g克，其中一个不合格(重量可能大于或小于g克). 有一个秤可以称出重物的准确重量. 假设所有的砝码可以同时放到秤上，设计一个算法找出这个不合格的砝码，且秤重的次数达到最少.  采用分治算法，每次取一半砝码（比如t个）称重，如果恰好重tg克，那么不合格的砝码在剩下的砝码中；否则不合格的砝码就在被称重的砝码中. 设n枚砝码的称重次数是T(n)，关于T(n)的递推方程是:

​

​

括号里应该填：

​

‏

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

5、单选题：

‏在之前n个砝码的题目中（其顺序可能出现在该题之后），在初值T(2)=1条件下，确定：对于给定的n个砝码，找到其中不合格砝码最多需要称重多少次，并选择一个函数填入括号内. .

‍选项：
A:
B:
C:
D:
E:
答案: 【