参考教材：算法设计与分析（Python版） 作者：王秋芬
1 . 普通 （5分）以下算法框架中，哪个是排列树模型的算法设计模式（）
A. def Backtrack (t):
if (t>n):
output(x) else:
for i in range(1,m+1):
if (constraint(t) and bound(t)):
x[t]=i
做其他相关标识
Backtrack(t+1)
做其他相关标识的反操作
B. def Backtrack (t):
if (t>n):
output(x) else:
for i in range(t,n+1):
x[t], x[i]←x[i], x[t]
if (constraint(t) and bound(t)):
Backtrack(t+1)
x[t], x[i]←x[i], x[t]
C. def Backtrack (int t):
if (t>=n):
output(x) else:
for i in range(s(n,t),e(n,t)):
x[t]=d(i)
if (constraint(t) and bound(t)):
Backtrack(t+1)
D. def Backtrack (int t):
if (t>n):
output(x)
if(constraint(t)):
做相关标识
Backtrack(t+1)
做相关标识的反操作
if(bound(t)):
做相关标识
Backtrack(t+1)
做相关标识的反操作
2 . 普通 （5分）最优化问题优化目标是使求目标函数最大化，基于回溯法求解该问题。如果对于解空间的任何分支X，均可求出目标函数值的两个上界lb1(X)和lb2(X)，且总有lb1（X）>=lb2(X),则如果想用于剪枝，从减少搜索节点的角度，哪个界限更优？
A. lb1
B. lb2
C. 二者等价
D. 依赖于具体输入
3 . 容易 （5分）0-1背包问题的解空间结构属于（）
A. 排列树
B. 子集树
C. 满n叉树
D. 隐式图
4 . 容易 （5分）以下关于回溯法的说法，错误的是
A. 回溯法一般会将解空间组织成树形结构并按照深度优先的顺序遍历
B. 回溯法可以适用于求所有解、某个解、最优解等各种问题
C. 回溯法能够保证生成时间复杂度较低的算法
D. 回溯法的编程中，有“当前搜索路径”的概念，需要保存当前路径上节点的状态
5 . 普通 （5分）现有一个用于求解最优化问题的回溯算法，在搜索过程中涉及的函数的描述，错误的是
A. 违反约束函数的分支不属于问题的定义域
B. 违反限界函数的分支不需要访问，不能够得到更优解
C. 目标函数是衡量解的优劣程度的函数
D. 在目标函数最小化问题中，限界函数应当使用上界
6 . 普通 （5分）关于旅行商问题的说法，错误的是
A. 旅行商问题的解空间与最短路径问题相同
B. 旅行商问题的优化目标是回路长度最短
C. 有4个点的旅行商问题的两个回路，ABCDA和BCDAB，实际上是两个相同的回路
D. 旅行商问题无法用穷举求解，因为回路数目太多
7 . 普通 （5分）以下有关旅行商问题的递归代码，根据注释判断空缺部分填写正确的是（）。
def Traveling(t):
( )#到达叶子结点
#g存储图的邻接矩阵，x是存储解向量，初始化为x[1:n]={1,2,...,n},cl是当前已走的路经长度，bestl是当前已找到的最短路径长度。
if(g[x[n] ][1] !=∞ and (cl+g[x[n]][1]< bestl ) ):
for j in range(1,n+1):
bestx[j]=x[j]
bestl=cl+g[x[n]][1] else:#没有到达叶子结点
( ) #控制当前节点的分支数目，即对xt的所有可能的取值。
if( g[x[t-1]][x[j]] !=∞ and(cl+g[x[t-1]][x[j]]< bestl) ):
#保存第t个要去的城市编号到x[t]中，进入到第t+1层
x[t],x[j]=x[j],x[t] #交换两个元素的值
cl+=g[x[t-1]][x[j]]
Traveling(t+1)#从第t+1层的扩展结点继续搜索 #第t+1层搜索完毕，回溯到第t层 cl-=g[x[t-1]][x[j]]
x[t],x[j]=x[j],x[t]
A. 空1：if(t==n) 空2：for(j=t;j<=n;j++)
B. 空1：if(t>n-1) 空2：for(j=1;j<=n;j++)
C. 空1：if(t>n) 空2：for(j=t;j<=n;j++)
D. 空1：if(t>=n-1) 空2：for(j=1;j<=n;j++)
8 . 容易 （5分）有关回溯法说法正确的是（）
A. 回溯法是一种深度优先搜索的搜索算法
B. 回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C. 回溯法是一种宽（广）度优先搜索的搜索算法
D. 回溯法是一种最大效益或最小费用优先搜索的方法
9 . 普通 （5分）有关n皇后问题说法正确的是（）
A. 该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B. 该问题的初始状态为：(0,0,...,0)
C. 该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D. 该问题只需要设置约束条件，不需要限界条件。 E、 该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
10 . 容易 （5分）下述有关搜索过程描述错误的是（）
A. 当解空间结构是一棵树时，搜索从根开始
B. 搜索过程中，正在生成孩子的节点称为扩展节点
C. 搜索过程中，所有孩子节点均已生成的节点称为扩展节点
D. 搜索过程中，所有孩子节点均已生成的节点称为活结点节点 E、 搜索过程中，所有孩子节点均已生成的节点称为死节点 F、 搜索过程动态生成的树称为搜索树
11 . 普通 （5分）以下描述中，影响回溯法的搜索效率的是（）
A. 问题的解空间，即搜索范围
B. 设定的约束函数和限界函数
C. 搜索方法
D. 满足约束条件和限界条件的节点数目
12 . 普通 （5分）以下有关子集树的描述中说法正确的是（）
A. 当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时，相应的解空间树称为子集树。
B. 子集树模型解的形式为n元组（x1,x2,…,xn），分量xi(i=1,2,…,n)表示第i个元素是否在子集中。
C. 子集树模型的解向量中，分量xi的取值为0或1，xi=0表示第i个元素不在子集中；xi=1表示第i个元素在子集中。
D. 旅行售货员问题可以开用子集树模型求解 E、 最优装载问题可以采用子集树模型求解 F、 0-1背包问题可以采用子集树模型求解
13 . 容易 （5分）有关子集树描述中，说法错误的是（）
A. 子集树的根结点为问题的初始状态
B. 子集树的中间结点为搜索过程中形成的某中间状态
C. 子集树的叶子结点为问题结束状态
D. 子集树的分支表示从一个状态过渡到另一个状态的行为 E、 子集树中从根结点到叶子结点的路径是一个可行解（一个子集） F、 子集树的深度等于问题的规模加1
14 . 普通 （5分）有关0-1背包问题说法正确的是（）
A. 该问题的解的形式为(x1, x2, … , xn)，xi(i=1,2,3,...n)的取值为0或1
B. 该问题的解空间的组织结构可以是排列树。
C. 该问题需要设置约束条件，也可以设置限界条件。
D. 该问题只需要设置约束条件，不需要限界条件。
15 . 普通 （5分）有关下图说法正确的是（）
A. 该树表示的问题的规模为3
B. 该树为一棵排列树
C. 该树表示的问题规模为4。
D. 该树为一棵子集树
16 . 普通 （5分）有关批处理作业调度问题说法正确的是（）
A. 该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}，i=1,2,...,n
B. 该问题的解空间的组织结构是排列树。
C. 该问题需要设置约束条件，不需要限界条件。
D. 该问题不需要设置约束条件，只需要限界条件。 E、 该问题既需要设置约束条件，也需要限界条件。
17 . 普通 （5分）有关旅行售货员问题说法正确的是（）
A. 该问题的解形式为(x1,x2,…,xn)，xi取值范围为：令S={1,2,…,n}，则xi∈S-{x1,x2,…,xi-1}
B. 该问题的解空间的组织结构是排列树。
C. 该问题需要设置约束条件，不需要限界条件。
D. 该问题不需要设置约束条件，只需要限界条件。 E、 该问题既需要设置约束条件，也可以设置限界条件。
18 . 容易 （5分）有关回溯法说法正确的是（）
A. 回溯法是一种深度优先搜索的搜索算法
B. 回溯法是一种“能进则进、进不了则换、换不了则退（回溯）”的搜索方法
C. 回溯法是一种宽（广）度优先搜索的搜索算法
D. 回溯法是一种最大效益或最小费用优先搜索的方法
19 . 普通 （5分）有关n皇后问题说法正确的是（）
A. 该问题的解的形式为(x1, x2, … , xn)，xi表示第i个皇后位于第i行、第xi列(i=1,2,3,...n)
B. 该问题的初始状态为：(0,0,...,0)
C. 该问题的解空间的组织结构可以是排列树，也可以是满n叉树。
D. 该问题只需要设置约束条件，不需要限界条件。
E. 该问题解向量中的任意两个分量xi,xj满足：xi≠xj且|i-j|≠|xi-xj|
20 . 普通 （5分）以下描述中，影响回溯法的搜索效率的是（）
A. 问题的解空间，即搜索范围
B. 设定的约束函数和限界函数
C. 搜索方法
D. 满足约束条件和限界条件的节点数目