5.1单项选择题及其参考答案
5.1.1单项选择题
1. 回溯法是在问题的解空间中按策略从根结点出发搜索的。
A. 广度优先B. 活结点优先
C. 扩展结点优先D. 深度优先
2. 下列算法中通常以深度优先方式搜索问题的解。
A. 回溯法B. 动态规划C. 贪心法D. 分支限界法
3. 关于回溯法,以下叙述中不正确的是。
A. 回溯法有通用解题法之称,可以系统地搜索一个问题的所有解或任意解
B. 回溯法是一种既带系统性又带有跳跃性的搜索算法
C. 回溯算法需要借助队列来保存从根结点到当前扩展结点的路径
D. 回溯算法在生成解空间的任一结点时,先判断该结点是否可能包含问题的解,如
果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向祖先结点回溯
4. 回溯法的效率不依赖于下列因素。
A. 确定解空间的时间B. 满足显式约束的值的个数
C. 计算约束函数的时间D. 计算限界函数的时间
5. 下面是回溯法中为避免无效搜索采取的策略。
A. 递归函数B. 剪枝函数C. 随机数函数D. 搜索函数
6.对于含有n个元素的子集树问题(每个元素二选一), 最坏情况下解空间树的叶子结
点个数是。
A.n! B.2nC.2n+1-1 D.2n-1 
7. 用回溯法求解0/1背包问题时的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
8. 用回溯法求解0/1背包问题时的最坏时间复杂度是。
A.O(n) B.O(nlog2n) C.O(n×2n) D.O(n2)
9. 用回溯法求解TSP 问题时的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
10. 有
n 
个学生,每个人有一个分数,求最高分的学生的姓名,最简单的方法
是。
A. 回溯法B. 归纳法C. 迭代法D. 以上都不对
11. 求中国象棋中马从一个位置到另外一个位置的所有走法,采用回溯法求解时对应
的解空间是。
A. 子集树B. 排列树
106 


C. 深度优先生成树D. 广度优先生成树
12.n个人排队在一台机器上做某个任务,每个人的等待时间不同,完成他的任务的时
间不同,求完成这n个任务的最小时间,采用回溯法求解时对应的解空间是。
A. 子集树B. 排列树
C. 深度优先生成树D. 广度优先生成树
5.1.2单项选择题参考答案
1. 答:回溯法采用深度优先搜索在解空间中搜索问题的解。答案为D。
2. 答:回溯法采用深度优先搜索在解空间中搜索问题的解,分支限界法采用广度优先
搜索在解空间中搜索问题的解。答案为A。
3. 答:回溯算法是采用深度优先遍历的,需要借助栈保存从根结点到当前扩展结点的
路径。答案为C。
4. 答:回溯法的解空间是虚拟的,不必事先确定整个解空间。答案为A。
5. 答:剪支函数包括约束函数(在扩展结点处剪去不满足约束条件的路径)和限界函数
(剪去得不到问题的解或最优解的路径) 。答案为B。
6. 答:这样的解空间树是一棵高度为n+1 的满二叉树,叶子结点恰好有2n个。答案
为B。
7. 答:在0/1背包问题中每个物品是二选一(要么选中,要么不选中), 与物品的顺序无
关,对应的解空间为子集树类型。答案为A。
8. 答:0/1背包问题的解空间是一棵高度为n+1 的满二叉树,结点个数为2n+1-1,最
坏情况下搜索全部结点。答案为C。
9. 答:TSP 问题的解空间属于典型的排列树,因为路径与顶点的顺序有关。答案为B。
10. 答:最简单的方法是依次迭代比较求最高分数。答案为C。
11. 答:每一步马从相邻可走的位置中选择一个位置走下去。答案为A。
12. 答:该问题是求1~n的某个排列,对应n个任务完成的最小时间。答案为B。
5.2问答题及其参考答案
5.2.1问答题
1. 回溯法的搜索特点是什么? 
2.有这样一个数学问题,x和y是两个正实数,求x+y=3的所有解,请问能否采用回
溯法求解? 如果
x 
和
y 
是两个均小于或等于10 的正整数,又能否采用回溯法求解? 如果
能够,请采用解空间画出求解结果。

对于n=4,7),31 的子集和问题,利用左、右剪支的回溯法算法求
解,求出所有解并且画出解空间中的搜索过程。

