算法设计与分析 中国大学mooc慕课答案满分完整版章节测试

涩朝惟恒堆谰弘蹬卡酪邓虽巢

第一周 基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界 作业测验

1、 考虑下述选择排序算法：最坏情况下该算法做次交换运算，这种情况在下列哪种输入条件下发生？

答案: 数列元素各不相等且递减有序

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

答案:

3、 已知是含有个元素并且从小到大排好序的数组，在中。如果出现在中第个位置的概率是在前一个位置概率的一半，当充分大时，下述查找算法平均情况下的时间复杂度（ ）。（只需给出近似值）

答案: 2

4、 下列哪个排序算法在最坏情况下的时间复杂度最低？

答案: 堆排序

5、 下列有关阶乘函数的表述错误的是？

答案:

6、 与之间的渐近关系是？

答案: 无法确定

7、 以下关于函数阶的关系中，哪几项是正确的？

答案: ;
;
;

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

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

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

第二周 基础知识（2）：序列求和方法，递推方程求解 作业测验

1、 递归方程的解的精确值是：

答案:

2、 ，的阶是：

答案:

3、 请用主定理确定递归式的渐近的界：

答案:

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

答案:

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

答案:

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

答案:

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

答案:

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。下列哪一段代码是利用分治策略给出的正确的移动策略：

答案:

2、 给定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从大到小的次序输出，现有如下算法，算法：调用i次找最大算法Findmax，每次从S中删除一个最大的数。该算法在最坏情况下的时间复杂度是：

答案:

3、 给定n个不同数的数组S和正整数i，，求S中最大的i个数，并且按照从大到小的次序输出，现有如下算法，算法：对S排序，并输出S中最大的i个数。该算法在最坏情况下的时间复杂度是：

答案:

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

答案:

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

答案:

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

答案: 1

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

答案:

第四周 分治策略（2） 作业测验

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

答案: d, c, a, b

2、 设信号向量是 ，，用于平滑处理的权向量是，根据卷积计算公式，处理后的信号向量是，那么的值分别为( )，从下面的项中选择合适的答案：

答案: 4.1，5.8，5.5

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

答案: a, b, c

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

答案:

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

答案:

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

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

第五周 动态规划（1） 作业测验

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

答案: 36000

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

答案: 或者是序列A的第一个数，或者它前面的数都比它大

3、 在第2题中，设算法输入的实例是A=<2,8,4,-4,5,9,11>，那么 的值是：

答案: 1, 2, 2, 1, 3, 4, 5

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

答案:

5、 在第4题中，从问题本质看，任务的加工时间相当于0-1背包问题中的下述输入参数：

答案: 既是物品i的价值，也是它的重量

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

答案:

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

答案: 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 可以连通到 b,c,d;b 可以连通到 c,d;c 可以连通到 d;d 可以连通到 c