算法设计与分析（包翠竹）答案-中国大学慕课

第一周 基础知识（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个数字之间不要加任何符号）.

第五周 动态规划（1）

作业测验

1、考虑考虑矩阵链相乘问题，假设给定的输入实例是 , 根据动态规划算法，备忘录中的 等于
    A、60000
    B、36000
    C、3000
    D、30000
    E、3000

2、设 是n个不等的整数构成的序列，A的一个单调递增子序列是序列 使得 ，且 。子序列 的长度是含有的整数个数k。例如 ，它的长度为4的递增子序列是： ， ，...请使用动态规划算法求A的一个最长的单调递增子序列。设 表示以 作为最后项的最长单调递增子序列的长度，那么 ，如果在 前面有项 使得 如果 ，那么一定有：
    A、
    B、
    C、
    D、

3、在第2题中，设算法输入的实例是 ，那么 的值是：
    A、1, 2, 2, 1, 3, 3, 5
    B、1, 2, 2, 0, 3, 4, 5
    C、1, 2, 2, 1, 3, 4, 5
    D、1, 2, 1, 2, 2, 3, 4

4、设有n项任务，加工时间分别表示为正整数 。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令 那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。 假设问题的解是 ，其中 . 如果 ，那么第i项任务放到第一台机器上加工；如果 ，那么第i项任务放到第二台机器上加工。把这个问题描述成组合优化问题，那么它的目标函数是：
    A、
    B、
    C、
    D、

5、在第4题中，从问题本质看，任务的加工时间相当于0-1背包问题中的下述输入参数：
    A、既是物品i的价值，也是它的重量
    B、仅代表物品i的价值
    C、仅代表物品i的重量
    D、物品i单位重量的价值

6、考虑上述双机调度问题.令 表示考虑前k项任务，在第一台机器时间不超过y的情况下其加工时间的最大值. 那么
    A、
    B、
    C、
    D、

7、在第6题中，给定双机调度问题的实例如下： 假设第一条机器的完成时间不超过T，那么该实例有______个解
    A、0
    B、1
    C、2
    D、3
    E、4

8、一个有向图D由顶点集V和边集E构成。如果D有n个顶点，那么顶点集为 ，如果在D中从 到 有一条有向边，那么 属于E。有向图D可以用一个n行n列的0-1矩阵M来表示。如果D中的 到 有一条有向边，那么矩阵M的第i行第j列元素；否则 。图的连通性是指从图的某些顶点到其他顶点存在一条由连续有向边构成的路径。一个著名的检查图的连通性的算法就是Warshall算法。假设M是图D的矩阵表示，考虑n+1个矩阵构成的序列 将矩阵 的i行j列元素记作 。对于 当且仅当图中存在一条从 到 的路径，并且这条路径除端点外中间只经过 中的顶点。不难看出 就是M，而在 中如果 ，则说明D中 和 是连通的。Warshall算法从 开始，顺序计算 ,直到 为止。可以通过动态规划的迭代实现Warshall算法，用以下实例作为输入，给出实例的结果。假设某有向网络的结点是a,b,c,d，已知网络的矩阵表示是：
    A、a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
    B、a 可以连通到 b,c,d;b 可以连通到 c;c 可以连通到 d;d 可以连通到 c
    C、a 可以连通到 b,c;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
    D、a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 b,d;d 可以连通到 c

作业测验

1、考虑考虑矩阵链相乘问题，假设给定的输入实例是 , 根据动态规划算法，备忘录中的 等于
    A、60000
    B、36000
    C、3000
    D、30000

2、设 是n个不等的整数构成的序列，A的一个单调递增子序列是序列 使得 ，且 。子序列 的长度是含有的整数个数k。例如 ，它的长度为4的递增子序列是： ， ，...请使用动态规划算法求A的一个最长的单调递增子序列。设 表示以 作为最后项的最长单调递增子序列的长度，那么 ，如果在 前面有项 使得 如果 ，那么一定有：
    A、
    B、
    C、
    D、

3、在第2题中，设算法输入的实例是 ，那么 的值是：
    A、1, 2, 2, 1, 3, 3, 5
    B、1, 2, 2, 0, 3, 4, 5
    C、1, 2, 2, 1, 3, 4, 5
    D、1, 2, 1, 2, 2, 3, 4

