下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
本文格式为Word版,下载可任意编辑——算法设计与分析试卷及答案算法设计与分析
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、解:用分治法求解的算法代码如下:intpartition(floatA[],intp,intr){
inti=p,j=r+1;floatx=a[p];while(1){while(a[++i]x);if(i>=j)break;
a[i]←→a[j]……………..(4分)};a[p]=a[j];a[j]=x;
returnj;……………..(7分)}
voidQuicksort(floata[],intp,intr){if(p=c[i][j-1])c[i][j]=c[i-1][j];
elsec[i][j]=c[i][j-1];……………..(7分)returnc[m][n];……………..(8分)};
char*build_lcs(chars[],char*a,char*b){
intk,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分)
elseif(c[i][j]==c[i][j-1])j--;else{s[--k]=a[i-1];i--,j--;}}
returns;……………..(15分)}
5、解:intgreedy(vecterx,intn){
intsum=0,k=x.size();for(intj=0;jn){
coutn){sum++;s=x[i];}……………..(9分)}
returnsum;……………..(12分)}
6、解:此题用动态规划算法求解:intdist()
{
intm=a.size();intn=b.size();vectord(n+1,0);
for(inti=1;i1?d[j-1]:i;……………..(10分)intdel=a[i-1]==b[j-1]?0:1;
d[j]=min(x+del,y+1,z+1);……………..(13分)}}
returnd[n];……………..(16分)}
7、解:解答如下:voidcompute(){k=1;
while(!search(1,n)){k++;
if(k>maxdep)br
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 银行机构业务部课程设计
- 预算编制课程设计目标
- 课程设计数学建模案例
- 跑酷课程设计案例
- 通风除尘课课程设计书
- 铸造工艺设计的课程设计
- GB/T 45162.1-2024物流仓储设备可靠性试验规范第1部分:输送分拣设备
- 二零二五年度高端猫舍购买合同协议书3篇
- 2024年钢结构工程清工责任承包合同版B版
- 2024消防器材买卖合同
- 2025年度私立学校教师聘用合同(初中部专业学科)3篇
- 2024年关爱留守儿童工作总结
- GB/T 45092-2024电解水制氢用电极性能测试与评价
- 《算术平方根》课件
- DB32T 4880-2024民用建筑碳排放计算标准
- 2024-2024年上海市高考英语试题及答案
- 注射泵管理规范及工作原理
- 山东省济南市2023-2024学年高二上学期期末考试化学试题 附答案
- 大唐电厂采购合同范例
- GB/T 18724-2024印刷技术印刷品与印刷油墨耐各种试剂性的测定
- IEC 62368-1标准解读-中文
评论
0/150
提交评论