算法分析样卷.doc

《算法分析与设计》样卷
一、选择题（20分，每题2分）
1.0-1背包问题用（）实现算法最好。
A、分治策略B、动态规划法
C、贪心法D、穷举法
2.下列动态规划的最基本的要素是（）。
A、算出最优解B、贪心选择性质
C、重叠子问题D、定义最优解
3.下列算法中通常以广度优先方式系统搜索问题解的是（）。
A、分支限界法B、动态规划法
C、贪心法D、回溯法
4.自底向上方法是（）的计算最优值的方法中的一种。
A、分支界限算法B、动态规划算法
C、贪心算法D、回溯算法
5.一般(部分)背包问题的贪心算法所需的计算时间为（）
A、O（n）B、O（nlogn）
C、O（2n）D、O（n2）
6.大整数乘法可以利用（）的算法来实现。
A、分治策略B、动态规划法
C、贪心法D、回溯法
7..下列程序段的频度是（）。
for(i=0;i<n;i++)
for(j=0;j<n;j++)
k++;
A、n2B、n
C、n*(n+1)/2D、2n
8.下列问题一般不采用分治法的是（）。
A、三分检索B、求最大最小值问题
C、最大子段和 D、矩阵连乘问题
9.对多段图问题描述不正确的是（）
A、多段图是一个无向图B、可用向前处理法
C、可用向后处理法D、可用分治法解决。
10.以下对回溯法描述正确的是（）
A、必须使用栈来实现算法。
B、使用广度优先方式系统搜索问题解
C、它可以用裁剪函数来减少搜索空间的规模，减少时间复杂度
D、回溯法只能用来求最优化问题
二、填空题（20分，每空2分）
算法的确定性是（）。
有限性是指（）。
矩阵连乘问题可以用（）设计。
所谓贪心选择性质是指所求问题的（）以通过()，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与（）主要区别。
可以用（）来描述回溯法和分支限界法的解空间树。
在回溯法中常用剪枝函数有()和（）。
矩阵连乘问题的最优子结构性质建立子问题最优值的递归关系。用m[i][j]记录需要的最少数乘次数，则m[i][j]递归定义为：
（）
三、简答题（20分，每小题5分）
写出动态规划的基本要素。
说明贪心算法与动态规划算法的的主要差别。
写出用回溯法搜索排列树的一般算法。
简述利用分冶法来解决大整数乘法的基本思想。
四、算法设计题（40分）
1.给定数组a[0:n-1]，试设计一个分治算法，在最坏情况下用n+[logn]-2次比较找出a[0:n-1]中元素的最大值和次最大值。要求写出算法的思想，算法步骤，并说明时间复杂性。（20分）
2.给定由n个整数组成的序列a[0:n-1]。序列a的递增子序列定义为，存在下标序列i1<i2<…<ik使得a[i1]<=a[i2]<=…<=a[ik]。求a的最长递增子序列。要求写出用动态规划解此问题的算法的思想，最优子结构性质，递归公式，递归公式的计算方法，时间复杂性说明。（20分）
参考答案及评分标准（B）
选择题（20分，每题2分）
1. B 2. C3. A 4. B 5. B
6. A 7. A8. D 9. A 10.C

二、填空题（20分，每空2分）
1.组成算法的每条指令是清晰，无歧义的
算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的
2. 动态规划
3. 整体最优解一系列局部最优的选择动态规划
4. n元组
5.约束函数限界函数
6.动态规划
7.

（4分）

三、简答题（20分，每小题5分）
写出动态规划的基本要素。
（1）最优子结构性质（2）重叠子问题性质
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

说明贪心算法与动态规划算法的的主要差别。
对于贪心算法，所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

写出用回溯法搜索子集树的一般算法。
遍历排列树需要O(n!)计算时间
voidbacktrack(intt)
{
if(t>n)output(x);
else
for(inti=t;i<=n;i++){
swap(x[t],x[i]);
if(legal(t))backtrack(t+1);
swap(x[t],x[i]);
}
}

简述利用分冶法来解决大整数乘法的基本思想。
分治法:
X=a2n/2+b
Y=c2n/2+d
XY=ac2n+(ad+bc)2n/2+bd
复杂度分析T(n)=O(n2)没有改进
为了降低时间复杂度，必须减少乘法的次数。为此，我们把XY写成另外的形