第1页 / 共13页
第2页 / 共13页
第3页 / 共13页
第4页 / 共13页
第5页 / 共13页
第6页 / 共13页
第7页 / 共13页
第8页 / 共13页
算法期末试题南大.doc
《算法分析与设计》期末复习题
一、 选择题
1.应用 Johnson 法则的流水作业调度采用的算法是（D）
A. 贪心算法
B. 分支限界法
C.分治法
D. 动态规划算法
2.Hanoi 塔问题如下图所示。现要求将塔座 A 上的的所有圆盘移到塔座 B 上，并
仍按同样顺序叠置。移动圆盘时遵守 Hanoi 塔问题的移动规则。由此设计出解
Hanoi 塔问题的递归算法正确的为：（B）
A. void hanoi(int n, int A, int C, int B)
Hanoi 塔
{
if (n > 0)
{
hanoi(n-1,A,C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
B. void hanoi(int n, int A, int B, int C)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
C. void hanoi(int n, int C, int B, int A)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
D. void hanoi(int n, int C, int A, int B)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move(n,a,b);
hanoi(n-1, C, B, A);
}
3. 动态规划算法的基本要素为（C）
A. 最优子结构性质与贪心选择性质
B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质
D. 预排序与递归调用
4. 算法分析中，记号 O 表示（B）， 记号 表示（A）， 记号 表示（D）。
A.渐进下界
B.渐进上界
C.非紧上界
D.紧渐进界
E.非紧下界
5. 以下关于渐进记号的性质是正确的有：（A）
A. f (n)
(g(n)),g(n)
(h(n))
f (n)
(h(n))
B. f (n) O(g(n)),g(n) O(h(n))
h(n) O(f (n))
C. O(f(n))+O(g(n)) = O(min{f(n),g(n)})
D. f (n) O(g(n))
g(n) O(f (n))
6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）
A. 最优子结构性质与贪心选择性质
B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质
D. 预排序与递归调用
7. 回溯法在问题的解空间树中，按（D）策略，从根结点出发搜索解空间树。
A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先
8. 分支限界法在问题的解空间树中，按（A）策略，从根结点出发搜索解空间树。
A． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先
9. 程序块（A）是回溯法中遍历排列树的算法框架程序。
A.
B.
C.
D.
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t], x[i]);
if (legal(t)) backtrack(t+1);
swap(x[t], x[i]);
}
}
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (legal(t)) backtrack(t+1);
}
}
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=0;i<=1;i++) {
x[t]=i;
if (legal(t)) backtrack(t-1);
}
}
void backtrack (int t)
{
if (t>n) output(x);
else
for (int i=t;i<=n;i++) {
swap(x[t], x[i]);
10. 回溯法的效率不依赖于以下哪一个因素？（C ）
A.产生 x[k]的时间；
B.满足显约束的 x[k]值的个数；
C.问题的解空间的形式；
D.计算上界函数 bound 的时间；
E. 满足约束函数和上界函数约束的所有 x[k]的个数。
F. 计算约束函数 constraint 的时间；
11. 常见的两种分支限界法为（D）
A. 广度优先分支限界法与深度优先分支限界法；
B. 队列式（FIFO）分支限界法与堆栈式分支限界法；
C. 排列树法与子集树法；
D. 队列式（FIFO）分支限界法与优先队列式分支限界法；
12. k 带图灵机的空间复杂性 S(n)是指（B）
A.
B.
C.
D.
k 带图灵机处理所有长度为 n 的输入时，在某条带上所使用过的最大方格数。
k 带图灵机处理所有长度为 n 的输入时，在 k 条带上所使用过的方格数的总
和。
k 带图灵机处理所有长度为 n 的输入时，在 k 条带上所使用过的平均方格数。
k 带图灵机处理所有长度为 n 的输入时，在某条带上所使用过的最小方格数。
NP={L|L 是一个能在非多项式时间内被一台 NDTM 所接受的语言}；
NP={L|L 是一个能在多项式时间内被一台 NDTM 所接受的语言}；
13. NP 类语言在图灵机下的定义为（D）
A.
B.
C.
D.
NP={L|L 是一个能在多项式时间内被一台 DTM 所接受的语言}；
NP={L|L 是一个能在多项式时间内被一台 NDTM 所接受的语言}；
14. 记号 O 的定义正确的是（A）。
A.
O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有：0 f(n)
cg(n) }；
B.
O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有：0 cg(n)
f(n) }；
C.
O(g(n)) = { f(n) | 对于任何正常数 c>0，存在正数和 n0 >0 使得对所有 n n0
有：0 f(n)0，存在正数和 n0 >0 使得对所有
n n0 有：0 cg(n) < f(n) }；
15. 记号 的定义正确的是（B）。
A.
O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有：0 f(n)
cg(n) }；
B.
O(g(n)) = { f(n) | 存在正常数 c 和 n0 使得对所有 n n0 有：0 cg(n)
f(n) }；
C.
(g(n)) = { f(n) | 对于任何正常数 c>0，存在正数和 n0 >0 使得对所有 n n0
有：0 f(n)0，存在正数和 n0 >0 使得对所有 n n0
有：0 cg(n) < f(n) }；
二、 填空题
1. 下面程序段的所需要的计算时间为（
2O(n )
）。
int MaxSum(int n, int *a, int &besti, int &bestj)
{
int sum=0;
for(int i=1;i<=n;i++){
int thissum=0;
for(int j=i;j<=n;j++){
thissum+=a[j];
if(thissum>sum)
sum=thissum;
besti=i;
bestj=j;
{
}
}
return sum;
}
}
2. 有 11 个待安排的活动，它们具有下表所示的开始时间与结束时间，如果
以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活
动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活
动（ {1，4，8，11} ）。
i
S[i]
f[i]
1
1
4
2
3
5
3
0
6
4
5
7
5
3
8
6
5
9
7
6
10
8
8
11
9
8
12
10
2
13
11
12
14
3. 所谓贪心选择性质是指（所求问题的整体最优解可以通过一系列局部最
优的选择，即贪心选择来达到）。
4. 所谓最优子结构性质是指（问题的最优解包含了其子问题的最优解）。
5. 回溯法是指（具有限界函数的深度优先生成法）。
6. 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在
任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树
中从根结点到叶结点的最长路径的长度为 h(n)，则回溯法所需的计算空
间通常为（O(h(n))）。
7. 回溯法的算法框架按照问题的解空间一般分为（子集树）算法框架与（排
列树）算法框架。
8. 用回溯法解 0/1 背包问题时，该问题的解空间结构为（子集树）结构。
9.用回溯法解批处理作业调度问题时，该问题的解空间结构为（排列树）结
构。
10.用回溯法解 0/1 背包问题时，计算结点的上界的函数如下所示，请在空格
中填入合适的内容：
Typep Knap::Bound(int i)
{// 计算上界
Typew cleft = c - cw;
Typep b = cp;
// 以物品单位重量价值递减序装入物品
while (i <= n && w[i] <= cleft) {
// 剩余容量
// 结点的上界
cleft -= w[i];
b += p[i];
i++;
}
// 装满背包
if (i <= n) （b += p[i]/w[i] * cleft）;
return b;
}
11. 用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为
n m 的方格阵列，扩展每个结点需 O(1)的时间，L 为最短布线路径的长度，则
算法共耗时 (
O(mn)
)，构造相应的最短距离需要（O(L)）时间。
for (int i = 0; i < NumOfNbrs; i++) {
nbr.row = here.row + offset[i].row;
nbr.col = here.col + offset[i].col;
if (grid[nbr.row][nbr.col] == 0) {
// 该方格未标记
grid[nbr.row][nbr.col]
= grid[here.row][here.col] + 1;
if ((nbr.row == finish.row) &&
(nbr.col == finish.col)) break; // 完成布线
Q.Add(nbr);}
}
12. 用回溯法解图的 m 着色问题时，使用下面的函数 OK 检查当前扩展结点的每
一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn））。
Bool Color::OK(int k)
{//
for(int j=1;j<=n;j++)
if((a[k][j]= =1)&&(x[j]= =x[k])) return false;
return true;
}
13. 旅行售货员问题的解空间树是（排列树）。
三、 证明题
1. 一个分治法将规模为 n 的问题分成 k 个规模为 n／m 的子问题去解。设分
解阀值 n0=1，且 adhoc 解规模为 1 的问题耗费 1 个单位时间。再设将原问题
分解为 k 个子问题以及用 merge 将 k 个子问题的解合并为原问题的解需用 f(n)
个单位时间。用 T(n)表示该分治法解规模为|P|=n 的问题所需的计算时间，
则有：
( )
T n
O
/
(1)
)
( )
kT n m f n
(
n
n
1
1
通过迭代法求得 T（n）的显式表达式为：
( )
T n
n
log
k
m
试证明 T（n）的显式表达式的正确性。
1
j
k f n m
(
/
j
)
log
nm
j
0
2. 举反例证明 0/1 背包问题若使用的算法是按照 pi/wi 的非递减次序考虑选择的
物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优
解（此题说明 0/1 背包问题与背包问题的不同）。
证明：举例如：p={7,4,4},w={3,2,2},c=4 时，由于 7/3 最大，若按题目要求的方
法，只能取第一个，收益是 7。而此实例的最大的收益应该是 8，取第 2，3 个。
3. 求证：O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 。
证明：对于任意 f1(n) O(f(n)) ，存在正常数 c1 和自然数 n1，使得对所有 n n1，
有 f1(n) c1f(n) 。
类似地，对于任意 g1(n) O(g(n)) ，存在正常数 c2 和自然数 n2，使得对
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
