算法设计与分析(期末总复习)
更新时间: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
粮油公司假期社会实践报告02-27
2022-2022年三年级科学下册教案(全册)-教科版小学三年级04-13
2011年中央电大7月中级财务会计二考试复习资料及历年的考试试题07-03
校本课程资料 - 图文01-21
统编人教部编版小学语文二年级下册语文期末测试题4(含答案)04-14
感恩父母德育实践活动课10-22
中国石油大学在线考试参考答案(1)03-25
1.1《信息与信息的特征》说课稿303-06
四风问题清单02-11
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 算法
- 期末
- 复习
- 分析
- 设计
- 东航2008年度放行人员B737-300试题C
- 最新-初中语文教师述职报告 精品
- 乡镇工作面临的机遇和挑战及其原因对策分析
- 2019届中考地理第十五章认识区域第4节青藏地区 - 图文
- 新浙教版七年级数学下册《二元一次方程组的应用(2)》导学案
- 小学生艺术展演活动方案
- 密立根油滴实验
- 西南交大 大学物理 下 第9次作业 答案
- 2016-2021年餐饮油水分离器行业深度分析及“十三五”发展规划指
- 西班牙语发音快速入门
- 在“两会”结束时的讲话
- 2015贵州省会计人员继续教育考试技巧与口诀
- 网络程序设计试题A卷-2013(李金库)
- 2018大学生金工实习报告4篇
- 2017年食品加工厂项目可行性研究报告
- BLDC控制 - 图文
- 自动控制原理—试卷B(胡俊峰)
- 经典医疗整形美容广告文案
- 磁悬浮列车文献综述
- 汽车销售系统实训报告