您所在位置: 网站首页 / 文档列表 / 数据结构与算法 / 文档详情
计算机09级《算法设计与分析》中考试卷1.doc 立即下载
上传人:yy****24 上传时间:2024-09-08 格式:DOC 页数:5 大小:66KB 金币:12 举报 版权申诉
预览加载中,请您耐心等待几秒...

计算机09级《算法设计与分析》中考试卷1.doc

计算机09级《算法设计与分析》中考试卷1.doc

预览

在线预览结束,喜欢就下载吧,查找使用更方便

12 金币

下载文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

计算机科学技术学院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.用动态规划算法计算矩阵连乘问题的最优值所花的时间是,子问题空间大小是。5.n个物品的0-1背包问题可用法求解,其解空间树中叶子结点个数是,解空间树中每个内结点的孩子数是。三、计算题(共4小题,第1,2,3小题10分,第4小题15分,总计45分)1.(10分)给定两个序列X={B,C,D,A},Y={A,B,C,B},请按下列动态规划算法求其最长公共子序列。要求分别填写s矩阵和m矩阵,并标示出怎样求其最长公共子序列。填空。voidLCSLength(intm,intn,char*x,char*y,int**m,Type**s){inti,j;for(i=0;i<=m;i++)m[i][0]=0;for(j=0;j<=n;j++)m[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){m[i][j]=m[i-1][j-1]+1;s[i][j]=‘↖’;}elseif(m[i-1][j]>m[i][j-1]){m[i][j]=m[i-1][j];s[i][j]=‘↑’;}else{m[i][j]=m[i][j-1];s[i][j]=‘←’;}}voidLCS(inti,intj,char*x,Type**s){if((i==0)||(j==0))return;if(s[i][j]==‘↖’){LCS(i-1,j-1,x,s);cout<<x[i];}elseif(s[i][j]==‘↑’)LCS(i-1,j,x,s);elseLCS(i,j-1,x,s);}s矩阵最长公共子序列:m矩阵2.(10分)对下列各组函数f(n)和g(n),确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ(g(n)),并简要说明理由。(1)f(n)=logn3;g(n)=(2)f(n)=n!;g(n)=3n(3)f(n)=1000;g(n)=log100(4)f(n)=5n;g(n)=7n(5)f(n)=2n;g(n)=n53.(10分)对下图所示的连通网络G,用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中,依次加入T的边集TE中的边。说明该算法的基本思想及贪心策略,并简要分析算法的时间复杂度。123456181117151921266794.考虑n=3的批处理作业调度实例:tji机器1机器2作业1111作业231作业321其中tji是作业Ji需要在机器j上处理的时间。对于给定的3个作业,制定一个最佳作业调度方案,使其完成时间和达到最小。要求:(1)画出该问题的解空间树;(5分)(2)写出该问题的剪枝策略(即限界条件),要求只保留第一个最优解;(2分)(3)按回溯法搜索解空间树,并用剪枝策略对解空间树中该剪枝的位置打;(5分)(4)给出最优解及最优值。(3分)四、算法填空题(共1小题,总计15分)(15分)用分治策略设计的求一维空间上点集S中最接近点对的算法如下。intCpair(intS[],intl,intr)//算法的功能是确定数组S中[l,r]区间的最近点对距离{if(l>=r)ruturn∞;//注释:____________________________intm=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中
单篇购买
VIP会员(1亿+VIP文档免费下)

扫码即表示接受《下载须知》

计算机09级《算法设计与分析》中考试卷1

文档大小:66KB

限时特价:扫码查看

• 请登录后再进行扫码购买
• 使用微信/支付宝扫码注册及付费下载,详阅 用户协议 隐私政策
• 如已在其他页面进行付款,请刷新当前页面重试
• 付费购买成功后,此文档可永久免费下载
年会员
99.0
¥199.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用

手机号注册 用户名注册
我已阅读并接受《用户协议》《隐私政策》
已有账号?立即登录
我已阅读并接受《用户协议》《隐私政策》
已有账号?立即登录
登录
手机号登录 微信扫码登录
微信扫一扫登录 账号密码登录

首次登录需关注“豆柴文库”公众号

新用户注册
VIP会员(1亿+VIP文档免费下)
年会员
99.0
¥199.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用