西安邮电大学算法资料.docVIP

选择： 1.算法的性质包括输入、输出、（ A ）、有限性。 A. 确定性 B. 随机性 C. 复杂性 D. 渐近复杂性 2.备忘录法是那种算法的变形（ B ）。 分治算法 B、动态规划算法 C、贪心算法 D、回溯法 3.具有最优子结构的算法有（ D ）。 A．概率算法 B．回溯法 C．分支限界法 D．动态规划法 4.回溯法解旅行商问题时的解空间树是（ B ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下面哪种函数是回溯法中避免无效有哪些信誉好的足球投注网站采取的策略（ C ）。 A、递归函数 B、随机函数 C、剪枝函数 D、有哪些信誉好的足球投注网站函数 简答： 算法的概念：算法是指解决问题的一种方法或一个过程。 算法的性质：算法是若干指令的有穷序列，满足性质：（1）输入：有外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令是清晰，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。（5）可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现。 程序的概念：程序是算法用某种程序设计语言的具体实现 算法与程序的不同：（1）算法是给人来读的，直接将算法输入计算机是不能运行的（2）程序可以不满足算法的“有限性”。 算法复杂性：算法所需要的计算机资源，所需资源多，算法的复杂性高；反之则复杂性低。【时间复杂性（指令数）、空间复杂性（存储器大小）、渐近复杂性】 计算复杂性：是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数（时间复杂度），二是计算所需的存储单元数量（空间复杂度）。 渐近复杂性的基本分析方法 可操作性最好且最有实际价值的是最坏情况下的时间复杂性。 算法渐近复杂性分析中常用函数：单调函数；取整函数；多项式函数；指数函数；对数函数；阶乘函数； 第 2 章 递归与分治策略 （1）分治法的基本思想：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。 （2）分治法所能解决问题具有的特征：将要求解的较大规模的问题分割为 k 个较小规模的子问题。对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。 （3）分治法与动态规划算法的相同点和不同点是什么：分治法与动态规划的相同点：分治法与动态规划，二者要求原问题具有最有子结构，都是将问题分而治之分解成若干个规模较小的子问题；不同点：动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分；算法的应用：装配线，矩阵乘法，最长公共子序列，构造最优的二叉树分治法是将原问题分解为多个子问题，利用递归对各个子问题独立求解，最后利用各子问题的解进行合并形成原问题的解。分治法将分解后的子问题看成是相互独立的。 （4）二分有哪些信誉好的足球投注网站方法的基本思想：将 n 个元素分成个数大致相同的两半，取 a[ n / 2 ]与欲查找的 x 作比较，如果 x = a[ n / 2 ]则找到 x，算法终止；如果 x a[ n / 2 ]，则只要在数组 a 的左半部继续有哪些信誉好的足球投注网站 x（这里假设数组元素呈升序排列）。如果x a[ n / 2 ]，则只要在数组 a 的右半部继续有哪些信誉好的足球投注网站 x。 ！（5）二分有哪些信誉好的足球投注网站方法的程序设计：充分利用了元素间的次序关系，采用分治策略 （6）棋盘覆盖问题的基本思想：棋盘覆盖问题初看起来很难下手解决，但仔细思考后可以采用分治策略设计针对该问题的一个巧妙解法：如下图所示，当 k 0 时，将 2k × 2k 棋盘分割为 4 个 2k-1 × 2k-1 子棋盘，如图 (a) 所示。显然特殊方格必位于图 (a) 中 4 个较小子棋盘之一中，其余 3 个子棋盘中则无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L 型骨牌覆盖这 3 个较小棋盘的会合处，如图 (b) 和 (c) 所示。从而将原问题转化为 4 个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘 1×1（易于求解）。 （7）合并排序基本思想是：（1）将待排序元素分成大小大致相同的两个子集合，（2）分别对两个子集合进行排序，（3）最终将排好序的子集合合并成为所要求的排好序的集合。 （8）快速排序基本思想：排序子数组 a[ p : r ]，步骤如下：（1）分解：以 a[ p ] 为基准元素将 a[ p : r ] 分成 3 段：