西安邮电大学算法资料

《西安邮电大学算法资料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、选择：1.算法的性质包括输入、输出、（A）、有限性。A.确定性B.随机性C.复杂性D.渐近复杂性2.备忘录法是那种算法的变形（B）。A、分治算法B、动态规划算法C、贪心算法D、回溯法3.具有最优子结构的算法有（D）。A．概率算法B．回溯法C．分支限界法D．动态规划法4.回溯法解旅行商问题时的解空间树是（B）。A、子集树B、排列树C、深度优先生成树D、广度优先生成树5.下面哪种函数是回溯法中避免无效搜索采取的策略（C）。A、递归函数B、随机函数C、剪枝函数D、搜索函数简答：（1）算法的概念：算法是指解决问题的一种方法或一个过程。（2）算法的性质：

2、算法是若干指令的有穷序列，满足性质：（1）输入：有外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令是清晰，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。（5）可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现。（3）程序的概念：程序是算法用某种程序设计语言的具体实现（4）算法与程序的不同：（1）算法是给人来读的，直接将算法输入计算机是不能运行的（2）程序可以不满足算法的“有限性”。（5）算法复杂性：算法所需要的计算机资

3、源，所需资源多，算法的复杂性高；反之则复杂性低。【时间复杂性（指令数）、空间复杂性（存储器大小）、渐近复杂性】（6）计算复杂性：是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数（时间复杂度），二是计算所需的存储单元数量（空间复杂度）。（7）渐近复杂性的基本分析方法（8）可操作性最好且最有实际价值的是最坏情况下的时间复杂性。（9）算法渐近复杂性分析中常用函数：单调函数；取整函数；多项式函数；指数函数；对数函数；阶乘函数；第2章递归与分治策略（1）分治法的基本思想：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成

4、大问题的解。（2）分治法所能解决问题具有的特征：将要求解的较大规模的问题分割为k个较小规模的子问题。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。（3）分治法与动态规划算法的相同点和不同点是什么：分治法与动态规划的相同点：分治法与动态规划，二者要求原问题具有最有子结构，都是将问题分而治之分解成若干个规模较小的子问题；不同点：动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为

5、相互间有联系，有重叠的部分；算法的应用：装配线，矩阵乘法，最长公共子序列，构造最优的二叉树分治法是将原问题分解为多个子问题，利用递归对各个子问题独立求解，最后利用各子问题的解进行合并形成原问题的解。分治法将分解后的子问题看成是相互独立的。（4）二分搜索方法的基本思想：将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如果xa[n/2]，则只要在数组a的右半部继续搜索x。！（5）二分搜索方法的程序设计：

6、充分利用了元素间的次序关系，采用分治策略（6）棋盘覆盖问题的基本思想：棋盘覆盖问题初看起来很难下手解决，但仔细思考后可以采用分治策略设计针对该问题的一个巧妙解法：如下图所示，当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1子棋盘，如图(a)所示。显然特殊方格必位于图(a)中4个较小子棋盘之一中，其余3个子棋盘中则无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如图(b)和(c)所示。从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1（易于求解

7、）。（7）合并排序基本思想是：（1）将待排序元素分成大小大致相同的两个子集合，（2）分别对两个子集合进行排序，（3）最终将排好序的子集合合并成为所要求的排好序的集合。（8）快速排序基本思想：排序子数组a[p:r]，步骤如下：（1）分解：以a[p]为基准元素将a[p:r]分成3段：a[p:q-1]、a[q]、a[q+1:r]。满足条件：a[p:q-1]中任何一个元素<=a[q]；a[q+1:r]中任何一个元素>=a[q]。下标q在划分过程中确定。（2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。（3）合并：

8、对a[p:q-1]和a[q+1:r]的排序在各自的范围内进行，因此排好序后不需任何运算整个数组a[p:r]即完成排序。第3章动态规划（1）动态规划的基