2015算法设计与分析考试复习刚要及习题(2)

构性质。 参考解答：最优子结构性质是指大问题的最优解包含子问题的最优解。 动态规划方法是自底向上计算各个子问题的最优解，即先计算子问题的最优解，然后再利用子问题的最优解构造大问题的最优解，因此需要最优子结构 8.请说明：(1)优先队列可用什么数据结构实现？(2)优先队列插入算法基本思 4

想？(3)优先队列插入算法时间复杂度？ 参考解答：

（1）堆。(1分) （2）在小根堆中，将元素x插入到堆的末尾， 然后将元素x的关键字与其双亲的关键字比较， 若元素x的关键字小于其双亲的关键字， 则将元素x与其双亲交换，然后再将元素x与其新双亲的关键字相比，直到元素x的关键字大于双亲的关键字，或元素x到根为止。(4分) （3）O( log n)（1分） 9..设计动态规划算法的主要步骤是怎么的？请简述。 参考解答：（1）找出最优解的性质，并刻划其结构特征。(6分) （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造最优解。 10.分治法所能解决的问题一般具有哪几个特征？请简述。 参考解答：（1）该问题的规模缩小到一定的程度就可以容易地解决；(6分) （2）该问题可以分解为

若干个规模较小的相同问题，即该问题具有最优子结构性质; （3） 利用该问题分解出的子问题的解可以合并为该问题的解； （4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 11.分支限界法的搜索策略是什么？ 参考解答：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值（限界），并根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。(6分) 12 算法的要特性是什么？ 参考解答：确定性、可实现性、输入、输出、有穷性 13 算法分析的目的是什么？ 参考解答：分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 14 算法的时间复杂性与问题的什么因素相关？ 参考解答：算法的时间复杂性与问题的规模相关，是问题大小n的函数。 15 算法的渐进时间复杂性的含义？ 参考解答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用

T(n)的数量级 5

(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 16 最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：

max{ T(n，I) } , I∈Dn

W(n) =

平均时间复杂性是所有输入实例的处理

时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 17 简述二分检索（折半查找）算法的基本过程。 参考解答：设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]

跳跃式地深度优先搜索，即用判定函数考察x[k]的取值，如果x[k]是合理的就搜索x[k]为根节点的子树，如果x[k]取完了所有的值，便回溯到x[k-1]。 21 n皇后问题回溯算法的判别函数place的基本流程是什么？ 参考解答：将第K行的皇后分别与前k-1行的皇后比较，看是否与它们相容，如果不相容就返回false，测试完毕则返回true。 22 为什么用分治法设计的算法一般有递归调用？ 参考解答：子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归. 23 为什么要分析最坏情况下的算法时间复杂性？ 参考解答：最坏情况下的时间复杂性决定算法的优劣，并且最坏情况下的时间复杂性较平均时间复杂性游可操作性。 24 简述渐进时间复杂性上界的定义。 参考解答：T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)

27 贪心算法的基本思想？ 参考解答：是一种依据最优化量度依次选择输入的分级处理方法。基本思路

是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中 28 回溯法的解（x,x,??x）的隐约束一般指什么？ 12n参考解答：回溯法的解（x,x,??x）的隐约束一般指个元素之间应满足的某12n种关系。 29 阐述归并排序的分治思路。 参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。 30 快速排序的基本思想是什么。 参考解答：快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。 31 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 参考解答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函 …… 此处隐藏：656字，全部文档内容请下载后查看。喜欢就下载吧 ……