算法分析与设计期末考试试卷B卷.docx
- 文档编号:4732558
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:5
- 大小:38.54KB
算法分析与设计期末考试试卷B卷.docx
《算法分析与设计期末考试试卷B卷.docx》由会员分享,可在线阅读,更多相关《算法分析与设计期末考试试卷B卷.docx(5页珍藏版)》请在冰点文库上搜索。
班级学号姓名
密封装订线密封装订线密封装订线
西南交通大学2015-2016学年第
(一)学期考试试卷
课程代码3244152课程名称算法分析与设计考试时间120分钟
题号
一
二
三
四
五
总成绩
得分
·
阅卷教师签字:
一、填空题(每空1分,共15分)
1、程序是
(1) 用某种程序设计语言的具体实现。
2、矩阵连乘问题的算法可由
(2)设计实现。
3、从分治法的一般设计模式可以看出,用它设计出的程序一般是(3)。
4、大整数乘积算法是用(4)来设计的。
5、贪心算法总是做出在当前看来(5)的选择。
也就是说贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的(6)。
6、回溯法是一种既带有(7)又带有(8)的搜索算法。
7、平衡二叉树对于查找算法而言是一种变治策略,属于变治思想中的(9)类型。
8、在忽略常数因子的情况下,O、和三个符号中,(10)提供了算法运行时间的一个上界。
9、算法的“确定性”指的是组成算法的每条(11)是清晰的,无歧义的。
10、问题的(12)是该问题可用动态规划算法或贪心算法求解的关键特征。
11、算法就是一组有穷(13),它们规定了解决某一特定类型问题的(14)。
12、变治思想有三种主要的类型:
实例化简,改变表现,(15)。
二、选择题(每题2分,共20分)
1、二分搜索算法是利用( )实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、衡量一个算法好坏的标准是()。
A、运行速度快B、占用空间少C、时间复杂度低D、代码短
3、能采用贪心算法求最优解的问题,一般具有的重要性质为:
()
A.最优子结构性质与贪心选择性质B.重叠子问题性质与贪心选择性质
C.最优子结构性质与重叠子问题性质
4、D.预排序与递归调用
4、常见的两种分支限界法为()
A、广度优先分支限界法与深度优先分支限界法;
B、队列式(FIFO)分支限界法与堆栈式分支限界法;
C、排列树法与子集树法;
D、队列式(FIFO)分支限界法与优先队列式分支限界法;
5、实现循环赛日程表利用的算法是( )。
A、分治策略 B、动态规划法
C、贪心法 D、回溯法
6、回溯法的效率不依赖于下列哪些因素()
A.满足显约束的值的个数 B.计算约束函数的时间
C.计算限界函数的时间 D.确定解空间的时间
7、使用分治法求解不需要满足的条件是()。
A、子问题必须是一样的B、子问题不能够重复
C、子问题的解可以合并D、原问题和子问题使用相同的方法解
8、实现合并排序利用的算法是()。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
9、背包问题的贪心算法所需的计算时间为()
A、O(n2n) B、O(nlogn) C、O(2n) D、O(n)
10、广度优先是()的一搜索方式。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
三、算法及程序分析(共25分)。
1.阅读下面的程序,按要求回答问题:
(共10分)
#include
#include
intvis[101][101];
intmap[101][101];
intR,C;
intdp(inti,intj);
intmain()
{
inti,j,ans,max;
scanf("%d%d",&R,&C);
for(i=0;i for(j=0;j scanf("%d",&map[i][j]); max=0; for(i=0;i memset(vis[i],-1,sizeof(vis[i])); for(j=0;j ans=dp(i,j); if(ans>max)max=ans; } } printf("%d\n",max); return0; } intdp(inti,intj) { intmax=0; if(vis[i][j]>0) returnvis[i][j]; if(i-1>=0) if(map[i-1][j]
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 期末考试 试卷