4、设有n项任务，加工时间分别表示为正整数 。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令 那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。 假设问题的解是 ，其中 . 如果 ，那么第i项任务放到第一台机器上加工；如果 ，那么第i项任务放到第二台机器上加工。把这个问题描述成组合优化问题，那么它的目标函数是：
    A、
    B、
    C、
    D、

5、设有n项任务，加工时间分别表示为正整数 。现有2台同样的机器，从0时刻可以安排对这些任务的加工。规定只要有待加工的任务，任何机器就都不得闲置。如果直到时刻t所有任务都完成了，总的加工时间就等于t。设计一个算法找到使得总加工时间t达到最小的调度方案。令 那么存在一个最优调度使得第一台机器上总加工时间不超过T，且达到最大. 该问题称为双机调度问题。 假设问题的解是 ，其中 . 如果 ，那么第i项任务放到第一台机器上加工；如果 ，那么第i项任务放到第二台机器上加工。 从问题本质看，任务的加工时间相当于0-1背包问题中的下述输入参数：
    A、既是物品i的价值，也是它的重量
    B、仅代表物品i的价值
    C、仅代表物品i的重量
    D、物品i单位重量的价值

6、考虑上述双机调度问题.令 表示考虑前k项任务，在第一台机器时间不超过y的情况下其加工时间的最大值. 那么
    A、
    B、
    C、
    D、

7、在第6题中，给定双机调度问题的实例如下： 假设第一条机器的完成时间不超过T，那么该实例有______个解
    A、0
    B、1
    C、2
    D、3
    E、4

8、一个有向图D由顶点集V和边集E构成。如果D有n个顶点，那么顶点集为 ，如果在D中从 到 有一条有向边，那么 属于E。有向图D可以用一个n行n列的0-1矩阵M来表示。如果D中的 到 有一条有向边，那么矩阵M的第i行第j列元素；否则 。图的连通性是指从图的某些顶点到其他顶点存在一条由连续有向边构成的路径。一个著名的检查图的连通性的算法就是Warshall算法。假设M是图D的矩阵表示，考虑n+1个矩阵构成的序列 将矩阵 的i行j列元素记作 。对于 当且仅当图中存在一条从 到 的路径，并且这条路径除端点外中间只经过 中的顶点。不难看出 就是M，而在 中如果 ，则说明D中 和 是连通的。Warshall算法从 开始，顺序计算 ,直到 为止。可以通过动态规划的迭代实现Warshall算法，用以下实例作为输入，给出实例的结果。假设某有向网络的结点是a,b,c,d，已知网络的矩阵表示是：
    A、a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
    B、a 可以连通到 b,c,d;b 可以连通到 c;c 可以连通到 d;d 可以连通到 c
    C、a 可以连通到 b,c;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c
    D、a 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 b,d;d 可以连通到 c

第六周 动态规划（2）

作业测验

1、设P是一台Internet上的Web服务器。 是n个下载请求的集合， 表示下载请求i所申请的带宽。已知服务器的最大带宽是正整数K。我们的目标是使带宽得到最大限度的利用，即确定T的一个子集S，使得 ，且 的值达到最小。类似于0-1背包问题，令 表示考虑前i个申请，带宽限制为y时的最大带宽使用量，则有如下递推式：
    A、d,a,c,b,d
    B、d,a,b,b,c
    C、c,b,c,b,d
    D、c,a,b,a,d
    E、c,a,b,b,d

2、找零钱问题： 设有面值为 的n种货币，需要付款的总钱数为M，其中 和M都是正整数。问如何付款使得所付货币张数最少？ 设 分别表示付款时使用第i种货币的张数，用组合最优化方法描述该问题，约束条件是 ，其中 定义函数 表示使用前k种币值总钱数为y时所使用钱币的最少张数, 定义函数 表示使用后k种币值总钱数为y时所使用钱币的最少张数, 那么该问题的目标函数是：
    A、
    B、
    C、
    D、

