20141210--计科 - 算法分析与设计试卷(A)

…………………… 算法分析与设计 课程 考试试卷（第 A 卷）

考试专业班级 计科12级 考试形式 考试时间 120 分钟 考试学期 考试类型 命题教师 徐晓蓉 题号 分值 D. 无论消耗多少计算机时间和空间也不能求解

3．分枝限界法在解空间树T上的搜索方式是（ ）。

A．深度优先

C．最小耗费优先

B．广度优先 D．活结点优先

一 30 二 20 三 25 四 25 五 六 七 八 总分 4．一个使用函数自身给出定义的函数称为（ ）函数

A、自定义 B、递归 C、反身 D、可解

5. 下列不属于NP问题的是（ ）。

A. 0/1背包问题 B. TSP问题 C. 皇后问题 D. 排序问题

系学 号 姓 名 不 准级超 过 密 封 线 ，班否 则 试学卷号作 废 ， 成 绩 记姓零名分 。 一、填空题（30分，每空2分）

1、算法是 。 2、算法复杂度是指算法执行过程中所需空间和 资源的量。 3、凡渐进时间复杂度以 为界的算法称做多项式时间算法。

4、若我们可计算得到某算法的时间复杂度为T(n)=10n2+9nlogn+1则用大O表示法T(n)= 。

5、一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二， ；第三， 。

6、用 方法适合求解具有最优子结构特性和最优量度标准的最优化问题。 7、在使用动态规划法求解最长公共子序列问题时，需定义一个二维数组来保存最长公共子序列的长度，设c[i][j]保存Xi=(x1,x2,…xi)和Yj=(y1,y2,…yj)的最长公共子序列的长度.那么,当i=0或j=0时, c[i][j]= ;若xi =yj(i,j>0),则c[i][j]= ;若xi ≠yj(i,j>0),则c[i][j]= 。

8、使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为 ；广度优先生成结点，并使用剪枝函数的方法称为 。

9， 函数和 函数统称为剪枝函数。 10、回溯法本质上是一种以 优先方式的搜索过程。

二 选择题（20分，每小题2分）

1．对于给定的问题，考虑算法复杂性的意义在于（ ）。

A. 设计出复杂性尽可能低的算法

B. 若该问题已有多种算法时，选择其中复杂性低的求解问题 C. 提高算法设计的学术水平层次

D. 判断算法的正确性

2．下列关于难处理问题的说法正确的是（ ）。

A. 能在多项式时间内求解的问题

B. 不存在多项式时间内求解算法的问题

C. 至今还没有找到多项式时间算法求解的问题

6．有一段程序如下：

void GreedyKnapsack (float *x)

//前置条件：w[k]已按p[k]/w[k]的非增次序排序 {

float u=m;

for(int j=0;j

if(w[j]>u) break; x[j]=1.0; u=u-w[j]; }

if(j

请问下列关于这段程序的功能说法正确的是（ ）。

A. 采用贪心算法求解0/1背包问题 B. 采用贪心算法求解一般背包问题 C. 采用动态规划法求解一般背包问题 D. 采用分枝限界法求解0/1背包问题

7．对于0/1背包问题，用（ ）不一定求得最优解。

A. 分枝限界法 B. 回溯法 C. 动态规划法 D. 贪心算法

8．时间复杂性达到（ ）的算法称为最优算法。

A、次数 B、最大 C、下界 D、常数 9、n

皇后问题，若显式约束描述为:xi?{0，1…n-1}且

xi?xj(i?j时)(0?i,j?n?1)则解空间的大小为:（ ）

。 A. n！ B. nn C. （n?1）！ D. （n?1）（n?1）

10、用贪心法求解背包问题时，所选择的最优量度标准是（ ）

A．物品的重量 B. 物品的收益 C. 单位物品的收益 D. 背包容量

1

……………密………………封………………线……………………………………

学………………………三 算法设计策略。（25分）

1．有一八谜问题（八数码问题），初始状态和目标状态分别如下图所示。

8数码问题的初始状态为： 目标状态为：

1 2 3 4 5 7 8 6

1 2 3 4 5 6 7 8

系… 号… 姓… 名… 不 准密…级超… 过… 密… 封… 线… ，封班否… 则试… …学卷…号作废… ，… 成线 绩… 记… …姓零…名分。… ……………………… 请采用LC分枝限界法求解。

（1）定义代价估计函数?c ( X ) （2分）

（2）画出分枝限界法求解过程生成的状态空间树，并计算每个结点的代价估计函数

值（6分）

（3）请写出一个可行解。（1分）

2．对于以下5 个矩阵：M1: 2*3, M2: 3*6, M3: 6*4, M4: 4*2, M5: 2*7 ,

(1),用动态规划法求这5个矩阵相乘需要的最小数乘次数。（必须计算m和s矩阵，

否则，不给分）（6分）

(2),请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。（2分）

3. 设有0/1背包问题，n=5，(w0,w1,w2,w3,w4)=(2,6,3,4,4)，(p0,p1,p2,p3,p4)=( 3,15,6,8,10)，M=12。请采用回溯法求解其最优解，要求：

（1）画出回溯法求解过程中生成的状态空间树；（6分） （2）请求出最优解时的装包策略以及背包里的最大收益值。（2分）

四 算法设计（25分）

1、Fibonacci数列问题:已知Fibonacci数列为：1，1，2，3，5，8，13，21，34……….. (1)试给出Fibonacci数列第n项Fib(n)的递归定义式;（1分） (2)设计计算Fib(n)的递归算法;（5分）

(3)分析给出(2)中算法时间复杂度的递推公式;（2分） (4)使用迭代法计算(3)中的递推公式。（2分） 2、最优装载问题:

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载

问题是指在装载体积不受限制的情况下，求使得装箱数目最多的装载方案.

(1), 给出贪心法求解这一问题的最优量度标准；（2分） (2), 证明该问题具有最优子结构特性;（4分） (3), 编写装箱问题的贪心算法（6分）

(4), 设有重量为(7,2,6,9,3,5,4)的7个集装箱，轮船的载重为26,使用贪心法求其最优

解及最优解的值.（3分）

2