内容发布更新时间 : 2024/11/8 19:39:51星期一 下面是文章的全部内容请认真阅读。

一、问答题（30分）。

1．什么是最坏情况时间复杂性？什么是平均情况时间复杂性？ 答：最坏情况时间复杂性：

Tmax(N)?maxT(N,I)?max?tiei(N,I)??tiei(N,I*)?T(N,I*)I?DNI?DNi?1i?1kk平均情况时间复杂性：

Tavg(N)?

I*是DN中使T(N, I*)达到Tmax(N)的合法输入；P(I)是在算法的应用中出现输入I的概率 2．什么是递归算法？什么是递归函数？ 答：（1）递归算法:直接或间接地调用自身的算法； （2）递归函数:用函数自身给出定义的函数。 3．递归函数的二要素是什么？ 答：（1）边界条件（2）递归方程 4．分治法的设计思想是什么？

答：将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。

5．什么叫问题的最优子结构性质？

答：一个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 6．动态规划基本步骤是什么？ 答：（1）找出最优解的性质，并刻划其结构特征; （2）递归地定义最优值;

（3）以自底向上的方式计算出最优值;(4)根据计算最优值时得到的信息，构造最优解。 7．动态规划算法的基本要素是什么？举例说明一些可以用动态规划算法解决的问题。 答：（1）最优子结构性质和子问题重叠性质是动态规划算法的基本要素 （2）矩阵连乘问题，建立递归关系，求最优解，0-1背包问题等 8．说明分治法与动态规划法的相同点和不同之处？

答：同：基本思想都是将待求解问题分解成若干个子问题先求解子问题，然后从这些子问题的解得到原问题的解；

异：（1）适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要消耗指数时间；

（2）不同子问题的数目常常只有多项式量级，在用分治法求解时，有些子问题被重复计算了许多次。动态规划法保存已解决的子问题的答案，在需要时再找到已得到的答案，可以避免大量重复计算，从而得到多项式时间算法。

9．贪心算法的两个重要要素是什么？举例说明一些可以用贪心算法解决的问题。 答：（1）贪心选择性质和最优子结构性质。

（2）背包问题，单源最短路径，最小生成树问题等。 10．什么叫贪心选择性质？ 答：所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

11．贪心算法与动态规划算法的的相同点和不同之处？

答：同：贪心算法和动态规划算法都要求问题具有最优子结构性质

异：贪心具有贪心选择性质，这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

12．背包问题与0－1背包问题有何区别？

答：背包问题可以用贪心算法求解，而0-1背包问题不能用贪心算法求解。 13．回溯法与分支限界法之间的相同点是什么？不同之处在哪些方面？ 答：同：他们同是在问题的解空间树上搜索问题解的算法； 异：（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分

I?DN?P(I)T(N,I)??P(I)?te(N,I)iiI?DNi?1k支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解；

（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以

广度优先或以最小耗费优先的方式搜索解空间树。 14．分支限界法基本思想是什么？

答：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。 15．常用的剪枝函数有哪两类？ 答：（1）约束函数（2）限界函数 16．约束函数的功能是什么？

答：用约束函数在扩展结点处剪去不满足约束的子树 17．限界函数的功能是什么？

答：用限界函数剪去得不到最优解的子树 18.．常见的两种分支限界法是什么？ 答：（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

19．回溯法中剪枝函数有哪几类？各有何用途？ 答：（1）约束函数 限界函数 （2）用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。

20．什么是P问题和NP问题？ 答：（1）P（ Polynomial ）问题：如果一个问题可以找到一个能在多项式时间里解决它的算法，那么这个问题就属于P问题。

（2）NP（ Non-Deterministic Polynomial ）问题： NP问题不是非P类问题，是多项式复杂程度的非确定性问题。 是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。 21．什么是NP完全问题？

答：NP完全（NPC， Complete ）问题：如果问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题 。 22．NP-Hard问题？ 答：（1）NP-Hard问题要比NPC问题的范围广；

（2）NP-Hard问题同样难以找到多项式的算法，它不一定是NP问题；

（3）即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法；

（4）事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

二、证明题（算法时间复杂性）

☆（1）O（f）+O（g）=O(max(f,g)); ☆（2）O（f）+O（g）=O(f+g); 证明：令 F[N]=O[f],则存在自然数N1,C1,使得对任意的自然数N>=N1，有：F（N）<=C1f[N];同理令：G[N]=O[g],则存在自然数N2,C2,使得对任意的自然数N>=N2，有：G（N）<=C2g[N];令C3=max{C1,C2},N3=max{N1,N2},则对所有的N>=N3,有 F[N]<=C1f(N)<=C3f(N);G[N]<=C2f(N)<=C3g(N);

故有：O(f)+O(g)=F(N)+G(N)<=C3f(N)+C3g(N)=C3(f(N)+g(N))=O(f+g);因此有：O(f)+ O(g)= O(f+g)

（3）O（f）O（g）=O（fg）;

☆（4）如果g(N)=O(f(N)),则O(f)+O(g)=O(f);

（5）O（Cf(N)）=O(f(N)),其中C是一个正的常数； （6）f=O(f)

三、动态规划知识点——流水作业调度

问题: n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工,其中机器M2要等时间t后才可利用。可表示为T(N,t)。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 分析：

1.直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。 2.在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 3.设全部作业的集合为N={1，2，…，n}。

4.S?N是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2可能还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。

5.流水作业调度问题的最优值为 6.T(N,0)。

设?是所给n个流水作业的一个最优调度。它所需的加工时间为 a?(1)+T’。

其中T’是在机器M2的等待时间为b?(1)时，安排作业?(2)，…，?(n)所需的时间。 记S=N-{?(1)}，则有T’=T(S,b?(1))。

//说明了流水作业调度问题具有最优子结构的性质。

四、贪心算法知识点——活动安排问题（代码）

重点题型：

设待安排的11个活动的开始时间和结束时间按结束时间如下： i 1 2 1 3 4 5 6 5 7 6 8 3 9 10 11 8 0 5 7 S[i] 3 f[i] 5 2 12 8 4 13 14 11 9 10 8 12 6

算法greedySelector 的计算过程如上图所示。图中每行相应于算法的一次迭代。阴影