《算法设计与分析试卷及答案》由会员分享，可在线阅读，更多相关《算法设计与分析试卷及答案（8页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析1、(1)证明：O(f)+O(g)=O(f+g)(7 分)(2)求下列函数的渐近表达式：6分) 3n2+10n; 21+1/n;2、对于下列各组函数(n)和g(n),确定f(n)=O(g(n域f(n)=Q(g(n)或 f(n)= &g(n)并简述理由o(15分)(1) f (n) = log n2; g (n) = log n + 5;(2) f (n) = log n 2; g (n) =、： n;(3) f (n) = n; g(n) = log2 n;3、试用分治法对数组An实现快速排序。(13分)4、试用动态规划算法实现最长公共子序列问题015分)5、试用贪心算法求解汽车
2、加油问题：已知一辆汽车加满油后可行n 公里，而旅途中有若干个加油站试设计一个有效算法，指出应在哪些 加油站停靠加油，使加油次数最少012分)6、试用动态规划算法实现下列问题：谩和B是两个字符串。我们要 用最少的字符操作，将字符串A转换为字符串8,这里所说的字符操作 包括：(1删除一个字符。(2) 插入一个字符。(3) 将一个字符改为另一个字符。将字符串A变换为字符串8所用的最少字符操作数称为字符鼠到B 的编辑距离，记为d(A,B),试设计一个有效算法，对任给的两个字符串 A和B，计算出它们的编辑距离l(A,B)b（16 分）7、试用回溯法解决下列整数变换问题：关于整数的变换f和g定义如 下：/
3、=3源=Li/2。对于给定的两个整数和m，要求用最少的变 换/和g变换次数将变为m。（16分）1、证明:令F(n)=O(f)W0存在自然数、c1，使得对任意的自然数Nn1,有：F(nWCf(n) (2 分)同理可令G(n)=O(g)则存在自然数虬、c2,使得对任意的自然麴，皿2,有：G(n)Wc g(n) (3 分)2令 c3=maxcL,c2，n3=max,n2, 对所有 的nn3，有：F(n芹 cf(n芹 c3f(n)G(n芹c g(n芹c g(n) (5 分)23故有：O(f)+O(g)=F(n)+G(n)c3f(n)+cg(n)=c(f(n)+g(n)333因此有：O(f)+O(g)=
4、O(f+g(7 分)解：(3n 2 + 10n) - 3n 2_-lim= 0; 因为n*3n2 + 10nU由渐近表达式的定义易知：3n2是3n2+10n的渐近表达式。 (3分)21 +1 - 21 因为n T 0, n T3，由渐近表达式的定义易知：21 + 1n21是21 +1的渐近表达式。(6分)n说明：函数!间的渐近表达式t(n)定义为：T (n) -1 (n) 0, n 8T (n)2、解：经分析结论为：(1) logn2 =。(logn + 5)； (5 分)(2) logn2 =。(3) ； (10 分)(3) n = 0(log2 n) ； (15 分)3、解：用分治法求解的
5、算法代码如下：int partition(float A,int p,int r)int i=p,j=r+1;float x=ap;while(1)while(a+ix);if(i=j) break;ai - j (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 l
6、cs_len(char* a,char* b,int cN)int m=strlen(a),n=strlen(b)时；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=1j=cij-1)cij=ci-1j;elsecij=cij-1;(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)
7、i-; (11 分)else if(cij=cij-1)j-;else(s-k=ai-1;i-J;return s; (15 分)5、解：int greedy(vecter x,int n)int sum=0,k=x.size();for(int j=0jn)coutvVNosolutionvvendl;return-1; (6 分)for(int i=0,s=0;in)sum+;s=xi; (9 分)return sum; (12 分)6、解：此题用动态规划算法求解：int dist()int m=a.size();int n=b.size();vector d(n+1,0);for(int
8、 i=1;i=n;i+)di=i (5 分)for(i=1;i=m;i+)int y=i-1;for(int j=1;j1?dj-1:i; (10 分)int del=ai-1=bj-1?0:1;dj=min(x+del,y+1,z+1); (13 分)return dn; (16 分)7、解：解答如下：void compute()k=1;while(!search(1,n)k+;if(kmaxdep)break;；(6 分)if(found)output() (9 分)else coutNoSolution”k)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 分)
