[算法期末参考.doc

最 最重要的是期中考试的试卷题型+书例题。 过一下： 1.算法的复杂性有 时间 复杂性和 空间 复杂性之分。 程序是?????用某种程序设计语言的具体实现。 、算法的“确定性”指的是组成算法的每条是清晰的，无歧义的。 矩阵连乘问题的算法可由设计实现。 拉斯维加斯算法找到的解一定是。 算法是指解决问题的或。 。 问题的是该问题可用动态规划算法或贪心算法求解的关键特征。 以深度优先方式系统有哪些信誉好的足球投注网站问题解的算法称为。 数值概率算法常用于的求解。 计算一个算法时间复杂度通常可以计算循环次数 、基本操作的频率或计算步。 利用概率的性质计算近似值的随机算法是__数值概率算法，运行时以一定的概率得到正确解的随机算法是__蒙特卡罗算法_____________________。 解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法，分支限界法。 、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题，只使用约束条件进行裁剪的是N皇后问题。 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 矩阵连乘问题的算法可由设计实现。 拉斯维加斯算法找到的解一定是。 动态规划算法的基本思想是将待求解问题分解成若干，先求解，然后从这些的解得到原问题的解。 大整数乘积算法是用来设计的。 以广度优先或以最小耗费方式有哪些信誉好的足球投注网站问题解的算法称为。 舍伍德算法总能求得问题的。 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 分支限界法 简述二分检索（折半查找）算法的基本过程。 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]x，则A[i：(i+j)/2-1]找x，否则在A[ (i+j)/2+1：j] 找x。上述过程被反复递归调用。 背包问题的目标函数和贪心算法最优化量度相同吗？ 不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。 采用回溯法求解的问题，其解如何表示？有什么规定？ 问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(in)一定合理。 回溯法的有哪些信誉好的足球投注网站特点是什么？ 在解空间树上跳跃式地深度优先有哪些信誉好的足球投注网站，即用判定函数考察x[k]的取值，如果x[k]是合理的就有哪些信誉好的足球投注网站x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。 n皇后问题回溯算法的判别函数place的基本流程是什么？ 将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。 为什么用分治法设计的算法一般有递归调用？ 子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。 为什么要分析最坏情况下的算法时间复杂性？ 最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。 简述渐进时间复杂性上界的定义。 T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)f(n)，这种关系记作T(n)=O(f(n))。 二分检索算法最多的比较次数？ 二分检索算法的最多的比较次数为 log n 。 快速排序算法最坏情况下需要多少次比较运算？ 最坏情况下快速排序退化成冒泡排序，需要比较n2次。 贪心算法的基本思想？ 是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。 回溯法的解（x1,x2,……xn）的隐约束一般指什么？ 回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。 阐述归并排序的分治思路。 将数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。 快速排序的基本思想是什么。 快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放