算法分析与设计期末考试模拟试题一
更新时间:2023-05-16 23:52:01 阅读量: 实用文档 文档下载
第 1 页 (共 4 页) 算法分析与设计期末考试模拟试题一
课程名称:__ 算法分析与设计 考试形式: 闭 卷
学习中心:_________ 考试时间: 90分钟
姓 名:_____________ 学 号:
一、填空题(每小题4分,共计40分)
1. 通常只考虑三种情况下的时间复杂度,即 情况、
情况和 情况下的时间复杂度,分别记为T max (N)、T min
(N) 和T avg (N),实践表明可操作性最好且最有实际价值的是 情况下的时间复杂度。
2. n n 1032 的渐近表达式是 ,
)log(3n 的渐近表达式是 。
3. 根据符号O 的定义易知O(1)=O(2),用O(1)和O(2)表示同一个方法
时,差别仅在于其中的 。
4. 递归算法是指 的算法,递归函数
是指 的
函数。
5. 贪心算法总是做出在当前看来_____________的选择,也就是说,贪
心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的
________________。
6. 如果某问题具有________________________和
___________________________两个重要性质,该问题可以用贪心算
法求解。
7. 单源最短路径问题适合用_______________算法来求解、0-1背包问
题适合用_____________算法来求解。
8. 分治法是将一个规模为n的问题分解为k个规模________的子问题,
这些子问题___________且与原问题__________。递归地求解这些子
问题,然后将各个子问题的解_________得到原问题的解。
9. 动态规划算法的两个基本要素是____________________和
____________________。
10.___ 算法可以有效地解凸多边形最优三角剖分问题,
而____________算法是求解最优装载问题的有效方法。
二、简答题(每小题10分,共计40分)
1. 如果只需要求解问题的最优值,动态规划算法步骤是什么?如果需要构造最优解,则还需要加上什么步骤?
2. 请简述什么是贪心选择性质
3. 请简述什么是最小生成树。
4. 请简述贪心算法比动态规划算法效率高的原因。
三、算法分析和设计题(每小题10分,共计20分)
1. 请写出汉诺塔问题的简要递归算法。
2. 请设计一个在有序数组a[1..n]中二分搜索元素x的递归算法,要求若x在数组中则返回其下标否则返回0.
算法分析与设计模拟试题一答案
一、填空题答案(每小题4分,共计40分)
第 2 页(共 4 页)
第 3 页 (共 4 页) 1. 最坏、最好、平均、最坏
2.
)(2n O 、)(log n O 3. 常数因子
4. 直接或间接地调用自身、用函数自身给出定义
5. 最好、局部最优选择
6. 贪心选择性质、最优子结构性质
7. 贪心算法、动态规划算法
8. 较小、互相独立、相同、合并
9. 最优子结构(性质)、子问题重叠(性质)
10.动态规划算法、贪心算法。
二、简答题答案(每小题10分,共计40分)
1. 如果只需要求解问题的最优值,动态规划算法步骤如下:
(1)找出最优解的性质,并刻画其结构特征;
(2)递归地定义最优值;
(3)以自底向上的方式计算出最优值;
如果需要构造最优解,则还需要加上如下步骤:
(4)根据计算最优值时得到的信息,构造最优解。
2. 所谓贪心选择性质是指,所求问题的全局最优解可以通过一系列局
部最优选择,即贪心选择来达到。
3. 如果G 的子图G ’是一棵包含G 的所有顶点的树,则称G ’为G 的生成树。生成树上各边权的总和称为该生成树的耗费。在G 的所有生成树中,耗费最小的生成树称为G 的最小生成树。
4. 动态规划算法需要知道所有子问题的解,而贪心算法不需要知道所有子问题的解,它只是在每一步迭代中选择看起来最好的解,并不从整体进行最优考虑,因此效率较高。
三、算法分析和设计题答案(每小题10分,共计20分)
1. 汉诺塔问题的递归算法如下:
public static void Hanoi(int n, int a, int b, int c)
第 4 页 (共 4 页)
{ if( n>0 )
{
Hanoi( n-1, a,c,b );
Move( a, b );
Hanoi( n-1, c,b,a );
}
} 2. 算法如下:
输入:正整数n 和存储n 个元素的数组a[1..n],被搜索的元素x 输出:若x 在数组中则返回其下标否则返回0
i=binarysearch(1,n,a,x);
return I;
end BINARYSEARCH1
过程 binarysearch(low,high,a,x)
//在数组a 的下标为low 到high 范围内寻找x, //若找到x 则返回其下标否则返回0
if low>high then
return 0;
else
mid=[]2/)(high low +;
if a[mid]=x then
return mid;
else if a[mid]<x then
return binarysearch(low,mid-1,a,x); else return binarysearch(mid+1,high,a,x); end if
end if
正在阅读:
算法分析与设计期末考试模拟试题一05-16
Reseaurant Promotions五星级酒店餐饮开业促销方案08-31
竞赛第二讲 运动学01-06
阅读综合练习七04-19
2019年《动物防疫法》知识竞赛试题库及答案(完整版)06-09
数学学习的心理辅导12-25
幼儿园突发事件应急预案04-23
氩弧焊安全操作规程05-15
《信息系统安全等级保护基本要求》培训教材07072606-06
怎样评估自己的发展史06-18
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 模拟试题
- 算法
- 期末
- 分析
- 考试
- 设计
- 2016大兴区高三理科综合能力测试一模(化学部分)试卷及答案
- 数学知识的记忆(修改稿)
- 2021-2022学年度人教版二年级上册健康教学计划
- 黑格尔绝对理念的历史地位
- 苏教版三年级数学上册口算笔算竞赛题
- 远红外光谱及其应用
- 日语商务写作:什么样的简历能够获得HR的青睐
- 外源一氧化氮对NaCl胁迫下番茄幼苗生理影响
- 中国利用外资中存在的问题及对策初探
- 《机械设计基础》第1章:绪论
- 制度Microsoft Word 文档
- 2.1-2.5.4时域离散信号和系统的频域分析
- 2011年中考化学专题训练-气体的制取、干燥与净化
- 小学教师应具备的基本素质
- 上病下治:18个上下对应而效用神奇的穴位
- 班主任工作计划幼儿园秋季中班班主任工作计划
- An event-driven framework for the simulation of networks of spiking neurons
- 马克思主义哲学研究综述
- 陕西省中考化学模拟试卷11
- 2010年第一学期高三英语期中测试题及答案