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

201703考试批次 《算法与数据分析》结课作业 学生姓名 学号 201209338664 专 业 北京语言大学网络教育学院 《算法与数据分析》结课作业 注意： 本学期所布置的结课作业，请同学一律按照以下要求执行： 1) 结课作业提交起止时间：2017年1月21日--3月20日。（届时平台自动关闭，逾期不予接收。） 2) 结课作业课程均需通过“离线作业”栏目提交电子版，学院不收取纸介的结课作业，以纸介回寄的作业一律视为无效； 3）截止日期前可多次提交，平台只保留最后一次提交的文档，阅卷时以最后一次提交的结课作业为准，截止日期过后将关闭平台，逾期不交或科目提交错误者，按0分处理； 4) 提交文档要求：提交的文档格式为doc、rar，大小10M以内； 5) 必须严格按照每门课程的答题要求完成作业，没有按照学院要求来做的结课作业，将酌情扣分。 论述题(本大题共5小题,请任选其中两道题作答,每小题25分，总分50分) 分治法所能解决的问题一般具有哪些特征。 分治法所能解决的问题一般具有的几个特征是： （1）该问题的规模缩小到一定的程度就可以容易地解决； （2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质; （3）利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 设计算法用分支限界法设计算法的步骤是： (1)针对所给问题，定义问题的解空间（对解进行编码）； (2)确定易于有哪些信誉好的足球投注网站的解空间结构（按树或图组织解） ； (3)以广度优先或以最小耗费（最大收益）优先的方式有哪些信誉好的足球投注网站解空间，并在有哪些信誉好的足球投注网站过程中用剪枝函数避免无效有哪些信誉好的足球投注网站。 常见的两种分支限界法的算法框架常见的两种分支限界法的算法框架 （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 回溯法中常见的两类典型的解空间树是子集树和排列树。 当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。 9 这类子集树通常有2n个叶结点，遍历子集树需O(2n)计算时间 。 当所给的问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。这类排列树通常有n!个叶结点。遍历排列树需要O(n!)计算时间。 5．分支限界法的有哪些信誉好的足球投注网站策略是什么？ 分支限界法的有哪些信誉好的足球投注网站策略是： 在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速有哪些信誉好的足球投注网站的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使有哪些信誉好的足球投注网站朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。 给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分有哪些信誉好的足球投注网站的算法，并分析其时间复杂度。 templateclass Type 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(xa[middle])left=m；elseright=middle-1;；Return-1;；时间复杂性为O(logn)； void MergeSort(Type a[], int left, int right) { if (leftright) {//至少有2个元素 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)。 N皇后回溯法。 bool Queen::Place(int k) { //检查x[k]位置是否合法 for (int j=1;jk;j++) if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false; return true; } void Queen: