201703考试批次《算法与数据分析》（结课作业）

李老师

201703考试批次
《算法与数据分析》结课作业




学生姓名                      学习中心  
学号                           
专  业                        年级层次












北京语言大学网络教育学院
《算法与数据分析》结课作业
注意：
本学期所布置的结课作业，请同学一律按照以下要求执行：
1) 结课作业提交起止时间：2017年1月21日--3月20日。（届时平台自动关闭，逾期不予接收。）
2) 结课作业课程均需通过“离线作业”栏目提交电子版，学院不收取纸介的结课作业，以纸介回寄的作业一律视为无效；
3）截止日期前可多次提交，平台只保留最后一次提交的文档，阅卷时以最后一次提交的结课作业为准，截止日期过后将关闭平台，逾期不交或科目提交错误者，按0分处理；
4) 提交文档要求：提交的文档格式为doc、rar，大小10M以内；
5) 必须严格按照每门课程的答题要求完成作业，没有按照学院要求来做的结课作业，将酌情扣分。



一.        论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分)
1.        分治法所能解决的问题一般具有哪些特征。
2.        分支限界法设计算法有哪些步骤。
3.        常见的两种分支限界法的算法框架是什么？
4．回溯法中常见哪两类典型的解空间树？分析各自的使用场合及时间复杂度？
5．分支限界法的搜索策略是什么？
二.        算法设计题(本大题5小题,请任选其中两道题作答,每小题25分，总分50分)
1．        给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。
2．        利用分治算法写出合并排序的算法，并分析其时间复杂度。
3．        N皇后回溯法。
4．        最大团问题
5．        统计数字问题：一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6页用数字6表示，而不是06或006等。数字计数问题要求对给定书的总页码n(1≤n≤109)，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。输入数据、输出结果示例