《算法分析与设计试卷-》

《算法分析与设计》试卷（A)

(时间90分钟 满分10０分)

题号 分数 阅卷人 阅卷人 一 得分 二 三 四 一、填空题(30分，每题２分）。

D 原问题和子问题使用相同的方法解

8．用动态规划算法解决最大字段和问题，其时间复杂性为（ B ）． A.loｇn B.n Ｃ.n2 D．nlogｎ

合计 核分人 复核人 9.解决活动安排问题,最好用( B )算法ﻫA．分治 B．贪心C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ Ｂ ） A.递归函数

Ｂ.剪枝函数

ﻩC。随机数函数ﻩﻩ D．搜索函数

11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法，以下除（ C )之外都是最常见的方式.ﻫA.队列式分支限界法 Ｂ.优先队列式分支限界法ﻫC.栈式分支限界法 D．FＩFＯ分支限界法

12. ．回溯算法和分支限界法的问题的解空间树不会是( D ).

D、回溯法

Ａ.有序树 Ｂ．子集树C.排列树 D.无序树1ﻫ３．优先队列式分支限界法选取扩展结点的原则是( C ）。 A、先进先出

Ｂ、后进先出 ﻩﻩＣ、结点的优先级 D、随机

１．最长公共子序列算法利用的算法是（ B )。 Ａ、分支界限法ﻩ

B、动态规划法ﻩﻩﻩC、贪心法 ﻩ

2．在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ B ).

Ａ.回溯法 B．分支限界法C.回溯法和分支限界法 Ｄ.回溯法求解子集树问题 ３. 实现最大子段和利用的算法是（ B )。 A、分治策略

ﻩﻩB、动态规划法ﻩ

ﻩC、贪心法ﻩﻩ D、回溯法

１4．下面是贪心算法的基本要素的是（ Ｃ ）。 Ａ、重叠子问题ﻩ

Ｂ、构造最优解ﻩ

C、贪心选择性质

Ｄ、定义最优解

１5．回溯法在解空间树T上的搜索方式是（ A ).ﻫＡ.深度优先 B．广度优先 C．最小耗费优先 Ｄ．活结点优先 二、填空题（２0分，每空1分）。 阅卷人 得分 4．.广度优先是( A )的一搜索方式。

A、分支界限法 B、动态规划法 Ｃ、贪心法 D、回溯法 5.衡量一个算法好坏的标准是( Ｃ ）。

A 运行速度快 B 占用空间少 Ｃ 时间复杂度低 Ｄ 代码短 6．Sｔｒasｓen矩阵乘法是利用( A）实现的算法。 Ａ、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是 （ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并

--

1.算法由若干条指令组成的又穷序列,且满足输入、 输出 、 确定性 和 有限性 四个特性。

２．分支限界法的两种搜索方式有 队列式(ＦＩFＯ)分支限界法 、 优先队列式分支限界法 ，用一个队列来存储结点的表叫 活节点表 。 ３. 直接或间接 调用自身的方法叫 递归算法 。 4、大整数乘积算法是用 分治算法 来设计的。

--

５、以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 ６．动态规划的子问题 重叠 。

7．贪心算法的选择性质是 贪心选择性质 、动态规划法的选择性质是 最优子结构性质 。

8．问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。

９．以深度优先方式搜索问题解的算法称为 回溯法 。

10、快速排序法的三个步骤为： 分解 、 递归求解 、 合并 。

11、贪心算法的基本要素是 贪心选择性质 和 最有子结构性质 性质 。 三、问答题(30分,每题6分）。 阅卷人 得分

2．解释什么是NＰ类问题。

ＮP问题是指还未被证明是否存在多项式算法能够解决的问题,而其中NP完全问题又是最有可能不是Ｐ问题的问题类型。所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NＰ完全的问题具有如下性质：它可以在多项式时间内求解,当且仅当所有的其他的NＰ-完全问题也可以在多项式时间内求解。

3．动态规划法的4个步骤设计是什么?

（1)找出最优解的性质，并刻画其结构特征; （2)．递归地定义最优值;

(３)以自底向上的方式计算出最优值；

4.用回溯法解题通常包含几个步骤？

（1）O(２) （2）O(n）/ O(logｎ) (3）O(1)

--

n

1． 计算下列函数的渐进表达式（1）n2/102n(２)10log３n; (３) 2１＋1/ｎ;

(1)针对所给问题,定义问题的解空间； (2）确定易于搜索的解空间结构；

（3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

5 简述分支限界法与回溯法的异同点。

相同点:二者都是一种在问题的解空间树T上搜索问题解的算法。 不同点:1.在一般情况下，分支限界法与回溯法的求解目标不同。

--

回溯法的求解目标是找出Ｔ中满足约束条件的所有解，而分支限界法的求解目标则 是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值 达到极大或极小的解,即在某种意义下的最优解。

2.回溯法与分支-限界法对解空间的搜索方式不同，回溯法通常采用尝试优先搜索，而分支限界法则通常采用广度优先搜索。

3.对节点存储的常用数据结构以及节点存储特性也各不相同，除由搜索方式决定的不同的存储结构外，分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索

四、算法设计与分析（26分，1题１1分，2题15分)。 阅卷人 得分 用动态规划策略求解最长公共子序列问题: (1）给出计算最优值的递归方程。

（2)给定两个序列Ｘ={B,C,D,A },Y=｛A,Ｂ,C,B}，请采用动态规划策略求出

其最长公共子序列，要求给出过程。

(１)

引进一个二维数组c[］[],用c[i][j]记录X[i]与Ｙ[j］ 的ＬCS 的长度，b[i］[ｊ]记录ｃ［ｉ］［j]是通过哪一个子问题的值求得的，以决定搜索的方向。 我们是自底向上进行递推计算,那么在计算c［ｉ,j］之前，c[i-1][j－1]，c［i-1][j]与ｃ[i][ｊ-1]均已计算出来。此时我们根据Ｘ［i] = Y［j]还是X[i] !＝ Ｙ[ｊ]，就可以计算出c［i］[ｊ］。

问题的递归式写成:

--

(2)(2)

Ｙ A B C Ｂ X 0 0 0 0 B 0 0 １ 1 1 Ｃ 0 ０ 1 2 2 Ｄ 0 ０ 1 ２ A 0 １ １ 2

2 最长公共子序列:{ＢC}

２