3.a=(11,13,24,t=
4.对于
n 
皇后问题,通过解空间说明n=3时是无解的。
5.对于
n 
皇后问题,有人认为当
n 
为偶数时其解具有对称性,即
n 
皇后问题的解个数
107 


108 
恰好为n/2皇后问题的解个数的两倍,这个结论正确吗? 
6.请问能否采用解空间为排列树的回溯框架求解n 皇后问题? 如果能,请给出剪支操
图5.1 一个无向连通图
作,说明最坏情况下的时间复杂度,按照最坏情况下的时间复杂
度比较,哪个算法更好? 
7.对于如图5.1所示的无向连通图,假设颜色数m =2,给
出m 着色的所有着色方案,并且画出对应的解空间。
8.有一个0/1背包问题,物品个数n=4,物品编号分别为
0~3,它们的重量分别是3、1、2和2,价值分别是9、2、8和6,背
包容量W =3。利用左、右剪支的回溯法算法求解,并且画出解
空间中的搜索过程。
9.以下算法用于求n 个不同元素a 的全排列,当a=(1,2,3)时,请给出算法输出的全
排列的顺序。 
int cnt=0; //累计排列的个数
void disp(int a[]){ //输出一个解 
System.out.printf(" 排列%2d: (",++cnt); 
for(int i=0;i<a.length-1;i++) 
System.out.printf("%d,",a[i]); 
System.out.printf("%d)",a[a.length-1]); 
System.out.println(); 
}v
oid swap(int a[],int i,int j) { / /交 换 a[i]与a[j] 
int tmp=a[i]; 
a[i]=a[j]; a[j]=tmp; 
}v
oid dfs(int a[],int i) { //递归算法 
int n=a.length; 
if(i>=n-1) //递归出口 
disp(a); 
else { 
for(int j=n-1;j>=i;j--) { 
swap(a,i,j); //交换a[i]与a[j] 
dfs(a,i+1); 
swap(a,i,j); //交换a[i]与a[j]:恢复 
} 
} 
}v
oid perm(int a[]) { //求a 的全排列 
dfs(a,0); 
} 
10.假设问题的解空间为(x0,x1,…,xn-1),每个xi 有m 种不同的取值,所有xi 取不
同的值,该问题既可以采用子集树递归回溯框架求解,也可以采用排列树递归回溯框架求
解,考虑最坏时间性能应该选择哪种方法? 
11.以下两个算法都是采用排列树递归回溯框架求解任务分配问题,判断其正确性,如
果不正确,请指出其中的错误(其中,swap(x,i,j)用于交换x[i]和x[j])。

109 
(1)算法1: 
void dfs(int x[],int cost,int i) { //回溯算法 
if(i>n) { //到达叶子结点 
if(cost<bestc) { //比较求最优解 
bestc=cost; 
bestx=x; 
} 
} 
else { //没有到达叶子结点 
for(int j=1;j<=n;j++) { //为人员i 试探任务x[j] 
if(task[x[j]]) continue; //若任务x[j]已经分配,则跳过 
task[x[j]]=true; 
cost+=c[i][x[j]]; 
swap(x,i,j); //为人员i 分配任务x[j] 
if(bound(x,cost,i)<bestc) / /剪 支 
dfs(x,cost,i+1); //继续为人员i+1 分配任务 
swap(x,i,j); 
cost-=c[i][x[j]]; //cost 回溯 
task[x[j]]=false; //task 回溯 
} 
} 
}
(2)算法2: 
void dfs(int x[],int cost,int i) { //回溯算法 
if(i>n) { //到达叶子结点 
if(cost<bestc) { //比较求最优解 
bestc=cost; 
bestx=x; 
} 
} 
else { //没有到达叶子结点 
for(int j=1;j<=n;j++) { //为人员i 试探任务x[j] 
if(task[x[j]]) continue; //若任务x[j]已经分配,则跳过 
swap(x,i,j); //为人员i 分配任务x[j] 
task[x[j]]=true; 
cost+=c[i][x[j]]; 
if(bound(x,cost,i)<bestc) / /剪 支 
dfs(x,cost,i+1); //继续为人员i+1 分配任务 
cost-=c[i][x[j]]; //cost 回溯 
task[x[j]]=false; //task 回溯 
swap(x,i,j); 
} 
} 
} 
5.2.2 问答题参考答案
1.答:回溯法的搜索特点是深度优先搜索+剪支。深度优先搜索可以尽快地找到一个
解,剪支函数可以终止一些路径的搜索,提高搜索性能。

110 
图5.2 求x+y=3的解空间
2.答:当x 和y 是两个正实数时,理论上讲两个实数之间
有无穷个实数,所以无法枚举x 和y 的取值,不能采用回溯法求
x+y=3的所有解。
当x 和y 是两个均小于或等于10的正整数时,它们的枚举
范围是有限的,可以采用回溯法求x+y=3的所有解,采用剪支
仅扩展x,y∈[1,2]的结点。解向量是(x,y),对应的解空间如
图5.2所示,找到的两个解是(1,2)和(2,1)。
3.答:利用左、右剪支的回溯法算法求出两个解如下。 
第1 个解: 选取的数为11 13 7 
第2 个解: 选取的数为24 7 
在解空间中的搜索过程如图5.3所示,图中每个结点为(cs,rs),其中cs为考虑第i 个
整数时选取的整数和,rs为剩余整数和。题中实例搜索的结点个数是11,如果不剪支,需要
搜索31个结点。
图5.3 子集和问题的搜索过程
4.答:n=3时的解向量为(x1,x2,x3),xi 表示第i 个皇后的列号,对应的解空间如
图5.4所示,所有的叶子结点均不满足约束条件,所以无解。
图5.4 3皇后问题的解空间

5.答:这个结论是错误的,因为两个n/2皇后问题的解合并起来不是n皇后问题的解。
6.答:设n皇后问题的解向量为(x1,x2,…,xn),xi表示第i个皇后的列号,显然每个
解一定是1~n的某个排列,所以可以采用解空间为排列树的回溯框架求解n皇后问题。
其剪支操作是任何两个皇后不能同行、同列和同两条对角线。在最坏情况下该算法的时间
复杂度为O(n×n!), 由于O(n×n!) 好于O(n×nn), 所以按照最坏情况下的时间复杂度比
较,解空间为排列树的回溯算法好于解空间为子集树的回溯算法。
7.答:这里n=4,顶点编号为0~3,m=2,颜色编号为0和1,解向量为(x0,x1,x2,x3), 
xi表示顶点i的着色,对应的解空间如图5.5所示,着色方案有两种,分别是(0,1,1,1) 
和(1,0,0,0) 。
图5.5 m着色问题的解空间
8.答:求解过程如下。
①4 个物品按v/w递减排序后的结果如表5.1所示。
②从i=0开始搜索对应的解空间如图5.6所示。
表5.14个物品按v/w递减排序后的结果
序号i物品编号no重量w价值vv/w0 2 2 8 4 
1 0 3 9 3 
2 3 2 6 3 
3 1 1 2 2 
图5.

60/1背包问题的解空间
最后得到的最优解是选择编号为1和2的物品,总重量为3,总价值是10 。

9. 答:当a=(1,2,3)时,调用pa)的输出结果及其顺序如下。
erm(

111

112 
排列1: (3,1,2) 
排列2: (3,2,1) 
排列3: (2,3,1) 
排列4: (2,1,3) 
排列5: (1,3,2) 
排列6: (1,2,3) 
10.答:一般情况下,这样的问题采用子集树递归回溯框架求解时最坏时间复杂度为
O(mn),采用排列树递归回溯框架求解时最坏时间复杂度为O (n!),如果m =2,由于
O(2n)<O(n!),采用前者较好;如果m 接近n,由于O(nn)>O(n!),采用后者较好。
11.答:算法1是正确的。算法2不正确,在执行第一个swap(x[i],x[j])后已经为人
员i 分配了任务x[j],应该置task[x[i]]=true,cost+=c[i][x[i]],后面的回溯恢复过
程也是如此。
5.3 算法设计题及其参考答案
5.3.1 算法设计题
1.给定含n 个整数的序列a(其中可能包含负整数),设计一个算法从中选出若干整数, 
使它们的和恰好为t。例如,a=(-1,2,4,3,1),t=5,求解结果是(2,3,1,-1)、(2,3)、
(2,4,-1)和(4,1)。
2.给定含n 个正整数的序列a,设计一个算法从中选出若干整数,使它们的和恰好为t 
并且所选元素个数最少的一个解。
3.给定一个含n 个不同整数的数组a,设计一个算法求其中m (m ≤n)个元素的组合。
例如,a={1,2,3},m =2,输出结果是{{1,2},{1,3},{2,3}}。
4.设计一个算法求1~n 中m (m ≤n)个元素的排列,要求每个元素最多只能取一次。
例如,n=3,m =2时的输出结果是{{1,2},{1,3},{2,1},{2,3},{3,1},{3,2}}。
5.在求n 皇后问题的算法中每次放置第i 个皇后时,其列号xi 的试探范围是1~n,实
际上前面已经放好的皇后的列号是不必试探的,请根据这个信息设计一个更高效的求解n 
皇后问题的算法。
6.请采用基于排列树的回溯框架设计求解n 皇后问题的算法。
7.一棵整数二叉树采用二叉链b 存储,设计一个算法求根结点到每个叶子结点的路径。
8.一棵整数二叉树采用二叉链b 存储,设计一个算法求根结点到叶子结点的路径中路
径和最小的一条路径,如果这样的路径有多条,求其中的任意一条。
9.一棵整数二叉树采用二叉链b 存储,设计一个算法产生每个叶子结点的编码。假设
从根结点到某个叶子结点a 有一条路径,从根结点开始,路径走左分支时用0表示,走右分
支时用1表示,这样的0/1序列就是a 的编码。
10.假设一个含n 个顶点(顶点编号为0~(n-1))的不带权图采用邻接矩阵A 存储, 
设计一个算法判断其中顶点u 到顶点v 是否有路径。

113 
11.假设一个含n 个顶点(顶点编号为0~(n-1))的不带权图采用邻接矩阵A 存储, 
设计一个算法求其中顶点u 到顶点v 的所有路径。
12.假设一个含n 个顶点(顶点编号为0~(n-1))的带权图采用邻接矩阵A 存储,设
计一个算法求其中顶点u 到顶点v 的一条路径长度最短的路径。一条路径的长度是指路
径上经过的边的权值和。如果这样的路径有多条,求其中的任意一条。
13.给定一个m ×n 的迷宫,每个方格值为0时表示空白,为1时表示障碍物,在行走时
最多只能走到上、下、左、右相邻的方格。设计一个回溯算法求从指定入口s 到指定出口t 
的所有迷宫路径和其中一条最短路径。
14.给定一个不带权连通图,由指定的起点前往指定的终点,途经所有其他顶点且只经
过一次,称为哈密顿路径,闭合的哈密顿路径称作哈密顿回路。设计一个算法求无向图的所
有哈密顿回路。
15.采用回溯法求解最优调度问题,假设有n 个任务由k 个可并行工作的机器来完成,完
成任务i(0≤i<n)需要的时间为ti,设计一个算法求完成这n 个任务的最少时间。例如, 
n=10,t={67,45,80,32,59,95,37,46,28,20},k=7,完成这10个任务的最少时间是95。
5.3.2 算法设计题参考答案
1.解:由于a 中可能包含负整数,甚至t 有可能是负数,无法剪支,采用求a 的幂集的
思路,相当于求出a 的所有子集并且累计子集和cs,当到达一个叶子结点时,若满足cs=t 
就是一个解。对应的算法如下: 
int a[]; 
int n; 
int t; 
int x[]; //解向量
int sum; //累计组合个数
void dfs(int cs,int i) { / /回 溯 算 法 
if(i>=n){ //到达一个叶子结点 
if(cs==t){ //找到一个解 
System.out.printf(" (%d): ",++sum); 
for(int j=0;j<n;j++) { 
if(x[j]==1) 
System.out.printf("%d ",a[j]); 
} 
System.out.println(); 
} 
} 
else { //没有到达叶子结点 
x[i]=1; cs+=a[i]; 
dfs(cs,i+1); //选择a[i] 
cs-=a[i]; //回溯cs 
x[i]=0; 
dfs(cs,i+1); //不选择a[i] 
} 
}

114 
void subs4(int a[],int t) { //求解子集和问题 
this.a=a; 
this.t=t; 
n=a.length; 
x=new int[n]; //指定x 的长度为n 
sum=0; 
dfs(0,0); 
}
说明:有人说一旦找到了cs=t 就输出一个解(看成不再选择后面的元素),所以将输出
解的条件改为满足i<n &&cs=t。这样是错误的,因为这样做的结果是输出一个解后就
停止了该结点的扩展,后面的解就找不到了,例如(2,3)是一个解,这样修改就找不到(2,3, 
1,-1)这个解了。
2.解:属于典型的解空间为子集树的问题,采用子集树的回溯算法框架求解。当找到
一个解后通过对选取的元素个数进行比较求最优解bestx和bestm,剪支原理见《教程》中
5.3.5节的求解子集和问题的算法。对应的算法如下: 
int a[]; 
int n; 
int t; 
int bestx[]; //最优解向量
int bestm; //选择的最少元素个数
void dfs(int cs,int rs,int x[],int m,int i) { / /回 溯 算 法 
if(i>=n){ //到达一个叶子结点 
if(cs==t){ //找到一个解 
if(m<bestm){ //找更优解 
bestm=m; 
bestx=Arrays.copyOf(x,n); 
} 
} 
} 
else { //没有到达叶子结点 
rs-=a[i]; //求剩余的整数和 
if(cs+a[i]<=t) { //左孩子结点剪支 
x[i]=1; //选取整数a[i] 
dfs(cs+a[i],rs,x,m+1,i+1); 
} 
if(cs+rs>=t){ //右孩子结点剪支 
x[i]=0; //不选取整数a[i] 
dfs(cs,rs,x,m,i+1); 
} 
rs+=a[i]; //恢复剩余整数和 
} 
}v
oid subs(int a[],int t) { //求解子集和问题 
this.a=a; 
n=a.length; 
this.t=t; 
int x[]=new int[n]; //解向量 
int rs=0; //表示所有整数和