3.单项选择题及其参考答案
1 

3.1.1 
单项选择题
1. 穷举法的适用范围是。
A. 一切问
题 
B. 解的个数极多的问题
C. 解的个数有限且可一一列举D. 不适合设计算法
2. 如果一个4位数恰好等于它的各位数字的4次方和,则这个4位数称为玫瑰花数。
例如1634=14+64+34+44,则1634 是一个玫瑰花数。若想求出4位数中所有的玫瑰花
数,可以采用的解决方法是。
A. 递归法B. 穷举法C. 归纳法D. 都不适合
3.有一个数列,递推关系是a1=1 aan 
则求出的通项公式是。2,n+1= an 
+1, 
1 1 
1 n

A.an 
= n+1 B.an 
= C.an 
=2n 
D.an 
=2 

4. 猜想1=1,1-4=-(1+2)-4+9=1+2+3,…的第5个式子是。,1(n) 
A.12+22-32-42+52=1+2+3+4+
5
2-2

B.12+232+452=-(1+2+3+4+5)

C.12-22+32-42+52=-(1+2+3+4+5)

D.12-22+32-42+52=1+2+3+4+5 

5. 对于迭代法,下面的说法不正确的是。
A. 需要确定迭代模型
B. 需要建立迭代关系式
C. 需要对迭代过程进行控制,要考虑什么时候结束迭代过程
D. 不需要对迭代过程进行控制
6. 设计递归算法的关键是。
A. 划分子问
题 
B. 提取递归模型
C. 合并子问
题 
D. 求解递归出口
7. 若一个问题的求解既可以用递归算法,也可以用迭代算法,则往往用① 算法,因
为 
② 。
①A. 先递归后迭代B. 先迭代后递归

C. 递归D. 迭
代
②A. 迭代的效率比递归高B. 递归宜于问题分
解
C. 递归的效率比迭代高D. 迭代宜于问题分解
8. 一般来说,递归需要有递归出口和递归体,求解过程分为分解和求值,当到达递归出
口时。
A. 进行运算B. 返回求值C. 继续分解D. 结束求解
38

39 
9.递归函数f(n)=f(n-1)+n(n>1)的递归出口是。
A.f(-1)=0 B.f(1)=1 C.f(0)=1 D.f(n)=n 
10.递归函数f(n)=f(n-1)+n(n>1)的递归体是。
A.f(1)=0 B.f(1)=1 
C.f(n)=n D.f(n)=f(n-1)+n 
11.有以下递归算法,f(123)的输出结果是。 
void fun(int n) { 
if(n>0) { 
System.out.printf("%d",n%10); 
f(n/10); 
} 
} 
A.321 B.123 C.6 D.以上都不对
12.有以下递归算法,f(123)的输出结果是。 
void fun(int n) { 
if(n>0){ 
f(n/10); 
System.out.printf("%d",n%10); 
} 
} 
A.321 B.123 C.6 D.以上都不对
13.整数单链表h 是不带头结点的,结点类型ListNode为(val,next),则以下递归算法
中隐含的递归出口是。 
void fun(ListNode h) { 
if(h!=null) { 
System.out.printf("%d",h->val); 
f(h.next); 
} 
} 
A.if(h!=null)return; B.if(h==null)return0; 
C.if(h==null)return; D.没有递归出口
14.T(n)表示输入规模为n 时算法的效率,以下算法中性能最优的是。
A.T(n)=T(n-1)+1,T(1)=1 B.T(n)=2n2 
C.T(n)=T(n/2)+1,T(1)=1 D.T(n)=3nlog2n 
3.1.2 单项选择题参考答案
1.答:穷举法作为一种基本算法设计方法并非是万能的,主要适合于解个数有限且可
一一列举的问题的求解。答案为C。

2.答 :4位数的范围是1000~9999,可以一一枚举。答案为B。
答:采用不完全归纳法,2,3,4,5,…,n+1,可以采用数

3.a1=1 a2=1 a3=1 a4=1 an 
=1 
学归纳法证明其正确性。答案为A。

4. 答:推导如下
。
n=1,12=
1
n=2,1-4=1-22=-(1+2)
n=3,1-4+9=12-22+32=1+2+
3
n=3,12-22+32-42=-(1+2+3+4)
n=3,12-22+32-42+52=1+2+3+4+
5
答案为D。

