计算机科学技术学院09级《算法设计与分析》中考试题_第1页
计算机科学技术学院09级《算法设计与分析》中考试题_第2页
计算机科学技术学院09级《算法设计与分析》中考试题_第3页
计算机科学技术学院09级《算法设计与分析》中考试题_第4页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、.计算机科学技术学院09级算法设计与分析中考试题一、 简答题（共3小题，第1小题2分，第2，3小题4分，总计10分）1.(2分) 请用英文写出两种以上能求解0-1背包问题的设计算法策略。2.(4分) 请叙述动态规划法的基本思想。3.(4分) 请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思想？(3)优先队列插入算法时间复杂度？二、填空题 （共10个空，每空1分，总计10分）1递归的快速排序算法在最好情况下divide阶段所花的时间是 ，conquer阶段所花的时间是 ，算法的时间复杂度是 。3背包问题可用 ， 等策略求解。4用动态规划算法计算矩阵连乘问题的最优值所花的时

2、间是 ， 子问题空间大小是 。5n个物品的0-1背包问题可用 法求解，其解空间树中叶子结点个数是 ，解空间树中每个内结点的孩子数是 。三、计算题（共4小题，第1,2,3小题10分，第4小题15分，总计45分）1(10分) 给定两个序列X=B,C,D,A，Y=A,B,C,B，请按下列动态规划算法求其最长公共子序列。要求分别填写s矩阵和m矩阵，并标示出怎样求其最长公共子序列。填空。 void LCSLength(int m, int n, char *x, char *y, int *m, Type *s) int i, j; for(i=0; i=m; i+) mi0=0; for(j=0; j

3、=n; j+) m0j=0; for(i=1; i=m; i+) for(j=1; j mij-1) mij= mi-1j; sij=; else mij= mij-1; sij=; void LCS(int i, int j, char *x, Type *s) if( (i=0) | (j=0) ) return ; if (sij=) LCS(i-1, j-1, x, s); cout=r) ruturn ; / 注释：_ _ _int m=selec(S,l,r,(r-l)/2); / 找出中位数m，所花时间：_ _ _i= partition(a, l, r, m）;/ 用中位数m将数组分为两段, 所花时间：_ _d1=Cpair(S, l, i) ; / 求数组S中l, i区间的最近点对距离,所花时间：_ _d2=_ _ ; p=max(S, l, i); / 求数组S中l, i区间的最大数，所花时间：_ _q= min(S, i+1, r); / 求数组S中i+1，r区间的最小数d=min1(d1,d2,q-p); / 求三者中最小数，所花时间：_ _ return d ; / 返回最近点对的距离divide阶段所花的时间：_ _conquer阶段所花的时间：_ _combine阶段所花的时间：_ _算法时间复杂度T(n)的递归方程(2分)： _ _ _

人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论