算法设计与分析试卷及答案.doc

算法设计与分析
1、（1） 证明：O（f)+O（g)=O（f+g)（7分）
（2） 求下列函数的渐近表达式：（6分）
① 3n2+10n；
② 21+1/n；
2、对于下列各组函数f（n）和g(n)，确定f(n)=O（g（n）)或f(n)=Ω(g(n)）或f(n）=θ（g（n）)，并简述理由。（15分）
(1）
（2）
(3）
3、试用分治法对数组A［n］实现快速排序。（13分）
4、试用动态规划算法实现最长公共子序列问题.（15分)
5、试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法,指出应在哪些加油站停靠加油，使加油次数最少.（12分)
6、试用动态规划算法实现下列问题:设A和B是两个字符串.我们要用最少的字符操作,将字符串A转换为字符串B，这里所说的字符操作包括：
(1）删除一个字符。
(2）插入一个字符。
（3)将一个字符改为另一个字符。
将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为d（A,B).试设计一个有效算法，对任给的两个字符串A和B,计算出它们的编辑距离d(A，B)。
（16分）
7、试用回溯法解决下列整数变换问题：关于整数的变换和定义如下：.对于给定的两个整数和，要求用最少的变换和变换次数将变为。（16分)
1、⑴证明：令F(n)=O（f），则存在自然数n1、c1,使得对任意的自然数n≥n1，有:F（n）≤c1f(n）……………………………。.（2分）
同理可令G(n)=O（g）,则存在自然数n2、c2，使得对任意的自然数n≥n2，有:G（n）≤c2g（n）…………………………….。（3分）
令c3=max｛c1,c2},n3=max{n1，n2｝,则对所有的n≥n3,有:
F(n)≤c1f（n）≤c3f（n)
G（n）≤c2g（n)≤c3g（n）…………………………….。（5分）
故有：
O(f）+O(g）=F(n）+G(n）≤c3f(n）+c3g(n)=c3(f（n）+g（n))
因此有:
O（f)+O（g）=O（f+g）……………………………。。(7分）
⑵ 解：
① 因为由渐近表达式的定义易知:
3n2是3n2+10n的渐近表达式。……………………………。。（3分）
② 因为，由渐近表达式的定义易知:
21是的渐近表达式.……………………………。。(6分）
说明：函数T（n)的渐近表达式t(n)定义为:
2、解:经分析结论为：
（1）………………………….(5分）
(2）；…………………………。（10分）
（3)；…………………………。（15分）
3、解：用分治法求解的算法代码如下：
int partition(float A[],int p，int r）
{
int i=p，j=r+1;
float x=a[p]；
while（1)｛
while（a［++i]〈x)；
while(a［--j]〉x）；
if（i〉=j) break；
a［i]←→a[j］……………………………。。（4分）
｝；
a[p］=a［j]；
a［j]=x;
return j；……………………………。.（7分）
}
void Quicksort（float a[]，int p,int r)
{
if(p<r)｛
int q=partition（a，p,r）；……………………………。。(10分)
Quicksort(a，p，q-1）;
Quicksort(a，q+1,r）;
｝
};
Quicksort（a，0，n-1）;……………………………。.(13分）
4、解：用动态规划算法求解的算法代码如下：
int lcs_len(char＊ a,char＊ b，int c[]［N］)
{
int m=strlen(a)，n=strlen(b),i，j;
for(i=0；i〈=m;i++)c［i][0］=0；
for（j=1;j〈=n；j++）c［0］［j]=0;……………………………..（4分)
for（i=1；i〈=m;i++)
for(j=1;j<=n；j++)
if(a[i—1]==b［j—1]）c［i］[j］=c［i-1][j—1]+1；
else if（c[i-1］［j］〉=c［i]［j-1］)
c［i］［j]=c[i—1］[j]；
elsec［i]［j］=c[i][j—1]；…………………………….。(7分）
return c[m］[n］;……………………………。。（8分）
｝;
char＊ build_lcs(char s[］,char* a,char＊ b）
{
int k，i=strlen(a），j=strlen(b）,c[N］［N］;
k=lcs_len(a，b,c);
s［k］=’\0';
while(k〉0)｛
if(c[i][j]==c[i-1]［j］）i——;……………………………。.(11分）
else if（c［i]［j］==c［i]［j—1］)j—-;
else{
s[-—k]=a［i—1]；
i—-,j-—；
}
｝
return s;…………………………….。（15分）
}
5、解:int greedy（vecter〈int〉 x，int n）
{
int sum=0,k=x。size（）;
for(int j=0；j<k；j++）
if（x［j］>n)｛
cout〈<”Nosolution"<<endl；
return-1；……………………………。.（6分）
｝
for(int i=0,s=0；i〈k；i++)｛
s+=x［i];
if(s>n）{sum++；s=x［i］；｝…………………………….。（9分）
}
return sum；…………………………….。(12分）
}
6、解：此题用动态规划算法求解：
int dist()
{
int m=a.size();
int n=b。size()；
vector〈int〉 d(n+1,0)；
for（int i=1;i<=n；i++）d[i］=i;……………………………..（5分）
for（i=1;i<=m;i++）｛
int y=i—1;
for（int j=1；j〈=n；j++){
int x=y；
y=d［j];
int z=j〉1?d[j—1]：i;……………………………。.（10分）
int del=a［i—1]==b［j—1］？0:1;
d[j]=min（x+del，y+1，z+1）;……………………………..（13分）
｝
}
return d[n］;……………………………。.（16分）
｝
7、解：解答如下：
void compute()
｛
k=1;
while（！search（1,n))｛
k++；
if(k>maxdep)break；
init（)；
｝;…………………………….。（6分）
if(found）output（）;……………………………..（9分）
else cout<<”NoSolution!”<<endl；
}
bool search(int dep，int n)
{
if(dep〉k)return false;…………………………….。（11分)
for(int i=0；i<2；i++）{
int n1=f(n，i);t[dep]=I；……………………………。.（13分）
if（n1==m|｜search（dep+1，n1））｛
found=true;
out（);
return true；
}
return false;……………………………。.（16分）
}