算法设计与分析试卷及答案
更新时间:2024-03-26 09:58:01 阅读量: 综合文库 文档下载
算法设计与分析
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分)
2f(n)?logn;g(n)?logn?5; (1)
2f(n)?logn;g(n)?n; (2)
2f(n)?n;g(n)?logn; (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、试用回溯法解决下列整数变换问题:关于整数i的变换f和g定义如下:f(i)?3i;g(i)??i/2?。对于给定的两个整数n和m,要求用最少的变换f和g变换次数将n变为m。(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?10n)?3n2lim?0;2n??3n?10n① 因为由渐近表达式的定义易知:
3n2是3n2+10n的渐近表达式。……………………………..(3分) ② 因为
21?1?21n?0,n??,由渐近表达式的定义易知: 121?n21是21?的渐近表达式。……………………………..(6分) 说明:函数T(n)的渐近表达式t(n)定义为:
T(n)?t(n)?0,n?? T(n)1n2、解:经分析结论为:
2logn??(logn?5);………………………….(5分) (1)
2(2)logn??(n);………………………….(10分) 2n??(logn);………………………….(15分) (3)
3、解:用分治法求解的算法代码如下: int partition(float A[],int p,int r) {
int i=p,j=r+1; float x=a[p]; while(1){ while(a[++i]
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 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 sum=0,k=x.size(); for(int j=0;j cout<<”Nosolution”< return-1;……………………………..(6分) } for(int i=0,s=0;i if(s>n){sum++;s=x[i];}……………………………..(9分) } return sum;……………………………..(12分) } 6、解:此题用动态规划算法求解: int dist() { int m=a.size(); int n=b.size(); vector 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!”< 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分) }
正在阅读:
算法设计与分析试卷及答案03-26
中外国服装史复习03-20
教学四项经费管理与实施办法(试行)04-01
印开单员的操作细则07-26
郑州二本大学02-21
佛山联合验收办事指南06-24
水处理EPC招标文件第一卷(投标须知)(1) - 图文10-05
2012届高中毕业班补充题、压轴题语文试题参考答案-推荐下载04-30
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 算法
- 试卷
- 答案
- 分析
- 设计
- 国考申论考点预测
- 2018年英语同步优化指导(人教版选修7)练习:阶段质量评估1
- 复句练习题 -
- 第七八届全国大学生节能减排竞赛获奖统计
- 模块1(1-10单元语法专练)
- 部编人教版七年级上册语文期中试卷10套(2018最新审定) - 图文
- 辽宁省大连二十四中2014-2015学年高一(下)期中生物试卷 - 图文
- 6102采后总结
- 液体涂装厂安全管理规范
- 《概率统计》期末考试题(有答案)
- 初二物理 力学 每节练习题
- 离石施工组织设计
- 《现代远程教育导论》2015年春学期在线作业(一)满分答案
- 基于MATLAB的二进制数字系统的调制(包括2ask,2fsk,2psk,2dpsk) -
- 材料科学与工程
- 鸿业市政道路简易操作步骤(好用)
- Web实验报告 - 3
- 药剂学 复习 知识总结
- 修订版,苏教版五年级下册科学教案(1)
- 《濒危野生动植物种国际贸易公约》(CITES)附录I、附录II和附录II