201703考试批次《算法与数据分析》(结课作业)
更新时间:2024-04-25 17:38:01 阅读量: 综合文库 文档下载
- BJS 201703推荐度:
- 相关推荐
201703考试批次 《算法与数据分析》结课作业
学生姓名学号 专 业
徐前峰 计算机科学与技术 济宁奥鹏 年级层次 转升本
学习中心 201209338664
北京语言大学网络教育学院
《算法与数据分析》结课作业
注意:
本学期所布置的结课作业,请同学一律按照以下要求执行: 1) 结课作业提交起止时间:2017年1月21日--3月20日。(届时平台自动关闭,逾期不予接收。)
2) 结课作业课程均需通过“离线作业”栏目提交电子版,学院不收取纸介的结课作业,以纸介回寄的作业一律视为无效;
3)截止日期前可多次提交,平台只保留最后一次提交的文档,阅卷时以最后一次提交的结课作业为准,截止日期过后将关闭平台,逾期不交或科目提交错误者,按0分处理; 4) 提交文档要求:提交的文档格式为doc、rar,大小10M以内;
5) 必须严格按照每门课程的答题要求完成作业,没有按照学院要求来做的结课作业,将酌情扣分。
一. 论述题(本大题共5小题,请任选其中两道题作答,每小题25分,总分50分)
1. 分治法所能解决的问题一般具有哪些特征。
分治法所能解决的问题一般具有的几个特征是:
(1)该问题的规模缩小到一定的程度就可以容易地解决;
(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
(3)利用该问题分解出的子问题的解可以合并为该问题的解;
(4)原问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。
2. 分支限界法设计算法有哪些步骤。
用分支限界法设计算法的步骤是:
(1)针对所给问题,定义问题的解空间(对解进行编码);
(2)确定易于搜索的解空间结构(按树或图组织解) ;
(3)以广度优先或以最小耗费(最大收益)优先的方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
3. 常见的两种分支限界法的算法框架是什么?
常见的两种分支限界法的算法框架
(1)队列式(FIFO)分支限界法:按照队列先进先出(FIFO)原则选取下一个节点为扩展节点。 (2)优先队列式分支限界法:按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
4.回溯法中常见哪两类典型的解空间树?分析各自的使用场合及时间复杂度?
回溯法中常见的两类典型的解空间树是子集树和排列树。
当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。 9
这类子集树通常有2n个叶结点,遍历子集树需O(2n)计算时间 。
当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。
5.分支限界法的搜索策略是什么?
分支限界法的搜索策略是:
在扩展结点处,先生成其所有的儿子结点(分支),然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点,加速搜索的进程,在每一个活结点处,计算一个函数值(限界),并根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。
二. 算法设计题(本大题5小题,请任选其中两道题作答,每小题25分,总分50分)
1. 给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x,返回
其在数组中的位置,如果未找到返回-1。写出二分搜索的算法,并分析其时间复杂度。
template
int BinarySearch(Type a[], const Type& x, int n) {//在a[0:n]中搜索x,找到x时返回其在数组中的位置,否则返回-1
Int left=0; int right=n-1; While (left<=right)
{int middle=(left+right)/2; if (x==a[middle]) return middle;
if(x>a[middle])left=m;elseright=middle-1;;Return-1;;时间复杂性为O(logn); 2. 利用分治算法写出合并排序的算法,并分析其时间复杂度。
void MergeSort(Type a[], int left, int right)
{
if (left int i=(left+right)/2; //取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } } 算法在最坏情况下的时间复杂度为O(nlogn)。 3. N皇后回溯法。 bool Queen::Place(int k) { //检查x[k]位置是否合法 for (int j=1;j if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen::Backtrack(int t) { if (t>n) sum++; else for (int i=1;i<=n;i++) {x[t]=i; if ( 约束函数 ) Backtrack(t+1); } } 4. 最大团问题 void Clique::Backtrack(int i) // 计算最大团 { if (i > n) { // 到达叶结点 for (int j = 1; j <= n; j++) bestx[j] = x[j]; bestn = cn; return;} // 检查顶点 i 与当前团的连接 int OK = 1; for (int j = 1; j < i; j++) if (x[j] && a[i][j] == 0) // i与j不相连 {OK = 0; break;} if (OK ) { // 进入左子树 x[i] = 1; cn++; Backtrack(i+1); x[i] = 0; cn--; } if (cn+n-i>bestn) { // 进入右子树 x[i] = 0; Backtrack(i+1); } } 5. 统计数字问题:一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通 常的习惯编排,每个页码都不含多余的前导数字0。例如,第6页用数字6表示,而不 9 是06或006等。数字计数问题要求对给定书的总页码n(1≤n≤10),计算出书的全部页码中分别用到多少次数字0,1,2,?,9。输入数据、输出结果示例 输入数据、输出结果示例 输入数据:11 输出结果:数 字: 0 1 2 3 4 5 6 7 8 9 用到次数: 1 4 1 1 1 1 1 1 1 1 void count(int n,int a[10]) {int i,x,y; for (i=0;i<=9;i++) a[i]=0; for (i=1;i<=n;i++) {x=i; while (x) {y=x; a[y]++; x/=10; } } }
正在阅读:
201703考试批次《算法与数据分析》(结课作业)04-25
部署企业中第一台Windows+Exchange Server 2010 - 图文03-26
开展安全生产隐患排查工作总结多篇精选07-30
兴旺发达的兔家族07-24
基于SCTP协议的并行多路径传输研究08-21
最新佛山市国星光电股份公司实习周记原创09-17
2016年北京工具钳工中级理论考试题09-20
学科课题研究03-14
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 批次
- 数据分析
- 算法
- 作业
- 考试
- 201703
- 中国用具市场发展研究及投资前景报告(目录) - 图文
- 家和万事兴(蔡礼旭老师主讲)
- 勤动脑多思考1
- 合肥工业大学自动控制理论综合实验倒立摆实验报告
- 中石北京 机械动力学 第一次在线作业 满分答案
- 小学六年级英语语法全
- 高中地理第01章地理环境与区域发展1.3第一章复习(2)限时考新人教
- 休闲会所技师管理处罚条例
- 2016年10月电子政务第一次作业
- 美国中医药政策缩编 - 图文
- 汉明编码和译码实验 - 图文
- 五年级语文每日一练
- 初步设计说明
- 银行资金回笼情况调查报告范文
- 高中音乐“创作”教学研究 - 歌曲主题的写作
- 治安形势分析
- 高考原创机械能守恒定律计算题及答案
- 2017年党员自查自纠工作报告方面存在问题整改措施材料
- 西方哲学智慧课后习题
- 2014noip复赛模拟练习11