学
号
姓
名
不
准
超
过
密
封
线
︐
否
则
试
卷
作
废
︐
成
绩
记
零
分
︒
︙
算法分析与设计 课程 考试试卷（第 A 卷）
︙
考试专业班级 计科 12 级 考试形式 考试时间 120 分钟
︙
︙
考试学期 考试类型 命题教师 徐晓蓉
︙
题号 一 二 三 四 五 六 七 八 总分
︙
︙
分值 30 20 25 25
︙
︙
︙
︙
一、填空题（30 分，每空 2 分）
︙
1、算法是 。
︙
2、算法复杂度是指算法执行过程中所需空间和 资源的量。
密
3、凡渐进时间复杂度以 为界的算法称做多项式时间算法。
︙
4、若我们可计算得到某算法的时间复杂度为 T(n)=10n
2
+9nlogn+1 则用大 O 表示法
︙
︙
T(n)= 。
︙
5、一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干
︙
个规模较小、相互独立且与原问题类型相同的子问题；第二， ；
︙
第三， 。
封
6、用 方法适合求解具有最优子结构特性和最优量度标准的最优化问题。
︙
7、在使用动态规划法求解最长公共子序列问题时，需定义一个二维数组来保存最长
︙
公共子序列的长度，设 c[i][j]保存 X
i
=(x
1
,x
2
,…x
i
)和 Y
j
=(y
1
,y
2
,…y
j
)的最长公共子序列的长度.
︙
那么,当 i=0 或 j=0 时, c[i][j]= ;若 x
i
=y
j
(i,j>0),则 c[i][j]= ;若 x
i
≠
︙
︙
y
j
(i,j>0),则 c[i][j]= 。
︙
8、使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为 ；广
线
度优先生成结点，并使用剪枝函数的方法称为 。
︙
9， 函数和 函数统称为剪枝函数。
︙
10、回溯法本质上是一种以 优先方式的搜索过程。
︙
︙
二 选择题（20 分，每小题 2 分）
︙
1．
对于给定的问题，考虑算法复杂性的意义在于（ ）。
︙
A. 设计出复杂性尽可能低的算法
︙
B. 若该问题已有多种算法时，选择其中复杂性低的求解问题
︙
︙
C. 提高算法设计的学术水平层次
︙
D. 判断算法的正确性
︙
2．
下列关于难处理问题的说法正确的是（ ）。
︙
︙
A. 能在多项式时间内求解的问题
︙
B. 不存在多项式时间内求解算法的问题
C. 至今还没有找到多项式时间算法求解的问题
D. 无论消耗多少计算机时间和空间也不能求解
3．
分枝限界法在解空间树 T 上的搜索方式是（ ）。
A．深度优先 B．广度优先
C．最小耗费优先 D．活结点优先
4．
一个使用函数自身给出定义的函数称为（ ）函数
A、自定义 B、递归 C、反身 D、可解
5.
下列不属于 NP 问题的是（ ）。
A. 0/1 背包问题 B. TSP 问题 C. 皇后问题 D. 排序问题
6．
有一段程序如下：
void GreedyKnapsack (float *x)
//前置条件：w[k]已按 p[k]/w[k]的非增次序排序
{
float u=m;
for(int j=0;j<n;j++) x[j]=0;
for( j=0;j<n;j++){
if(w[j]>u) break;
x[j]=1.0;
u=u-w[j];
}
if(j<n) x[j]=u/w[j];
}
请问下列关于这段程序的功能说法正确的是（ ）。
A. 采用贪心算法求解 0/1 背包问题
B. 采用贪心算法求解一般背包问题
C. 采用动态规划法求解一般背包问题
D. 采用分枝限界法求解 0/1 背包问题
7．
对于 0/1 背包问题，用（ ）不一定求得最优解。
A. 分枝限界法 B. 回溯法 C. 动态规划法 D. 贪心算法
8．
时间复杂性达到（ ）的算法称为最优算法。
A、次数 B、最大 C、下界 D、常数
9 、 n 皇 后 问 题 ， 若 显 式 约 束 描 述 为 :x
i
{0 ， 1…n-1} 且
x
i
x
j
(i j时) (0 i, j n 1)
则解空间的大小为:（ ）。
A.
n！
B.
n
n
C.
（n 1）！
D.
（n 1）
（n1）
10、用贪心法求解背包问题时，所选择的最优量度标准是（ ）
A．物品的重量 B. 物品的收益 C. 单位物品的收益 D. 背包容量
1
系
级
班
学
号
姓
名
资源评论
