海大算法设计与分析考试复习试题

.

16 最坏情况下的时间复杂性和平均时间复杂性有什么不同？

参考解答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：

W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：

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]

参考解答：不相同。目标函数：获得最大利润。最优量度：最大利润/重量比。 19 采用回溯法求解的问题，其解如何表示？有什么规定？

参考解答：问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i

参考解答：在解空间树上跳跃式地深度优先搜索，即用判定函数考察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)

参考解答：二分检索算法的最多的比较次数为 log n 。 26 快速排序算法最坏情况下需要多少次比较运算？

参考解答：最坏情况下快速排序退化成冒泡排序，需要比较n2次。 27 贪心算法的基本思想？

参考解答：是一种依据最优化量度依次选择输入的分级处理方法。基本思路是：首先根据题意，选取一种量度标准；然后按这种量度标准对这n个输入排序，依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中

28 回溯法的解（x1,x2,……xn）的隐约束一般指什么？

参考解答：回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种

. .

.

关系。

29 阐述归并排序的分治思路。

参考解答：讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。

30 快速排序的基本思想是什么。

参考解答：快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。

31 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？ 参考解答：在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。

32 什么是哈密顿环问题？

参考解答：哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置。

33 用回溯法求解哈密顿环，如何定义判定函数？

参考解答：当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1], X[k])≠∞，如果k=-1，则C(X[k], X[1]) ≠∞。

. .

.

34 请写出prim算法的基本思想。

参考解答：思路是：最初生成树T为空，依次向内加入与树有最小邻接边的n-1条边。处理过程：首先加入最小代价的一条边到T，根据各节点到T的邻接边排序，选择最小边加入，新边加入后，修改由于新边所改变的邻接边排序，再选择下一条边加入，直至加入n-1条边。

三、算法设计题

1.【最长上升子序列问题】（8分）—— 提示：此题可采用动态规划算法实现

对于给定的一个序列(a1,a2,上升的子序列(ai1,ai2,,aN)，1?N?1000。我们可以得到一些递增

?iK?N。比如，对于序列(1, 7,

,aiK)，这里1?i1?i2?3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。你的任务：就是对于给定的序列，求出最长上升子序列的长度。要求写出你设计的算法思想及递推函数的公式表达。. 参考解答：设f(i)表示：从左向右扫描过来直到以a[i]元素结尾的序列，获得的最长上升子序列的长度，且子序列包含a[i]元素（1?i?n）。

1i?1??f(i)??max{f(j)?1:当a[i]?a[j];1?j?i}i?1

?1i?1;?j(1?j?i),都有a[i]??a[j]?即，f(i)是从f(1)，f(2)……到f(i?1)中找最大的一个值，再加1。或者就是1。主要是看a[i]这个元素能否加入到之前已经获得的最长上升子序列，如果能加入，是之前已获得的最长上升子序列长度加一；如果不能加入，就取这最后一个元素作为一个单独子序列，长度为1。

最后，所要求的整个序列的最长公共子序列长度为max{f(i): 1<=i<=n}

. .