算法设计与分析(期末总复习)
更新时间:2024-06-19 16:28:01 阅读量: 综合文库 文档下载
复习
一、简答题(每小题5分,选答2题,共10分)
1. 什么是算法?试说明算法设计分析过程的一般框架和主要步骤。 2. 简述非递归算法时间效率分析的通用方案。 3. 简述递归算法时间效率的通用方案。
4. 简述蛮力法、分治法、减治法,变治法、时空权衡、动态规划、贪婪技术、迭代改进八种算法设计技术中至少三种技术基本思想或原理。
二、分析题(每小题10分,共20分) 1. 考虑下面的算法。P52
算法 Mystery(n) //输入:非负整数n
S=0
for i ? 1 to n do
S ? S + i*i Return S
a. 该算法求的是什么? b. 它的基本操作是什么? c. 该基本操作执行了多少次? d. 该算法的效率类型是什么?
2. 考虑下面的递归算法。P52
算法 Secret(A[0..n-1]) //输入:包含n个实数的数组A[0..n-1] minval ? A[0]; maxval ? A[0] for i ?1 to n-1 do if A[i] < minval minval ? A[i] if A[i] > maxval maxval ? A[i] return maxval – minval a. 该算法求的是什么? b. 它的基本操作是什么? c. 该基本操作执行了多少次? d. 该算法的效率类型是什么?
3. 考虑下面的递归算法P59 算法 Q(n) //输入:正整数 if n=1 return 1 else return Q(n-1) + 2*n -1
a. 建立该函数值的递推关系并求解,以确定该算法计算的是什么; b. 建立该算法所做的乘法运算次数的递推关系并求解; c. 建立该算法所做的加减运算次数的递推关系并求解。
三、算法设计题(每小题10分,共20分)
1. 应用快速排序对序列E,X,A,M,P,L,E按照字母顺序排序。并画出相应的递归调用树。(4章分治法)P102
第 1 页 共 9页
2. 对于下面的有向图,应用基于DFS的算法来解拓扑排序问题。(5章减治法)P133.
第 2 页 共 9页
3. 用自底向上算法为列表1, 8, 6, 5, 3, 7, 4进行堆排序。(6章变治法)P175
4. 应用Horspool算法在下面的文本中查找模式BARBER:BSS_KNER_BARBER (7章时空权衡)P201
四、计算题(每小题10分,共20分)
第 3 页 共 9页
1. 对于输入30, 20, 56, 75, 31, 19和散列函数h(K)=K mod 11(7章时空权衡)P207 a. 构造它们的开散列表;
b. 求在本表中成功查找的最大键值比较次数; c. 求在本表中成功查找的平均键值比较次数。
2. 对由下面邻居矩阵定义的有向图,应用Warshall算法求它的传递闭包。(8章动态规划)P222
第 4 页 共 9页
3. 对于下面具有权重矩阵的有向图,求解完全最短路径问题。(8章动态规划)P223
4. 应用Prim算法或Kruskal算法求下列图的最小生成树。(9章贪婪技术)P245
第 5 页 共 9页
正在阅读:
算法设计与分析(期末总复习)06-19
模具材料选用标准05-29
猫作文300字07-14
21、伟大的悲剧导学案04-28
以读书为话题的作文600字02-05
最新部编人教版道德与法治二年级下册:05 健康游戏我常玩 教学设计 教案09-07
2015年杭州市环境状况公报11-05
vb二级模拟题汇总09-27
- 高一物理牛顿运动定律全套学习学案
- 水处理一级反渗透加还原剂亚硫酸氢钠后为什么ORP会升高
- 毕业设计(论文)-正文董家口 - 图文
- 荣盛酒店经营管理公司录用通知及入职承诺书II
- 第二讲 大学英语四级快速阅读技巧
- 质量管理体系文件(2015年委托第三方医药物流配送企业专用版本)
- 214071收款办法
- 苏轼对《文选》选文的评价
- 《诊断学基础B》1-8作业
- 广东省东莞市高一数学下学期期末教学质量检查试题
- 海南电网公司VIS推广应用管理办法
- 红星照耀中国习题
- 苏教版小学语文六年级上册期末复习资料之生字词整理
- 局域网组建与应用—王向东
- 税务稽查内部管理文书样式
- 环保社会实践调查表
- 九年级思品第一单元复习
- 2016年全国注册咨询工程师继续教育公路路线设计规范试卷
- 毕业设计-青岛港董家口港区防波堤设计
- 撞背锻炼方法与益处
- 算法
- 期末
- 复习
- 分析
- 设计
- 东航2008年度放行人员B737-300试题C
- 最新-初中语文教师述职报告 精品
- 乡镇工作面临的机遇和挑战及其原因对策分析
- 2019届中考地理第十五章认识区域第4节青藏地区 - 图文
- 新浙教版七年级数学下册《二元一次方程组的应用(2)》导学案
- 小学生艺术展演活动方案
- 密立根油滴实验
- 西南交大 大学物理 下 第9次作业 答案
- 2016-2021年餐饮油水分离器行业深度分析及“十三五”发展规划指
- 西班牙语发音快速入门
- 在“两会”结束时的讲话
- 2015贵州省会计人员继续教育考试技巧与口诀
- 网络程序设计试题A卷-2013(李金库)
- 2018大学生金工实习报告4篇
- 2017年食品加工厂项目可行性研究报告
- BLDC控制 - 图文
- 自动控制原理—试卷B(胡俊峰)
- 经典医疗整形美容广告文案
- 磁悬浮列车文献综述
- 汽车销售系统实训报告