5. 答:迭代法先确定迭代变量,再对迭代过程进行控制。答案为D。
6. 答:递归模型是递归算法的核心,反映递归算法的本质。答案为B。
7. 答:一般情况下求解同一个问题的迭代算法比递归算法的效率高。答案是①D 
②A 。
8. 答:当到达递归出口时得到该子问题的解,然后返回求值。答案为B。
9. 答:f(
f(1)+nn(
>1)是递归体,递归出口对应n=1的情况。答案为B。
n)=f(n-1)+n(

10. 答:f(n)=n-n>1)本身就是递归体。答案为D。
11. 答:该算法属于先合后递的递归算法。在执行f(123)时先输出123%10=3,再调
用f(12)输出2,最后调用f(1)输出1。答案为A。
12. 答:该算法属于先递后合的递归算法。执行过程是f(123)→f(12)→f(1), 返回
时依次输出1,2和3。答案为B。
13. 答:任何递归算法都包含递归出口,该递归算法是正向输出单链表
h 
中的结点值, 
递归出口是
h 
为空的情况。答案为C。
答:对于选项A,采用直接展开法求出T(=)。对于选项B,T(n2)。

14.n)Θ(n)=Θ(
对于选项C,采用主方法,2,n)1),logba 
n) 则T(
1,f(O(与f(的阶相同, n)

a=b==n=1(n) = 
Θ(og)。对于选项D,n)Θ(lg2n)。答案为C。

l2nT(=no

3.问答题及其参考答案
2 

3.2.1 
问答题
1. 用穷举法解题时的常用列举方法有顺序列举、排列列举和组合列举,问求解以下问
题应该采用哪一种列举方法? 
(1)求m~
n 
的所有素数。
(2)在数组
a 
中选择出若干元素,它们的和恰好等于k。
(3)有
n 
个人合起来做一个任务,他们的排列顺序不同完成该任务的时间不同,求最优
完成时间。
40

41 
2.许多系统用户登录时需要输入密码,为什么还需要输入已知的验证码? 
3.什么是递归算法? 递归模型由哪两个部分组成? 
4.比较迭代算法与递归算法的异同。
5.有一个含n(n>1)个整数的数组a,写出求其中最小元素的递归定义。
6.有一个含n(n>1)个整数的数组a,写出求所有元素和的递归定义。
7.利用整数的后继函数succ写出x+y(x 和y 都是正整数)的递归定义。
8.有以下递归算法,则f(f(7))的结果是多少? 
int f(int n) { 
if(n<=3) 
return 1; 
else 
return f(n-2)+f(n-4)+1; 
} 
9.有以下递归算法,则f(3,5)的结果是多少? 
int f(int x,int y) { 
if(x<=0 || y<=0) 
return 1; 
else 
return 3*f(x-1,y/2); 
} 
10.采用直接展开法求以下递推式: 
T(1)=1 
T(n)=T(n -1)+n 当n >1时 
11.采用递归树方法求解以下递推式: 
T(1)=1 
T(n)=4T(n/2)+n 当n >1时 
12.采用主方法求解以下递推式: 
(1)T(n)=4T(n/2)+n 
(2)T(n)=4T(n/2)+n2 
(3)T(n)=4T(n/2)+n3 
13.有以下算法,分析其时间复杂度。 
void f(int n) { 
for(int i=1;i<=n;i++){ 
for(int j=1;j<=i;j++) 
System.out.printf("%d %d %d\n",i,j,n); 
} 
if(n>0){ 
for(int i=1;i<=4;i++) 
f(n/2); 
} 
}

14.分析《教程》4.~en,的时间复杂度。
3.3节的求1n 
全排列的递归算法prm11(n)
15*.有以下多项式
:
n

n)xx3 x5 x7 x2n+1 

f(x,=-3!+5!-7!
+ 
…
+ 
(-1)(2n+1)! 

给出求f(x,值的递推式,

n) 分析其求解的时间复杂度。

3.2.2 
问答题参考答案
1.答:(1)采用顺序列举。
(2)采用组合列举。
(3)采用排列列举。
2.答:一般密码长度有限,密码由数字和字母等组成,可以采用穷举法枚举所有可能的
密码,对每个密码进行试探。如果加入验证码,就会延迟每次试探的时间,从而使得这样破
解密码变成几乎不可能。
3.答:递归算法是指直接或间接地调用自身的算法。递归模型由递归出口和递归体两
部分组成。
4.答:迭代算法与递归算法的相同点是都是解决“重复操作”的机制,不同点是递归算
法往往比迭代算法耗费更多的时间(调用和返回均需要额外的时间)与存储空间(用来保存
不同次调用下变量的当前值的栈空间),每个迭代算法原则上总可以转换成与它等价的递归
算法,反之不然。
a,表示a[共i+1个元素) 为大问题; a,

答:设f(i) i]( 中的最小元素, 设f(1)
表示a[0.
-共
i 
个元素)中的最小元素,为小问题。对应的递归定义如下:i1]( 
f(a,i)=a[0] 当i=0时
f(a,i)=min(f(i-1),a[i]) 

5. 
0.
i
a,1) 
a,其他
则f(n-求数组
a 
中
n 
个元素的最小元素。
答:设f(i) i]( 中的所有元素和, 设f(1)

a,表示a[共i+1个元素) 为大问题; a,

6. 
0.
i
表示a[0.
-1]( 中的所有元素和,为小问题。对应的递归定义如下:
i共
i 
个元素
)
f(i)=0] 当i=0
时


a,a[
f(i)f(i-1)+a[其他

a,=a,i] 
则f(a,1)求数组
a 
中
n 
个元素和。

n

7.答:设f(y)x+y,对应的递归定义如下。
当
x 
0时
x,=
f(x,==

y)
y 
f(x,=
x 
当y=0时

y)
f(x,=sc(x),uy))+2 其他

y)f(usc(

8.答:先求f(如图3.a) 求出f(=再求f(如图3.b) 求出
7), 1(所示, 7)5, 5), 1(所示, 
f(5)=3,所以f(f(7))的结果是3。

9.答:求f(3,的过程如图3.求出f(3,5)=
10.答:求T(
5)
的过程如下。
2所示, 27 。
n)
T(T(1)+n=[T(+(1)]T(2)n-1)


n)=n-n-2)n-+n=n-+n+
(
=T(3)n-+(2)


n-+n+(1)n

42

=… 
=n-+…+2 

T(1)+n+(1)

n+(n(Θ(=n-1)+…+2+1=n+1)/2=n2)。


图3.f(7)) 图3.3,5)的过程

1 求f(的过程2 求f(

11.解:构造的递归树如图3.3所示,第1层的问题规模为n,第2层的子问题的问题
规模为n/2,以此类推,当展开到第k+1 层时,其规模为n/2k 
=1,所以递归树的高度为
log2n+1 。
图3.

3 一棵递归树

第1层有一个结点,其时间为n, 其时间为4(=n,

第2层有4个结点, n/2)2以此类推, 
第
k 
层有4k-1个结点,每个子问题的规模为n/2k-1,其时间为4k-1(n/2k-1)=2k-1n。叶子
结点的个数为n,其时间为n。将递归树每一层的时间加起来,可得

k-1log2nn2)

T(n)=n+2n+ 
…+2n+ 
…+
n 
≈n*2=Θ(

12.答:(1)这里a=4,2,n)=n。nlogba 
=nlog24=n2,显然f(n)的阶小于nlogba 
,
b=f(
满足主方法中的情况①,所以T(logba 
)n2)。

n)=nΘ(

b=f(=logba 
=nlog24=logba

(2)这里a=4,2,n)n2。
Θn(=
n2,显然f(n)与n同阶,满足主方
法中的情况②,T(Θ(logban2)。
n)=nlog2n)=Θ(log2n 
4,b=2,n)logba 
=og24=n) log

(3)这里a=f(=n3。nnln2,显然f(的阶大于nba 
。另外, 
af(b)4×n3/8n3/2≤c1/2,
对于足够大的n,n/==f(n), 这里c=满足正规性条件,则有
T(=f(=Θ(

n)Θ(n))n3)。
n+1) Θ(

nn 

13.答:算法中两重for的执行次数为Σ1=Σi=n(
2 =n2)。对应的时Σ(i) 
i=1j=1 i=1 

43

间递推式如下: 
T(n)=1 当n=0时
Θ(log2n)。
rm11(n) 
T(n)n/2)+n2 其他情况

=4T(

ba 

n2
采用主方法,
a 
=4,b=2,
f 
(n)=n2,nlog=n2 与
f 
(n)的阶相同,则
T 
(n)= 

14.答:pen,用于求1~
n 
的全排列Pn 
,设其执行时间为T(n), 它首先调用
perm1(n-求出1n-1, n-再对Pn-1
n,1) ~1的全排列Pn-该小问题的执行时间为T(1), 
n

中每个集合元素(共(1)! 个集合元素)的每个位置(共
n 
个位置)插入n,合并结果得到
Pn 
, n-n!。所以递推式如下:

执行次数为n(1)!
T=
(1)=1 求P1 为常量

=n!g(~
n-1)+n! 当
n 
>1时
n-n-nn)因为
T1(n)=T(
则T(=(

令Tn(
)T(
n)( 
n 
的全排列中的排列个数为n!), 1)1)!g(1), 
代入T(=n-1)+n!中得到: 
n)-1)!g(n!g(
= 
(n-1)+n!

n
两边乘以n:nn)n(1)!g(1)n!=n-+n!
。


n!g(=n-n-+nn!g(1)
n
两边除以n!:n)=n-1)得到如下递推式
。


ng(g(+n,
g(1)=
1
g(=g(


n)n-1)/n+1 当
n 
>1时
采用直接展开法,n)g(1)/=n-n(1))+1/=…≤2 。

g(=n-n+1g(2)/(n-n+
1
n)n)≤
2
因此有T(=!)。
T(=n!g(n!


n)O(

15.答:为了简单省略
x 
参数
。
f(1)=x,g(1)=
x,(n) 
f(2)x3 
f(1)
+ 
(1)×x2 
=x-3!=-1)×g(3×2, 

g(2)=(-1)×g(1)×2x×23 

x3 x5 x2 

f(3)=x-3!+5!=f(2)
+ 
(-1)×g(2)×4×5, 

g(3)=(-1)×g(2)×4x×25 

可以推出求f(的递推式如下:

n)
f(1)=x,g(1)=
x


-1)×g(-1)×x2 

g(n)=(n(2n-2)(2n-1)
f(n)=n-1)+g(

f(n)
设求f(n)的执行时间为T(求f(需要求出g(但它们是同时计算的, 

n) nn)
), n) n), 也就是

说T(n)表示的是求f(和g(的时间,对应的执行时间的递推式如下: 
T(1)=O(1)
T(n)=T(1)

n-1)+O(当
n 
>1时

44

O()。

可以推出T(n)=
n 

3.算法设计题及其参考答案
3 

3.3.1 
算法设计题
1.有3种硬币若干个,面值分别是1分、2分、5分,如果要凑够1毛5,设计一个算法求
有哪些组合方式,共有多少种组合方式。
2.有一个整数序列是0,5,6,12,19,32,52,…, 其中第1项为0,第2项为5,第3项为
6,以此类推, n≥1)项。
采用迭代算法和递归算法求该数列的第n(

3.给定一个正整数n(1≤n≤100), 采用迭代算法和递归算法求s=1+(1+2)+(1+ 
2+3)+…+(1+2+…+n)。
4.一个数列的首项a1=0,后续奇数项和偶数项的计算公式分别为a2n 
=a2n-1+2, 
a2n+1=a2n-1+a2n 
-1,设计一个递归算法求数列的第
n 
项。
5.设计一个递归算法用于翻转一个非空字符串s(用String表示)。
6.对于不带头结点的非空整数单链表h,设计一个递归算法求其中值为
x 
的结点的
个数。
7.对于不带头结点的非空单链表h,设计一个递归算法删除其中第一个值为
x 
的
结点
8
。
.对于不带头结点的非空单链表h,设计一个递归算法删除其中所有值为
x 
的结点。

9.假设二叉树采用二叉链存储结构存放,结点值为整数,设计一个递归算法求二叉树
b 
中所有叶子结点值之和。
10.假设二叉树采用二叉链存储结构存放,结点值为整数,设计一个递归算法求二叉树
b 
中第k(1≤k≤二叉树
b 
的高度)层的所有结点值之和(根结点的层次为1)。
11.设计将十进制正整数
n 
转换为二进制数的迭代算法和递归算法。
12.在《的3.2节中采用迭代算法实现直接插入排序,请设计等效的递归算法。
教程》2.

13.在《的3.2节中采用迭代算法实现简单选择排序,请设计等效的递归算法。
教程》3.

在《教程》的3.2节中采用递归算法实现冒泡排序,请设计等效的迭代算法。

14. 
4.
在《教程》的3.4节中采用迭代算法求1n 
的幂集,请设计等效的递归算法。

15. 
3.~
16.给定一个含
n 
个元素的整数序列a,设计一个算法求其中两个不同元素相加的绝对
值的最小值。
采用非递归和递归算法创建一个n(阶螺旋矩阵并输出。例如,4时

的螺旋矩阵如下: 
1234 
1213145 
1116156 
109 8 7 

17. 
1≤n≤10) n=
45

46 
3.3.2 算法设计题参考答案
1.解:采用穷举法,设所需1分、2分和5分硬币的个数分别为i、j 和k,显然有0≤i≤15, 
0≤j≤7,0≤k≤3,约束条件i+2j+5k=15,用cnt表示组合方式数。对应的算法如下: 
int solve() { //求解算法 
int cnt=0; 
for(int i=0;i<=15;i++) { 
for(int j=0;j<=7;j++) { 
for(int k=0;k<=3;k++) { 
if(i+(2*j)+(5*k)==15) { 
System.out.printf("1 分硬币%d 个,2 分硬币%d 个,5 分硬币%d 个\n",i,j,k); 
cnt++; 
} 
} 
} 
} 
return cnt; 
} 
2.解:设f(n)为数列的第n 项,则
f(1)=0 
f(2)=5 
f(3)=6=f(1)+f(2)+1 
f(4)=12=f(2)+f(3)+1 
… 
可以归纳出当n>2时有f(n)=f(n-2)+f(n-1)+1。对应的迭代算法如下: 
int sequence1(int n) { //迭代算法 
int a=0,b=5,c=0; 
if(n==1) 
return a; 
else if(n==2) 
return b; 
else { 
for(int i=3;i<=n;i++) { 
c=a+b+1; 
a=b;b=c; 
} 
return c; 
} 
}
对应的递归算法如下: 
int sequence2(int n) { //递归算法 
if(n==1)

47 
return 0; 
else if(n==2) 
return 5; 
else 
return sequence2(n-2)+sequence2(n-1)+1; 
} 
3.解:设curs=1+2+…+(i-1),则curs+i 便是1+2+…+i,用ans累加所有的
curs(初始为0)。对应的迭代算法如下: 
int Sum1(int n){ //迭代算法 
int ans=0; 
int curs=0; 
for(int i=1;i<=n;i++){ 
curs+=i; 
ans+=curs; 
} 
return ans; 
}
设f(n)=1+(1+2)+(1+2+3)+…+(1+2+…+n),则f(n-1)=1+(1+2)+ 
(1+2+3)+…+(1+2+…+n-1),两式相减得到f(n)-f(n-1)=(1+2+…+n)= 
n(n+1)/2,则递归模型如下:
f(1)=1 
f(n)=f(n -1)+n(n +1)/2 
对应的递归算法如下: 
int Sum2(int n){ //递归算法 
if(n==1) 
return 1; 
else 
return Sum2(n-1)+n*(n+1)/2; 
} 
4.解:设f(m )计算数列的第m 项。当m 为偶数时,不妨设m =2n,则2n-1=m -1, 
所以有f(m)=f(m-1)+2。当m 为奇数时,不妨设m=2n+1,则2n-1=m-2,2n=m-1, 
所以有f(m )=f(m -2)+f(m -1)-1。对应的递归算法如下: 
int sequence(int m) { //递归算法 
if(m==1) 
return 0; 
else if(m%2==0) 
return sequence(m-1)+2; 
else 
return sequence(m-2)+sequence(m-1)-1; 
}

48 
5.解:设f(str,i)返回s[i..n-1](共n-i 个字符)的翻转字符串,为大问题;f(str, 
i+1)返回s[i..n-1](共n-i-1个字符)的翻转字符串,为小问题;i≥n 时空串的翻转结
果是空串。对应的递归模型如下: 
f(s,i)="" 当i ≥n 时
f(s,i)=f(s,i+1)+s[i] 其他情况 
对应的递归算法如下: 
String reverse1(String s,int i) { //递归算法 
if(i>=s.length()) 
return ""; 
else 
return reverse1(s,i+1)+s.charAt(i); 
}S
tring reverse(String s) { //求解算法 
return reverse1(s,0); 
} 
6.解:设f(h,x)返回单链表h 中值为x 的结点的个数,为大问题;f(h.next,x)返回
子单链表h.next中值为x 的结点的个数,为小问题;空单链表的结点的个数为0。对应的
递归模型如下: 
f(h,x)=0 当h =null时
f(h,x)=f(h.next,x)+1 当h.val=x 时
f(h,x)=f(h.next,x) 其他情况 
对应的递归算法如下: 
int Count(ListNode h,int x) { //求解算法 
if(h==null) 
return 0; 
else if(h.val==x) 
return Count(h.next,x)+1; 
else 
return Count(h.next,x); 
} 
7.解:设f(h,x)返回删除单链表h 中第一个值为x 的结点后的单链表,为大问题; 
f(h.next,x)返回删除子单链表h.next中第一个值为x 的结点后的单链表,为小问题。对
应的递归模型如下: 
f(h,x)=null 当h =null时
f(h,x)=h.next 当h.val=x 时
f(h,x)=h(h.next=f(h.next,x)) 其他情况 
对应的递归算法如下: 
ListNode Delfirstx(ListNode h,int x) { //递归算法 
if(h==null) return null; 
if(h.val==x)

49 
return h.next; 
else { 
h.next=Delfirstx(h.next,x); 
return h; 
} 
} 
8.解:设f(h,x)返回删除单链表h 中所有值为x 的结点后的单链表,为大问题; 
f(h.next,x)返回删除子单链表h.next中所有值为x 的结点后的单链表,为小问题。对应
的递归模型如下:
f(h,x)=null 当h =null时
f(h,x)=f(h.next,x) 当h.val=x 时
f(h,x)=h(h.next=f(h.next,x)) 其他情况 
对应的递归算法如下: 
ListNode Delallx(ListNode h,int x) { //递归算法 
if(h==null) return null; 
if(h.val==x) 
return Delallx(h.next,x); 
else { 
h.next=Delallx(h.next,x); 
return h; 
} 
} 
9.解:设f(b)返回二叉树b 中所有叶子结点值之和,为大问题,f(b.left)和f(b.right) 
分别返回二叉树b 的左、右子树中所有叶子结点值之和,为两个小问题。对应的递归模型
如下: 
f(b)=0 当b=null时
f(b)=b.val 当b 结点为叶子结点时
f(b)=f(b.left)+f(b.right) 其他 
对应的递归算法如下: 
int LeafSum(TreeNode b) { //递归算法 
if(b==null) return 0; 
if(b.left==null && b.right==null) 
return b.val; 
int lsum=LeafSum(b.left); 
int rsum=LeafSum(b.right); 
return lsum+rsum; 
} 
10.解:设f(b,h,k)返回二叉树b 中第k 层的所有结点值之和(初始时b 指向根结点, 
h 置为1表示结点b 的层次)。其递归模型如下:

50 
f(b,h,k)=0 当b=null时
f(b,h,k)=b.val 当h =k 时
f(b,h,k)=f(b.left,h +1,k)+f(b.right,h +1,k) 当h <k 时
f(b,h,k)=0 其他情况 
对应的递归算法如下: 
int LevelkSum1(TreeNode b,int h,int k) { //递归算法 
if(b==null) 
return 0; 
if(h==k) 
return b.val; 
if(h<k) { 
int lsum=LevelkSum1(b.left,h+1,k); 
int rsum=LevelkSum1(b.right,h+1,k); 
return lsum+rsum; 
} 
else return 0; 
}i
nt LevelkSum(TreeNode b,int k) { //求解算法 
return LevelkSum1(b,1,k); 
} 
11.解:设f(n)为n 的二进制数。求出n%2和n/2,n%2作为结果二进制数的最高
位,f(n/2)作为小问题。假设f(n/2)已经求出,将n%2作为其最高位得到f(n)的结果。
对应的递归模型如下: 
f(n)=空当n ≤0时
f(n)=n%2..f(n/2) 当n >0时
其中x..y 表示将x 作为y 的最高位。
采用数组存放转换的二进制数,每个元素表示一个二进制位,由于需要将n%2的二进
制位插入最前面,为此改为用Stack<Integer>集合存放转换的二进制数。对应的迭代算
法如下: 
Stack<Integer>trans1(int n) { //迭代算法 
Stack<Integer>ans=new Stack<>(); 
while(n>0) { 
int d=n%2; //求出二进制位d 
ans.push(d); //将d 作为高位的元素 
n/=2; //新值取代旧值 
} 
return ans; 
}
对应的递归算法如下: 
ArrayList<Integer>trans2(int n) { //递归算法 
ArrayList<Integer>ans=new ArrayList<>(); 
if(n<=0) return ans;

51 
ans=trans2(n/2); //先递后合 
int d=n%2; 
ans.add(d); 
return ans; 
} 
12.解:直接插入排序递归算法的设计思路参考《教程》中的3.2.2节。采用先递后合和
先合后递的两种递归算法如下: 
void Insert(int R[],int i) { //将R[i]有序插入R[0..i-1]中 
int tmp=R[i]; 
int j=i-1; 
do { //找R[i]的插入位置 
R[j+1]=R[j]; //将大于R[i]的元素后移 
j--; 
} while(j>=0 && R[j]>tmp); //直到R[j]<=tmp 为止 
R[j+1]=tmp; //在j+1 处插入R[i] 
} /***先递后合算法*****************************/ 
void InsertSort21(int R[],int i) { // 递 归直接插入排序 
if(i==0) return; 
InsertSort21(R,i-1); 
if(R[i]<R[i-1]) //反序时 
Insert(R,i); 
}v
oid InsertSort2(int R[]) { //递归算法:直接插入排序 
int n=R.length; 
InsertSort21(R,n-1); 
} /***先合后递算法*****************************/ 
void InsertSort31(int R[],int i) { // 递 归 直 接插入排序 
int n=R.length; 
if(i<1 || i>n-1) return; 
if(R[i]<R[i-1]) //反序时 
Insert(R,i); 
InsertSort31(R,i+1); 
}v
oid InsertSort3(int R[]) { //递归算法:直接插入排序 
InsertSort31(R,1); 
} 
13.解:简单选择排序递归算法的设计思路参考《教程》中的3.3.2节。采用先递后合和
先合后递的两种递归算法如下: 
void Select(int R[],int i) { //在R[i..n-1]中选择最小元素交换到R[i]位置 
int minj=i; //minj 表示R[i..n-1]中最小元素的下标 
for(int j=i+1;j<R.length;j++) { // 在 R[ i. . n-1]中找最小元素 
if(R[j]<R[minj])

52 
minj=j; 
} 
if(minj!=i) { //若最小元素不是R[i] 
int tmp=R[minj]; //交换R[minj]和R[i] 
R[minj]=R[i]; R[i]=tmp; 
} 
} /***先递后合算法*****************************/ 
void SelectSort21(int R[],int i) { // 递 归 的 简 单选择排序 
if(i==-1) return; //满足递归出口条件 
SelectSort21(R,i-1); 
Select(R,i); 
}v
oid SelectSort2(int R[]){ //递归的简单选择排序 
SelectSort21(R,R.length-2); 
} /***先合后递算法*****************************/ 
void SelectSort31(int R[],int i) { // 递 归 的 简 单选择排序 
int n=R.length; 
if(i==n-1) return; //满足递归出口条件 
Select(R,i); 
SelectSort31(R,i+1); 
}v
oid SelectSort3(int R[]) { //递归的简单选择排序 
SelectSort31(R,0); 
} 
14.解:冒泡排序迭代算法的设计思路参考《教程》中的3.4.2节。对应的算法如下: 
boolean exchange; //类变量
void Bubble(int R[],int i) { //在R[i..n-1]中冒泡最小元素到R[i]位置 
int n=R.length; 
for(int j=n-1;j>i;j--) { //无序区元素的比较,找出最小元素 
if(R[j-1]>R[j]) { //当相邻元素反序时 
int tmp=R[j]; //R[j]与R[j-1]进行交换 
R[j]=R[j-1]; R[j-1]=tmp; 
exchange=true; //本趟排序发生交换,置exchange 为true 
} 
} 
}v
oid BubbleSort1(int R[]) { //迭代算法:冒泡排序 
int n=R.length; 
for(int i=0;i<n-1;i++) { //进行n-1 趟排序 
exchange=false; //本趟排序前置exchange 为false 
Bubble(R,i); 
if(exchange==false) //本趟未发生交换时结束算法 
return; 
} 
}

53 
15.解:用Mi 表示1~i 的幂集,对应的递归模型如下。
M1 ={{},{1}} 
Mi =Mi-1 ∪Ai 当i >1时
其中,Ai=appendi(Mi-1,i)。幂集用List<List<Integer>>类型的Java集合存放,其中
每个List<Integer>类型的元素表示幂集中的一个集合。大问题是求{1~i}的幂集,小问
题是求{1~i-1}的幂集。采用先递后合和先合后递的两种递归算法如下: 
List<List<Integer>>deepcopy(List<List<Integer>>A) { //返回A 的深拷贝 
List<List<Integer>>B=new ArrayList<>(); 
for(List<Integer>x : A) 
B.add(new ArrayList<>(x)); 
return B; 
}L
ist<List<Integer>>appendi(List<List<Integer>>Mi_1,int i) { 
//向Mi_1 中每个集合元素的末尾添加i 
List<List<Integer>>Ai=deepcopy(Mi_1); 
for(int j=0;j<Ai.size();j++) 
Ai.get(j).add(i); 
return Ai; 
} /***先递后合算法*****************************/ 
List<List<Integer>>pset(int n,int i){ 
if(i==1) { 
List<List<Integer>>tmp=new ArrayList<>(); //建立tmp={{},{1}}并返回 
List<Integer>e1=new ArrayList<>(); 
tmp.add(e1); //添加{} 
List<Integer>e2=new ArrayList<>(); 
e2.add(1); 
tmp.add(e2); //添加{1} 
return tmp; 
} 
else { 
List<List<Integer>>Mi_1=pset(n,i-1); //递归求出Mi_1 
List<List<Integer>>Mi=Mi_1; //Mi 置为Mi_1 
List<List<Integer>>Ai=appendi(Mi_1,i); 
for(int j=0;j<Ai.size();j++) //将Ai 的所有集合元素添加到Mi 中 
Mi.add(Ai.get(j)); 
return Mi; //返回Mi 
} 
}L
ist<List<Integer>>subsets2(int n){ //递归算法 
return pset(n,n); 
}

54 
/***先合后递算法*****************************/ 
List<List<Integer>>pset(List<List<Integer>>M,int n,int i) { 
List<List<Integer>>A=deepcopy(appendi(M,i)); //求A 
for(int j=0;j<A.size();j++) //将A 的所有集合元素添加到M 中 
M.add(A.get(j)); 
if(i==n) //已经求出结果时返回M 
return M; 
else //否则递归调用 
return pset(M,n,i+1); 
}L
ist<List<Integer>>subsets3(int n) { //递归算法 
List<List<Integer>>M=new ArrayList<>(); 
List<Integer>e1=new ArrayList<>(); 
M.add(e1); //添加{} 
List<Integer>e2=new ArrayList<>(); 
e2.add(1); 
M.add(e2); //添加{1},置M={{},{1}} 
if(n==1) 
return M; 
else 
return pset(M,n,2); 
} 
16.解法1:采用穷举法,对任意两个不同元素求相加的绝对值,比较求最小值ans,算
法的时间复杂度为O(n2)。对应的算法如下: 
int minabs1(int a[]) { //解法1 
int n=a.length; 
int ans=0x3f3f3f3f; //初始置为∞ 
for(int i=0;i<n-1;i++) { 
for(int j=i+1;j<n;j++) { 
ans=Math.min(ans,Math.abs(a[i]+a[j])); 
if(ans==0) return ans; //当结果为0 时不必继续 
} 
} 
return ans; 
}
解法2:改进穷举法算法。如果a 中元素全部是正数,只需要找到其中两个不同的最
小元素,答案就是它们相加的结果,对应的时间复杂度为O(n)。但这里a 中可能有负数, 
那么在这种情况下就变成了求差的绝对值,而差的绝对值最小的两个整数一定是大小最相
近的,为此先对数组a 递增排序,用low和high前后遍历,求f=a[low]+a[high],将最小
绝对值保存在ans中,如果f>0,除去a[high];如果f<0,除去a[low]。算法的时间主要
花费在排序上,时间复杂度为O(nlog2n)。对应的算法如下: 
int minabs2(int a[]) { //解法2 
int n=a.length;

55 
int ans=0x3f3f3f3f; //初始置为∞ 
Arrays.sort(a); //递增排序 
int low=0,high=n-1; 
while(low<high) { 
int f=a[low]+a[high]; 
ans=Math.min(ans,Math.abs(f)); 
if(ans==0) return ans; //当结果为0 时不必继续 
if(f>0) high--; 
if(f<0) low++; 
} 
return ans; 
} 
17.解:采用递归解法。设f(x,y,start,n)用于创建左上角为(x,y)、起始元素值为
start的n 阶螺旋矩阵,共n 行n 列,它是大问题;f(x+1,y+1,start,n-2)用于创建左上
角为(x+1,y+1)、起始元素值为start的n-2阶螺旋矩阵,共n-2行n-2列,它是小问
题。图3.4所示为n=4时的大问题和小问题。对应的递归模型如下: 
f(x,y,start,n)≡ 不做任何事情当n ≤0时
f(x,y,start,n)≡ 产生只有一个元素的螺旋矩阵当n =1时
f(x,y,start,n)≡ 产生(x,y)的那一圈; 当n >1时 
f(x +1,y +1,start,n -2) 
图3.4 n=4时的大问题和小问题 
非递归解法则是采用循环语句代替递归调用。对应的算法如下: 
class Solution { 
int s[][]; 
int n; 
int start; 
void CreateaLevel(int ix,int iy,int ex,int ey) { //产生一圈的螺旋矩阵元素 
if(ix==ex) //该圈只有一个元素时 
s[ix][iy]=start++; 
else { 
int curx=ix; 
int cury=iy; 
while(curx!=ex) { //上一行 
s[iy][curx]=start++; 
curx++; 
} 
while(cury!=ey) { //右一列 
s[cury][ex]=start++;

56 
cury++; 
} 
while(curx!=ix) { //下一行 
s[ey][curx]=start++; 
curx--; 
} 
while(cury!=iy) { //左一列 
s[cury][ix]=start++; 
cury--; 
} 
} 
} 
void Spiral1(int n){ //非递归求解算法 
this.n=n; 
s=new int[n][n]; 
start=1; 
int ix=0,iy=0; 
int ex=n-1,ey=n-1; 
while(ix<=ex && iy<=ey) 
CreateaLevel(ix++,iy++,ex--,ey--); 
} 
void Spiral2(int x,int y,int n) { // 递归创建螺旋矩阵 
if(n<=0) //递归结束条件 
return; 
if(n==1) { //矩阵大小为1 时 
s[x][y]=start; 
return; 
} 
CreateaLevel(x,y,x+n-1,y+n-1); // 产生一圈的螺旋矩阵元素 
Spiral2(x+1,y+1,n-2); //递归调用 
} 
void Spiral2(int n) { //递归求解算法 
this.n=n; 
s=new int[n][n]; 
start=1; 
Spiral2(0,0,n); 
} 
} 
3.4 在线编程题及其参考答案
3.4.1 LeetCode647———回文子串★★ 
问题描述:给定一个字符串s(1≤s.length≤1000,s 由小写英文字母组成),设计一个
算法求这个字符串中回文子串的数目。注意,具有不同开始位置或结束位置的子串,即使是
由相同的字符组成的,也会被视作不同的子串。例如,s="aaa",有6个回文子串,即"a"、