算法设计与分析试卷及答案.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、试用分治法对数组An实现快速排序。（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,使得对任意的自然数nn1，有:F（n）c1f(n）。.（2分）同理可令G(n)=O（g）,则存在自然数n2、c2，使得对任意的自然数nn2，有:G（n）c2g（n）.。（3分）令c3=maxc1,c2,n3=maxn1，n2,则对所有的nn3,有: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=ap；while（1)while（a+ix)；while(a-jx）；if（i=j) break；aiaj。（4分）；ap=aj；aj=x;return j；。.（7分）void Quicksort（float a，int p,int r)if(pr)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 cN)int m=strlen(a)，n=strlen(b),i，j;for(i=0；i=m;i+)ci0=0；for（j=1;j=n；j+）c0j=0;.（4分)for（i=1；i=m;i+)for(j=1;j=n；j+)if(ai1=bj1）cij=ci-1j1+1；else if（ci-1j=cij-1)cij=ci1j；elsecij=cij1；.。(7分）return cmn;。（8分）;char build_lcs(char s,char* a,char b）int k，i=strlen(a），j=strlen(b）,cNN;k=lcs_len(a，b,c);sk=0;while(k0)if(cij=ci-1j）i;。.(11分）else if（cij=cij1)j-;elses-k=ai1；i-,j-；return s;.。（15分）5、解:int greedy（vecterint x，int n）int sum=0,k=x。size（）;for(int j=0；jn)cout”Nosolutionn）sum+；s=xi；.。（9分）return sum；.。(12分）6、解：此题用动态规划算法求解：int dist()int m=a.size();int n=b。size()；vectorint d(n+1,0)；for（int i=1;i=n；i+）di=i;.（5分）for（i=1;imaxdep)break；init（)；;.。（6分）if(found）output（）;.（9分）else cout”NoSolution!”endl；bool search(int dep，int n)if(depk)return false;.。（11分)for(int i=0；i2；i+）int n1=f(n，i);tdep=I；。.（13分）if（n1=m|search（dep+1，n1）found=true;out（);return true；return false;。.（16分）