算法设计与分析试题及答案.docx

、填空题(20分)
一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运 算，此外，算法还应具有以下五个重要特性：确定性，有穷性,可行性,0个或多个输入，一个 或多个输出。
算法的复杂性有时间复杂性和空间复杂性
k=i;
for(j=k+1; j<=n;j++)
if(E[k].b<s[j].b) k=j;
suap(s[i] .index ,s[k] .index); // 只移动:Lndu)(和tag
suap(s[i] .t-ag [k ]. tag);
(设函数名binarysearchtree))
uoid binarysearchtree(int a[]Tint b[] ,int n Tint **m,int **s,int **w) ' int ,!;
For(i=1;i<=n+1;i++)
w[i][i-1]=a[i-1];
■n[i][i-1] = 0；
For(l=0;l<=n-1 ；!**)// 1 是下标 j-i的差
For(i=1;i<=n-l;i++)
j=i+l；
W[i][j]=W[i][j-1]+a[j]+b[j];
m[i][j]=ri[i][i-1]+in[i+1][j]^[i][j];
For(k=i+1 ;k<=j;k++)
t=m[i][k-1]+ri[k+1][j]+u[i][j];
n«[i][j]=t；
或订[j]=k；
一、 填空题(本题15分，每小题1分)
1、 算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。
2、 在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基 本计算模型是随机存取机RAM(Random Access Machine)、随机存取存储程序机 RASP(Random Access Stored Program Machine)、图灵机(Turing Machine)。
3、 算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。
4、 计算机的资源最重要的是 时间和空间资源。因而，算法的复杂性有时间复杂度和空 间复杂度之分。
5、 f(n)= 6X2n+n2, f(n)的渐进性态 f(n)=O(2n)。
6、 贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它 所做出的选择只是在某种意义上的局部最优选择。
7、 许多可以用贪心算法求解的问题一般具有2个重要的性质：贪心选择性质和最优子结构 性质。
二、 简答题(本题25分，每小题5分)
1、 简单描述分治法的基本思想。
分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问 题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则 再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止; 将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的 解。
2、 简述动态规划方法所运用的最优化原理。
“最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n 个决策D1，D2,…，Dn，如若这个决策序列是最优的，对于任