算法设计中国大学mooc答案公众号

第一周 基础知识（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、

4、下列哪个排序算法在最坏情况下的时间复杂度最低？
    A、插入排序
    B、堆排序
    C、冒泡排序
    D、快速排序

5、下列有关阶乘函数的表述错误的是？
    A、
    B、
    C、
    D、
    E、

6、与之间的渐近关系是？
    A、
    B、
    C、
    D、无法确定

7、以下关于函数阶的关系中，哪几项是正确的？
    A、
    B、
    C、
    D、
    E、
    F、

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

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

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

第二周 基础知识（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具有更高的效率，即时间复杂度的阶低于的阶的最大正整数的值为：

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

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

第三周 分治策略（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、
    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、

6、设问题P的输入规模是n，下述三个算法是求解P的不同的分治算法. 算法1：在常数时间将原问题划分为规模减半的5个子问题，递归求解每个子问题，最多用线性时间将子问题的解综合而得到原问题的解. 算法2：先递归求解2个规模为n-1的子问题，最多用常量时间将子问题的解综合得到原问题的解. 算法3：在常数时间将原问题划分为规模n/3的9个子问题，递归求解每个子问题，最多用时间将子问题的解综合得到原问题的解. 要求在上述三个算法中选择最坏情况下时间复杂度最低的算法，需要选择哪个算法？
    A、1
    B、2
    C、3
    D、都不对

7、设问题P的输入规模是n，下述三个算法是求解P的不同的分治算法. 算法1：在常数时间将原问题划分为规模减半的5个子问题，递归求解每个子问题，最多用线性时间将子问题的解综合而得到原问题的解. 算法2：先递归求解2个规模为n-1的子问题，最多用常量时间将子问题的解综合得到原问题的解. 算法3：在常数时间将原问题划分为规模n/3的9个子问题，递归求解每个子问题，最多用时间将子问题的解综合得到原问题的解. 设最坏情况下时间复杂度最低的算法为A，A在最坏情况下的时间复杂度是
    A、
    B、
    C、
    D、
    E、

第四周 分治策略（2）

作业测验

1、给定含有n个不同的数的数组。如果L中存在，则称L是单峰的，并称是L的“峰顶”。假设L是单峰的，请把a-d四行代码补全到算法中使得算法正确找到L的峰顶。 。
    A、d, c, a, b
    B、d, c, b, a
    C、c, d, b, a
    D、d, b, c, a
    E、d, a, b, c

2、设信号向量是 ， ，用于平滑处理的权向量是，根据卷积计算公式，处理后的信号向量是，那么的值分别为( )，从下面的项中选择合适的答案：
    A、4.1，5.8，5.5
    B、2.2，8.4，3.2
    C、4.7，4.3，7.7
    D、0.4，3.2，0.6

3、在枚硬币中有一枚质量不合格的硬币(质量过轻或质量过重)，如果只有一架天平可以用来称重且称重的硬币数没有限制，下面是一个算法找出这枚不合格的硬币，每称1次作为1次基本运算。请把a,b,c三行代码填到算法中正确的位置中。
    A、c, a, b
    B、c, b, a
    C、a, b, c
    D、b, a, c
    E、b, c, a

4、设 T是n个不等的数构成的数组，现在用分治算法找T的最大数. 先把T从中间划分成两个大小差不多的子数组和，递归地求 和的最大数，分别记作和. 比较和，那么输出就是. 以元素比较做基本运算，该算法在最坏情况下的时间复杂度的的递推方程是：
    A、
    B、
    C、
    D、

5、找第k小问题的分治算法. 算法开始将n个数分成5个1组，共个组，然后取每组的中位数构成集合M，递归利用找第k小算法，计算M的中位数，用作为标准划分数组，得到子问题和. 递归求解其中一个子问题即可. 如果开始分组时是3个元素一组，算法在最坏情况下的时间复杂度将达到，如果开始分组时取7个元素一组，那么用划分数组后产生的子问题最大规模将达到（ ），算法在最坏情况下的时间复杂度是（ ），两个括号里分别应该填：
    A、
    B、
    C、
    D、

6、 针对表1给定的六个算法的时间复杂度T(n)，从表2中选择关于T(n)的正确的递推方程，并将方程所对应的标号a,b,c,d,e,f按照算法一、二、三、四、五、六的顺序填入括号内（填写时6个字母之间不要加任何符号）。

7、 针对表1给定的六个算法的时间复杂度T(n)，从表2中选择关于T(n)的正确的递推方程，从表3中选择正确的解，并将解所对应的标号1,2,3,4,5按照算法一、二、三、四、五、六的顺序填入括号内（填写时6个数字之间不要加任何符号）.