05计本算法设计与分析期考试卷(A卷)
更新时间:2024-07-05 21:01:01 阅读量: 综合文库 文档下载
- 05计本算法设计与分析推荐度:
- 相关推荐
___号学 ____ 栏__ 名 姓 息 级 年线 _ _ _ _ _ 信 _ 业 专订 _ _ _ 生 _ _ _ 系 _装 _ 考____院学______福建师范大学数学与计算机科学学院 2006 — 2007学年第二学期考试 A 卷
专 业:计算机科学与技术 年 级: 2005级 课程名称: 算法设计与分析 任课教师: 潘日晶 试卷类别:开卷( )闭卷(√) 考试用时: 120 分钟 考试时间: 2007 年 1 月 13 日 下 午 18 点 30 分
题号 一 二 三 四 五 总得分 评卷人 得分 题号 六 七 八 九 十 得分 福建师范大学试卷纸 共 9 页,第 1 页
一.填空题(每空2分,共30分) 1.算法的时间复杂性指算法中 的执行次数。 2.在忽略常数因子的情况下,O、?和?三个符号中, 提供了算法运行时间的一个上界。 3.设Dn表示大小为n的输入集合,t(I)表示输入为I时算法的运算时间, p(I)表示输入I出现的概率,则算法的平均情况下时间复杂性A(n)= 。 4.分治算法的时间复杂性常常满足如下形式的递归方程: ?f(n)?d , n?n0 ? f(n)?af(n/c)?g(n) , n?n0? 其中,g(n)表示 。 5. 分治算法的基本步骤包括 。 6.回溯算法的基本思想是 。 7.动态规划和分治法在分解子问题方面的不同点是 。 8.贪心算法中每次做出的贪心选择都是 最优选择。 9.PQ式的分支限界法中,对于活结点表中的结点,其下界函数值越小,优先级越 。 10.选择排序、插入排序和归并排序算法中, 算法是分治算法。 11.随机算法的一个基本特征是对于同一组输入, 不同的运行可能得到 的结果。 12.对于下面的确定性快速排序算法,只要在步骤3前加入随机化步骤 ,就可得到一个随机化快速排序算法,该随机化步骤的功能是 。 算法 QUICKSORT 输入:n个元素的数组A[1..n]。 输出:按非降序排列的数组A中的元素。 福建师范大学试卷纸 共 9 页,第 2 页
_____号学 _ _栏_ _ _ _ 名 姓 息 级 年 _ _信_ _ _ _ 业 专生 _ _ _ _ _ _ 考系______院学______1. quicksort(1, n) end QUICKSORT 过程 quicksort(A, low, high) // 对A[low..high]中的元素按非降序排序。 2. if low A[i]?A[1] w =i return w, A end SPLIT 二.计算题和简答题(每小题7分,共21分) 1.用O、?、?表示函数f与g之间阶的关系,并分别指出下列函数中阶最低和最高的函数: (1) f (n)=100 g(n)=100n (2) f(n)=6n+n?logn? g(n)=3n (3) f(n)= n/logn-1 g(n)=2n (4) f(n)=2n?n2 g(n)=3n (5) f(n)= log3n g(n)= log2n 2.下面是一个递归算法,其中,过程pro1和pro2的运算时间分别是1和log2n。给出该算法的时间复杂性T(n)满足的递归方程,并求解该递归方程,估计T(n)的阶(用?表示)。 算法 EX1 输入:正整数n,n=2k。 输出:… ex1(n) end EX1 过程 ex1(n) if n=1 then pro1(n) else 福建师范大学试卷纸 共 9 页,第 4 页 _____号学 _栏_ _ _ _ _ 名 姓息 级 年 _信_ _ _ _ _ 业 生专 _ _ _ _ _ _考系______院学______pro2(n) ex1(n/2) end if return end ex1 3.用Floyd算法求下图每一对顶点之间的最短路径长度,计算矩阵D0,D1,D2和D3,其中Dk[i, j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。 线 三.算法填空题(共34分) 1.(10分)设n个不同的整数按升序存于数组A[1..n]中,求使得A[i]=i 订 的下标i 。下面是求解该问题的分治算法。 算法 SEARCH 输入:正整数n,存储n个按升序排列的不同整数的数组A[1..n]。 输出:A[1..n]中使得A[i]=i的一个下标i,若不存在,则输出 no 装solution。 i=find ( (1) ) if i>0 then output i else output “no solution” end SEARCH 过程 find (low, high) // 求A[low..high] 中使得A[i]=i的一个下标并返回,若不存在, 福建师范大学试卷纸 共 9 页,第 5 页 //则返回0。 if (2) then return 0 else mid=?(low?high)/2? if (3) then return mid else if A[mid] _____号学 栏__ _ _ _ _ 名 息姓 级 年线 _ 信 _ _ _ _ _ 业 生专订 _ _ _ _ _ 考_ 系 _装_____院学______for i=1 to n C[i, i]= (1) for d=1 to n-1 for i=1 to n-d j= (2) C[i, j]= ∞ for k=i+1 to j x= (3) if x x=x0; y=y0 ; tag[x, y]=1 m=n*n i=1; k[i]=0 while (1) and not flag while k[i]<8 and not flag k[i]= (2) x1= x+dx[k[i]]; y1= y+dy[k[i]] if ((x1,y1)无越界and tag[x1, y1]=0) or ((x1,y1)=(x0,y0) and i=m) then x=x1; y=y1 tag[x, y]= (3) if i=m then flag=true else i= (4) (5) end if end if end while i=i-1 (6) (7) end while if flag then outputroute(k) //输出路径 else output “no solution” end HORSETRAVEL 福建师范大学试卷纸 共 9 页,第 8 页 _____号学 __ 栏__ _ _ 名 姓 息 级 年线 _ _ _ 信 _ _ _ 业 专订 _ 生 _ _ _ _ _ 系 考_装_____院学______ 四.算法设计题(15分) 1. 一个旅行者要驾车从A地到B地,A、B两地间距离为s。A、B两地之间有n个加油站,已知第i个加油站离起点A的距离为di公里,0=d1?d2???dn?s,车加满油后可行驶m公里,出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少?给出用贪心法求解该最优化问题的贪心选择策略,写出求该最优化问题的最优值和最优解的贪心算法,并分析算法的时间复杂性。 福建师范大学试卷纸 共 9 页,第 9 页
正在阅读:
05计本算法设计与分析期考试卷(A卷)07-05
二氧化碳的资源化利用07-18
读《为人民服务》有感12-30
我们班的新年音乐会作文800字06-23
有机化学实验(4)10-18
小学数学五年级下册第三单元测试题(人教)01-29
2018年中考物理试题分项版解析汇编第03期专题09简单机械及其效率含解析10-26
学校安全工作先进个人事迹材料01-20
铁道信号工程施工作业指导书 7-室外箱盒安装 - 图文11-10
美丽的冬天的作文【精华篇】06-13
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 期考
- 算法
- 试卷
- 分析
- 设计
- 2013年物流师资格认证考试及答案每日一讲(12月20日)
- 炉山煤矿维修措施
- 农夫山泉案例分析报告最终稿
- 小学数学精彩课堂之体会
- 2014年中考英语词汇题型及考点归纳
- 2017天津春季高考英语试题word版(含答案)
- 汽车运用与维修比赛规程
- 2008年高考英语短文改错练习80篇 - 图文
- XX银行XX分行XX支行闭路监控及报警系统方案 - 图文
- VB学生管理系统论文范文
- 聚苯颗粒外墙保温工程监理细则 - secret
- 成卫发26号-2012版公共卫生服务项目 - 图文
- 2014年南京外国语学校小升初数学真题
- 物流部各岗位职责
- 2014新北师大版四年级数学上册知识点总结
- 高一化学方程式计算专题
- Spring--quartz中cronExpression配置说明
- 椒江区第二十二届中小学生科技文化艺术节单项获奖名单
- 大豆蛋白饲料生产项目可行性研究报告 - 图文
- 电力系统继电保护与自动化专业自荐信范文