资源简介

(共24张PPT)
三、 递归算法及其应用
第五章　数据结构与算法
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 如下程序的功能为使用递归的方法快速计算xn。画线处的代码是(　　)
def fun(x,n):
　　if n==1:
　　　　return x
　　t=fun(____________________)
　　if n%2==1:
　　　　return x*t*t
　　else:
　　　　return t*t
A. n//2,x B. n/2,x
C. x,n//2 D. x,n/2
【解析】 本题考查递归算法及Python程序实现。由if条件分支代码可知,此处先递归计算x^(n//2),即t=fun(x,n//2),如果n是偶数,则返回x*t*t,如果n是奇数,则直接返回t*t,C正确。
C
2. 对于任意非空字符串s,下面两个程序段输出结果相同,则方框处应填入的代码是(　　)
D
def f(s,t): 　　if t >= len(s)－2: 　　　　return s[t] 　　return f(s,t＋2) ＋ s[t] print(f(s,0)) r = ""
n = len(s)
for i in range(0,n,2):
　　　　　　　　
print(r)
A. r = s[n－i]＋r B. r = r＋s[n－i－1]
C. r = r＋s[i] D. r = s[i]＋r
【解析】 本题考查递归和递推。左边的程序段是一个递归函数,其逻辑是:如果 t >= len(s) － 2,返回字符串 s 的第 t 个字符,否则递归调用 f(s, t ＋ 2),并将结果与 s[t] 拼接。因此函数 f(s, 0) 的作用是从字符串 s 的第 0 个字符开始,每隔一个取一个字符(偶数索引),并将这些字符逆序拼接成结果字符串。右边的程序段则是采用循环递推的方式,索引从 0 开始遍历字符串,且每次步进 2(跳过一个字符),再拼接成结果字符串。因索引必须是偶数且逆序拼接结果字符串,而n的奇偶性不确定,D正确。
3. 有如下Python程序:
def fib(n):
　　if n == 1 or n == 2:
　　　　s = 1
　　else:
　　　　s = fib(n－1)＋ fib(n－2)
　　return s
n = int(input())
print(fib(n))
若输入n的值为8,则输出是(　　)
A. 5 B. 8
C. 13 D. 21
【解析】 本题考查递归算法的程序实现。在自定义函数中,又出现调用自定义函数本身,由此判断程序使用的是递归算法,代入n=8,得到的值是21,D正确。
D
4. 有如下程序段:
def f(x,n):
　　if n==0:
　　　　return 1
　　else:
　　　　return x*f(x,n－1)
print(f(2,10))
程序执行后,输出的结果是(　　)
A. 1 B. 1024
C. 2048 D. 362800
【解析】 本题考查递归算法的程序实现。在自定义函数中,又出现调用自定义函数本身,根据递推的过程f(2,10)=2*f(2,9)=2*2*f(2,8)…=210*f(2,1)=210=1024,B正确。
B
5. 有如下Python程序:
def p(x):
　　if x>3:
　　　　return p(x－1)＋p(x－2)＋p(x－3)
　　else:
　　　　return x
n=int(input())
print(p(n))
若输入n的值为6时,则输出的结果是(　　)
A. 6 B. 11
C. 20 D. 31
【解析】 本题考查递归算法。当n=6时,p(6)=p(5)＋p(4)＋p(3),其中p(5)=p(4)＋p(3)＋p(2) =6＋3＋2=11,由此可以求出p(6)=11＋6＋3=20,C正确。
C
6. 有8级楼梯,从第0级开始往上走,每次可以走一级或者两级,下列自定义函数f,可以计算走完n级楼梯有多少种走法,那么走完这8级楼梯的走法有(　　)
def f(n):
　　if n==1:
　　　　return 1
　　elif n==2:
　　　　return 2
　　else:
　　　　return f(n－1)＋f(n－2)
A. 34种 B. 35种
C. 36种 D. 37种
A
【解析】 这是关于前2个数为1,2的斐波那契数列的应用,在程序中使用递归算法思想解决。根据递归调用的规则可以推出递推式为 f(n)=f(n－1)＋f(n－2),因此f(3)=f(1)＋f(2)=3, f(4)=f(2)＋f(3)=5, f(5) =f(4)＋f(3)=8, f(6)=f(5)＋f(4) =13, f(7)=f(6)＋ f(5)=21, f(8)=f(7)＋f(6)=34,A正确。
7. 有如下Python程序段:
def trans(m,n):
　　if m!=0:
　　　　r=m%n
　　　　return trans(m//n,n)＋str(r)
　　else:
　　　　return "0"
a=int(input("a="))
b=int(input("b="))
print(trans(a,b))
执行该程序段,依次输入11和2,则输出的结果是(　　)
A. 1011 B. 1101
C. 01011 D. 11010
C
【解析】 本题考查递归算法以及进制转换问题。列出表格如下:
trans(11,2) trans(5,2) trans(2,2) trans(1,2) trans(0,2)
返回值 trans(5,2) ＋"1" trans(2,2) ＋"11" trans(1,2) ＋"011" trans(1,2) ＋"1011" “01011”
综上,C正确。
8. 有如下Python程序段:
def f(x):
　　if x==1 or x==2:
　　　　return 1
　　else:
　　　　return f(x－1)＋f(x－2)
s=0
for i in range(2,6):
　　s＋=f(i)
print(s)
执行该程序段后,变量s的值是(　　)
A. 20 B. 19
C. 12 D. 11
【解析】 本题的递归式是f(x)=f(x－1)＋f(x－2),边界值为:当x为1或2时,返回1,即x从3开始,f(x)为前两项的和,循环中s对f(2)到f(5)进行求和,即s=1＋2＋3＋5=11,D正确。
D
关键能力练
9. 定义如下递归函数,计算正整数n的每位数字之和,例如n=123,函数返回值为6。
def f(n):
　　x = 　　(1)　　
　　if x==0:
　　　　　return n
　　else:
　　　　　y = 　　　(2)　　　
　　　　　return 　　(3) 　　
上述程序段方框处可选的代码如下:
①n%10　②n//10　③y＋f(x)　④y＋f(n － 1)
则方框处的代码依次是(　　)
A. ①②③ B. ①②④
C. ②①③ D. ②①④
C
【解析】 本题考查递归代码的分析与理解能力。计算正整数n的每位数字之和,可以得出其递归公式:f(n)=f(n//10)＋n%10,当n<10时递归结束。结合题目给出的代码,依次分别是(1)n//10、(2)n%10、(3)y＋f(x),C正确。
10. 定义如下函数:
def move(n,a,b,c):
　　if n==1:
　　　　print(a,"－>",c)
　　　　return
　　move(n－1,a,c,b)
　　move(1,a,b,c)
　　move(n－1,b,a,c)
执行语句move(2,"A","B","C"),输出的第一行内容是(　　)
A. a－>c B. A－>C
C. a－>b D. A－>B
D
【解析】 本题考查递归算法及自定义函数知识。由代码可知,此为汉诺塔的递归函数,递归结束条件是n=1。将move(2,"A","B","C")中的条件代入模拟后可以发现,第一行是move(1,"A","C","B"),此时满足递归函数的结束条件,因此执行print语句,按照参数的先后次序关系,第一行应该输出A－> B,D正确。
11. 有如下Python程序段来判断是否为素数:
from math import sqrt
def prime(x,y):
　　if y>int(sqrt(x))＋1:
　　　　return _______________
　　elif x<2 or x%y==0:
　　　　return _______________
　　else:
　　　　return _______________
a=int(input("请输入正整数:"))
if prime(a,2):
　　print(a,"是素数!")
else:
　　print(a,"不是素数!")
上述程序段中画线处可选的代码如下:
①True　②False　③prime(x,y＋1)
画线处应填入的代码的顺序是(　　)
A. ②③① B. ②①③ C. ①③② D. ①②③
D
【解析】 本题考查递归算法及自定义函数知识。本题的突破点是,根据素数问题的定义,以及代码elif x<2 or x%y==0,此时x能被y整除,因此x肯定不是素数,故返回值应该是False,D正确。
12. 运行下列Python程序段,输出结果是(　　)
def trans(n):
　　if n <= 1:
　　　　return str(n)
　　else:
　　　　return trans(n//2)＋ str(n%2)
print(trans(13))
A. 1101 B. 1011
C. 13 D. 31
【解析】 本题考查递归算法及自定义函数知识。由代码可知,递归函数trans的递归结束条件是n<=1。若参数n>1则进入递归调用,将参数n=13条件代入函数模拟后可以发现,trans(13)=trans(6)＋"1"=trans(3)＋"01"=trans(1)＋"101",此时满足递归函数的结束条件,因此最左边的值为“1”,因此最终结果为“1101”,A正确。该递归函数的功能是将参数n转换为二进制输出。
A
13. 有如下Python程序段:
def f(x):
　　　if x == 1 or x == 2:
　　　　　return 1
　　　else:
　　　　　return f(x － 1)＋ f(x － 2)
s = 0
for i in range(1, 4):
　　　s ＋= f(i)
print(s)
执行该程序段后,f函数被调用的次数是(　　)
A. 3 B. 4
C. 5 D. 10
【解析】 本题考查自定义函数调用相关知识。在循环中求f(1)＋f(2)＋f(3)的和,其中f(1)调用了1次f函数,f(2)调用了1次f函数,f(3)调用了3次f函数,一共5次。C正确。
C
14. 有如下 Python 程序段:
def fac(n):
　　if n==0 :　#①
　　　　s=1
　　else:
　　　　s=n*fac(n－1)
　　return s
print(fac(3))
下列说法中,错. 误. 的是(　　)
A. 该程序运用了递归算法
B. 程序运行后,fac()函数被调用3次
C. 若问题规模为n,该程序段的时间复杂度为O(n)
D. 将①处代码改为“n==1”,该程序功能不变
【解析】 本题考查自定义函数和递归。fac()函数被调用4次,B符合题意。
B
15. 定义如下函数:
def f(k):
　　if k<=3:
　　 　print(k)
　　 　return
　　for i in range(1,4):
　　 　f(k－i)
　　return
执行语句f(6),则f(3)被调用的次数为(　　)
A. 1次 B. 2次
C. 3次 D. 4次
【解析】 本题考查递归函数相关知识。f(6)执行for语句调用f(5)、f(4)、f(3);f(5)执行for语句调用f(4)、f(3)、f(2);f(4)执行for语句调用f(3)、f(2)、f(1)。可知f(6)、f(5)、f(4)分别调用f(3)一次,f(4)被调用了2次,所以f(3)一共被调用4次。D正确。
D三、 递归算法及其应用
1. 如下程序的功能为使用递归的方法快速计算xn。画线处的代码是(　C　)
def fun(x,n):
　　if n==1:
　　　　return x
　　t=fun(　　　　)
　　if n%2==1:
　　　　return x*t*t
　　else:
　　　　return t*t
A. n//2,x B. n/2,x
C. x,n//2 D. x,n/2
【解析】 本题考查递归算法及Python程序实现。由if条件分支代码可知,此处先递归计算x^(n//2),即t=fun(x,n//2),如果n是偶数,则返回x*t*t,如果n是奇数,则直接返回t*t,C正确。
2. 对于任意非空字符串s,下面两个程序段输出结果相同,则方框处应填入的代码是(　D　)
def f(s,t): 　　if t >= len(s)－2: 　　　　return s[t] 　　return f(s,t＋2) ＋ s[t] print(f(s,0)) r = "" n = len(s) for i in range(0,n,2): 　　　　　　　　 print(r)
A. r = s[n－i]＋r B. r = r＋s[n－i－1]
C. r = r＋s[i] D. r = s[i]＋r
【解析】 本题考查递归和递推。左边的程序段是一个递归函数,其逻辑是:如果 t >= len(s) － 2,返回字符串 s 的第 t 个字符,否则递归调用 f(s, t ＋ 2),并将结果与 s[t] 拼接。因此函数 f(s, 0) 的作用是从字符串 s 的第 0 个字符开始,每隔一个取一个字符(偶数索引),并将这些字符逆序拼接成结果字符串。右边的程序段则是采用循环递推的方式,索引从 0 开始遍历字符串,且每次步进 2(跳过一个字符),再拼接成结果字符串。因索引必须是偶数且逆序拼接结果字符串,而n的奇偶性不确定,D正确。
3. 有如下Python程序:
def fib(n):
　　if n == 1 or n == 2:
　　　　s = 1
　　else:
　　　　s = fib(n－1)＋ fib(n－2)
　　return s
n = int(input())
print(fib(n))
若输入n的值为8,则输出是(　D　)
A. 5 B. 8
C. 13 D. 21
【解析】 本题考查递归算法的程序实现。在自定义函数中,又出现调用自定义函数本身,由此判断程序使用的是递归算法,代入n=8,得到的值是21,D正确。
4. 有如下程序段:
def f(x,n):
　　if n==0:
　　　　return 1
　　else:
　　　　return x*f(x,n－1)
print(f(2,10))
程序执行后,输出的结果是(　B　)
A. 1 B. 1024
C. 2048 D. 362800
【解析】 本题考查递归算法的程序实现。在自定义函数中,又出现调用自定义函数本身,根据递推的过程f(2,10)=2*f(2,9)=2*2*f(2,8)…=210*f(2,1)=210=1024,B正确。
5. 有如下Python程序:
def p(x):
　　if x>3:
　　　　return p(x－1)＋p(x－2)＋p(x－3)
　　else:
　　　　return x
n=int(input())
print(p(n))
若输入n的值为6时,则输出的结果是(　C　)
A. 6 B. 11
C. 20 D. 31
【解析】 本题考查递归算法。当n=6时,p(6)=p(5)＋p(4)＋p(3),其中p(5)=p(4)＋p(3)＋p(2) =6＋3＋2=11,由此可以求出p(6)=11＋6＋3=20,C正确。
6. 有8级楼梯,从第0级开始往上走,每次可以走一级或者两级,下列自定义函数f,可以计算走完n级楼梯有多少种走法,那么走完这8级楼梯的走法有(　A　)
def f(n):
　　if n==1:
　　　　return 1
　　elif n==2:
　　　　return 2
　　else:
　　　　return f(n－1)＋f(n－2)
A. 34种 B. 35种
C. 36种 D. 37种
【解析】 这是关于前2个数为1,2的斐波那契数列的应用,在程序中使用递归算法思想解决。根据递归调用的规则可以推出递推式为 f(n)=f(n－1)＋f(n－2),因此f(3)=f(1)＋f(2)=3, f(4)=f(2)＋f(3)=5, f(5) =f(4)＋f(3)=8, f(6)=f(5)＋f(4) =13, f(7)=f(6)＋ f(5)=21, f(8)=f(7)＋f(6)=34,A正确。
7. 有如下Python程序段:
def trans(m,n):
　　if m!=0:
　　　　r=m%n
　　　　return trans(m//n,n)＋str(r)
　　else:
　　　　return "0"
a=int(input("a="))
b=int(input("b="))
print(trans(a,b))
执行该程序段,依次输入11和2,则输出的结果是(　C　)
A. 1011 B. 1101
C. 01011 D. 11010
【解析】 本题考查递归算法以及进制转换问题。列出表格如下:
trans(11,2) trans(5,2) trans(2,2) trans(1,2) trans(0,2)
返回值 trans(5,2) ＋"1" trans(2,2) ＋"11" trans(1,2) ＋"011" trans(1,2) ＋"1011" “01011”
综上,C正确。
8. 有如下Python程序段:
def f(x):
　　if x==1 or x==2:
　　　　return 1
　　else:
　　　　return f(x－1)＋f(x－2)
s=0
for i in range(2,6):
　　s＋=f(i)
print(s)
执行该程序段后,变量s的值是(　D　)
A. 20 B. 19
C. 12 D. 11
【解析】 本题的递归式是f(x)=f(x－1)＋f(x－2),边界值为:当x为1或2时,返回1,即x从3开始,f(x)为前两项的和,循环中s对f(2)到f(5)进行求和,即s=1＋2＋3＋5=11,D正确。
9. 定义如下递归函数,计算正整数n的每位数字之和,例如n=123,函数返回值为6。
def f(n):
　　x = 　　(1)　　
　　if x==0:
　　　　　return n
　　else:
　　　　　y = 　　　(2)　　　
　　　　　return 　　(3) 　　
上述程序段方框处可选的代码如下:
①n%10　②n//10　③y＋f(x)　④y＋f(n － 1)
则方框处的代码依次是(　C　)
A. ①②③ B. ①②④
C. ②①③ D. ②①④
【解析】 本题考查递归代码的分析与理解能力。计算正整数n的每位数字之和,可以得出其递归公式:f(n)=f(n//10)＋n%10,当n<10时递归结束。结合题目给出的代码,依次分别是(1)n//10、(2)n%10、(3)y＋f(x),C正确。
10. 定义如下函数:
def move(n,a,b,c):
　　if n==1:
　　　　print(a,"－>",c)
　　　　return
　　move(n－1,a,c,b)
　　move(1,a,b,c)
　　move(n－1,b,a,c)
执行语句move(2,"A","B","C"),输出的第一行内容是(　D　)
A. a－>c B. A－>C
C. a－>b D. A－>B
【解析】 本题考查递归算法及自定义函数知识。由代码可知,此为汉诺塔的递归函数,递归结束条件是n=1。将move(2,"A","B","C")中的条件代入模拟后可以发现,第一行是move(1,"A","C","B"),此时满足递归函数的结束条件,因此执行print语句,按照参数的先后次序关系,第一行应该输出A－> B,D正确。
11. 有如下Python程序段来判断是否为素数:
from math import sqrt
def prime(x,y):
　　if y>int(sqrt(x))＋1:
　　　　return 　　　
　　elif x<2 or x%y==0:
　　　　return 　　　
　　else:
　　　　return 　　　
a=int(input("请输入正整数:"))
if prime(a,2):
　　print(a,"是素数!")
else:
　　print(a,"不是素数!")
上述程序段中画线处可选的代码如下:
①True　②False　③prime(x,y＋1)
画线处应填入的代码的顺序是(　D　)
A. ②③① B. ②①③
C. ①③② D. ①②③
【解析】 本题考查递归算法及自定义函数知识。本题的突破点是,根据素数问题的定义,以及代码elif x<2 or x%y==0,此时x能被y整除,因此x肯定不是素数,故返回值应该是False,D正确。
12. 运行下列Python程序段,输出结果是(　A　)
def trans(n):
　　if n <= 1:
　　　　return str(n)
　　else:
　　　　return trans(n//2)＋ str(n%2)
print(trans(13))
A. 1101 B. 1011
C. 13 D. 31
【解析】 本题考查递归算法及自定义函数知识。由代码可知,递归函数trans的递归结束条件是n<=1。若参数n>1则进入递归调用,将参数n=13条件代入函数模拟后可以发现,trans(13)=trans(6)＋"1"=trans(3)＋"01"=trans(1)＋"101",此时满足递归函数的结束条件,因此最左边的值为“1”,因此最终结果为“1101”,A正确。该递归函数的功能是将参数n转换为二进制输出。
13. 有如下Python程序段:
def f(x):
　　　if x == 1 or x == 2:
　　　　　return 1
　　　else:
　　　　　return f(x － 1)＋ f(x － 2)
s = 0
for i in range(1, 4):
　　　s ＋= f(i)
print(s)
执行该程序段后,f函数被调用的次数是(　C　)
A. 3 B. 4
C. 5 D. 10
【解析】 本题考查自定义函数调用相关知识。在循环中求f(1)＋f(2)＋f(3)的和,其中f(1)调用了1次f函数,f(2)调用了1次f函数,f(3)调用了3次f函数,一共5次。C正确。
14. 有如下 Python 程序段:
def fac(n):
　　if n==0:　#①
　　　　s=1
　　else:
　　　　s=n*fac(n－1)
　　return s
print(fac(3))
下列说法中,错误的是(　B　)
A. 该程序运用了递归算法
B. 程序运行后,fac()函数被调用3次
C. 若问题规模为n,该程序段的时间复杂度为O(n)
D. 将①处代码改为“n==1”,该程序功能不变
【解析】 本题考查自定义函数和递归。fac()函数被调用4次,B符合题意。
15. 定义如下函数:
def f(k):
　　if k<=3:
　　 　print(k)
　　 　return
　　for i in range(1,4):
　　 　f(k－i)
　　return
执行语句f(6),则f(3)被调用的次数为(　D　)
A. 1次 B. 2次
C. 3次 D. 4次
【解析】 本题考查递归函数相关知识。f(6)执行for语句调用f(5)、f(4)、f(3);f(5)执行for语句调用f(4)、f(3)、f(2);f(4)执行for语句调用f(3)、f(2)、f(1)。可知f(6)、f(5)、f(4)分别调用f(3)一次,f(4)被调用了2次,所以f(3)一共被调用4次。D正确。

展开更多......

收起↑