中国大学MOOC硕士生算法设计与分析答案

1、递归函数的要素是递归方程和（）
A、约束条件
B、边界条件
C、输入
D、输出
答案：对

2、递归一般用于解决的问题有（）
A、数据的定义是按递归定义的
B、问题解法按递归实现
C、数据的结构形式是按递归定义的
D、贪心问题
答案：数据的定义是按递归定义的;
问题解法按递归实现;
数据的结构形式是按递归定义的

3、递推是从小规模的问题推解出大规模间题的一种方法，是选代算法的最基本的表现形式。
答案：对

4、递归与循环都是解决“重复操作”的机制
答案：每个递归算法原则上总可以转换成与它等价的迭代算法

5、递归的效率高于递推
答案：×

6、每个递归算法原则上总可以转换成与它等价的迭代算法；反之不然 。
答案：正确

1、使用递推关系求解问题的常用方法有（）
A、递归
B、正推
C、倒推
D、迭代
答案：（1） 最速下降法（梯度法）（2） 共轭梯度法（3） 牛顿法（4） 变尺度法（DFP法）（5） 坐标轮换法（6） 鲍威尔法（Powell法）第8章

2、倒推法是从后向前推解问题的方法.
答案：对

3、不知前提条件的情况下，经常使用倒推求解问题。
答案：员工强烈要求解决他们的薪资待遇问题

4、由结果倒过来推解前提条件是倒推方法的一种
答案：正确

5、由于存储的要求从后向前进行推算是倒推方法的一种
答案：

1、迭代法分为（ ）
A、直接迭代
B、差消迭代
C、换元迭代
D、分元迭代
答案：直接迭代;
差消迭代;
换元迭代

2、求解递推方程的方法有（）
A、迭代法
B、递归树
C、归纳法
D、主定理
答案：迭代法;
递归树;
归纳法;
主定理

3、主方法可以求解满足T(n)=aT(n/b) + f (n) 形式的递推方程， 则下列关于方程正确的是？ A 对于系数a，必须满足a>=1 B对于系数b，必须满足b>1 C若对于常数ε>0，f(n)=O(nlogba-ε)，则T(n)=Θ(nlogba) D若f(n)=O(nlogba)，则T(n)=Θ(nlogbalogn)
A、对于系数a，必须满足a>=1
B、对于系数b，必须满足b>1
C、若对于常数ε>0，, 则
D、若,则
答案：若f(n)=O(nlogba)，则T(n)=Θ(nlogbalogn)

4、迭代法从原始递推方程出发，反复将对应方程左边的函数用右边等式带入，直至得到初值，然后将所得的结果化简。
答案：正确

5、迭代一般用于一阶递推方程，高阶方程需要使用差消法化简为一阶方程求解
答案：对

6、快速排序平均情况下的时间复杂度是O（nlogn）
答案：正确

1、实现下面POJ题目之一，上传代码和AC截图。 1）递推 POJ 1942 2）递归 POJ 2083 3）约瑟夫 POJ 2244 3517 1012
答案：

1、给定男孩和女孩的两张喜欢列表，GS算法的结果对（ ）是最好的选择。
A、男孩
B、女孩
C、男孩或女孩
D、男孩和女孩
答案：男孩

2、稳定匹配问题的输出是（ ）
A、完美匹配
B、没有不稳定配对
C、稳定匹配
D、不稳定匹配
答案：完美匹配;
没有不稳定配对;
最大匹配;
稳定匹配

3、给定一个匹配，如果Z喜欢A甚于匹配的女朋友，A喜欢Z甚于匹配的男朋友，那么A和Z是一个不稳定配对。
A:正确; B:错误
答案：正确

4、任意给定两张喜欢列表，稳定匹配问题只有一个稳定匹配。
答案：错

1、解决问题的基本步骤是（）。（1）算法设计（2）算法实现（3）数学建模（4）算法分析（5）正确性证明
A、(3)(1)(4)(5)(2)
B、(3)(4)(1)(5)(2)
C、(3)(1)(5)(4)(2)
D、(1)(2)(3)(4)(5)
答案：(3)(1)(5)(4)(2)

2、问题的两个要素是（ ）和（）
A、输入
B、输出
C、提问
D、算法
答案：B

3、算法的性质有（）
A、确定性
B、有穷性
C、输入
D、输出
答案：输入性;
输出性;
有穷性;
确定性

4、程序总是在有穷步的运算后终止。
答案：程序总是在有穷步的运算后终止

5、算法是一步步正确解决问题的方法或策略。
答案：正确

6、程序是算法用某种程序设计语言的具体实现，不能使用自然语言描述。
答案：程序总是在有穷步的运算后终止

7、算法每次求解一个实例，而计算机需要求解该问题的所有实例。
答案：对

1、从右向左计算p(x) = anxn + an-1xn-1 +… + a1x1 + a0 的数量级为（）
A、n
B、n^2
C、nlogn
D、logn
答案：n