3、考虑找零钱问题, 设 表示使用前k种币值总钱数为y时所使用钱币的最少张数，则 横线上应该填：
    A、
    B、
    C、
    D、
    E、

4、第4题中所给的算法的时间复杂度是：
    A、
    B、
    C、
    D、
    E、

5、二维0-1背包问题：给定n种物品和一个背包。物品i的重量是 ，体积是 ，价值为 ，每种物品只有1个。背包的重量限制为W，容积限制为V。问如何选择装入背包的物品，使得背包物品的总价值最大？ 设 表示使用前i种物品、背包重量限制为j、容积为k时的最大价值，其中 那么递推方程是：
    A、
    B、
    C、
    D、

6、考虑上述第6题中的二维0-1背包问题，动态规划算法的时间复杂度是：
    A、
    B、
    C、
    D、
    E、

7、有正实数构成的数字三角形排列形式如图所示. 第一行的数为 ；第二行的数从左到右依次为 第n行的数为 .从 开始，每一行的数 只有两条边可以分别通向下一行的两个数 和 . 用动态规划算法找出一条从 向下通到 中某个数的路经，使得该路经上的数之和达到最大. 令 是从 到 的路径上的数的最大和，则
    A、
    B、
    C、
    D、

8、第8题中所述算法的时间复杂度是：
    A、
    B、
    C、
    D、
    E、

9、用动态规划算法求解 和 的一个最长公共子序列（LCS），标记函数的表B[i,j]如下表所示： 该实例的解是(顺序从前到后给出最长公共子序列的字符,字符之间不要加任何符号)

第七周 贪心法（1）

作业测验

1、设有n个顾客同时等待一项服务，顾客i需要的服务时间为 。从时刻0开始安排服务。一个顾客的等待时间从时刻0开始计时，直到完成对他服务的时刻为止。问应该怎样安排n个顾客的服务次序使得总的等待时间（每个顾客等待时间的总和）最少？ 针对以上问题，请补全下面贪心算法： 横线上分别应该填：
    A、
    B、
    C、
    D、

2、在第一题中，如果安排服务的顺序是 其中 是 的某个排列，那么总的等待时间是：
    A、
    B、
    C、
    D、
    E、

3、第一题中算法最坏情况下的时间复杂度为：
    A、
    B、
    C、
    D、
    E、

4、设有一条边远山区的道路AB，沿着道路AB分布着n所房子。这些房子到A的距离分别是 。为了给所有房子的用户提供移动电话服务，需要在这条道路上设置一些基站。为了保证通信质量，每所房子应该位于距离某个基站4km范围之内。设计一个算法找到基站的位置，并且使得基站总数达到最少。下面哪一个算法可以得出正确的解：
    A、
    B、
    C、
    D、

5、有n个进程 。对于 进程i的开始时间为 ，截止时间为 。可以通过监测程序Test来测试正在运行的进程。Test每次测试时间很短，可以忽略不计。换句话说，如果Test在时刻t进行测试，那么它将对满足 的所有进程 同时取得测试数据。假设最早运行的进程的开始时间是0，问：如何安排测试时刻，使得对每个进程至少测试一次，且Test测试的次数达到最少？请补全下面贪心算法。
    A、
    B、
    C、
    D、
    E、

6、有n个文件存在磁带上，从单元1开始存储，每个文件占用连续的空间。已知第i个文件需要的存储空间为 ，被检索的概率是 检索每个文件需要从磁带的开始位置进行操作，例如文件i存储在磁带的第100到第250单元，那么检索该文件需要的时间是250。假设n个文件的排列顺序是 以扫描单元数作为时间复杂度的度量，这些文件的平均检索时间是：
    A、
    B、
    C、
    D、

7、用贪心法求解上述文件检索问题，贪心策略是：
    A、按照比值 从大到小对文件重新排序为 ，然后按照 的顺序将文件存入磁带
    B、按照文件被检索的概率 从大到小对文件重新排序为 ，然后按照 的顺序将文件存入磁带
    C、按照文件被检索的概率 从大到小对文件重新排序为 ，然后按照 的顺序将文件存入磁带
    D、按照乘积 从大到小对文件重新排序为 然后按照 的顺序将文件存入磁带