资源简介

5.1　递归算法思想
学习目标　
1.根据代码的运行次数与n的关系,掌握时间复杂度的计算方法。
2.掌握迭代算法的本质是每一次迭代得到的结果会作为下一次迭代的初始值。
3.掌握递归算法的本质通过重复将问题分解为同类的子问题而解决问题的方法。
　　　　　　 　　　　　 　　　　　
(2023年6月浙江省选考)定义如下函数:
def f(a,s):
　　if a>=s:
　　　　return a
　　else:
　　　　return f(a+1,s-a)
执行语句k=f(6,21)后,k的值为(　　)
A.6 B.7
C.8 D.9
　　一个算法中的语句执行次数称为语句频度或时间频度,算法中基本操作重复执行的次数是问题规模n的某个函数,记为T(n)。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。时间复杂度从小大到依次为常数阶、对数阶、线性阶、平方阶和指数阶。复杂问题的求解过程常常包含基本操作的多次重复进行,重复基本操作的常用方式有迭代和递归。迭代一般采用循环结构,通过某种递推式,不断更新变量新值,直到得到问题的解。递归则是算法中存在自调用,将大问题化为相同结构的小问题来求解,递归是一种有效的算法设计方法。
例1 定义如下函数:
def rf(n):
　　if n<3:
　　　　return n
　　return rf(n-1)+rf(n-3)
执行语句v=rf(5),函数rf被调用的次数是(　　)
A.11 B.5
C.7 D.15
变式1 有如下Python程序段:
def judge(s):
　　if len(s)==2:
　　　　return s[0]==s[1]
　　res=[];n=len(s)
　　for i in range(n-1):
　　　　r=(s[i]+s[i+1])%10
　　　　res.append(r)　#在res列表末尾添加一个元素r
　　return judge(res)
以下s执行judge(s)后,值为False的是(　　)
A.[2,3,6,9] B.[5,6,7,8]
C.[9,7,4,2] D.[3,9,0,2]
例2 对于任意非空字符串s,甲、乙程序段输出结果相同,则乙程序段加框处的正确代码为(　　)
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
变式2 甲、乙程序段的功能相同,则乙程序段加框处的正确代码为(　　)
a=1 b=1 m=int(input("请输入m的值:")) while a+b<=m: 　　c=a+b 　　a=b 　　b=c print(b) def f(a,b): 　　c=a+b 　　if c>m: 　　　　return b 　　else: 　　　　return 　　　　 m=int(input(“请输入m的值:”)) print(f(1,1))
甲程序段 乙程序段
A.f(b,c) B.f(a,b)
C.f(a,c) D.f(c,b)
1.有如下Python程序段:
def f(n):
　　if n<=1:
　　　　return 1
　　else:
　　　　return f(n-1)+f(n-2)
print(f(3))
程序运行后,函数f被调用的次数是(　　)
A.5 B.4
C.3 D.2
2.定义如下函数:
def quick(a):
　　if len(a)<=1:
　　　　return a
　　L="";M="";R=""
　　p=a[0]
　　for x in a:
　　　　if x　　　　　　L+=x
　　　　elif x==p:
　　　　　　M+=x
　　　　else:
　　　　　　R+=x
　　return quick(L)+M+quick(R)
若m="gibcb",执行语句st=quick(m),下列说法正确的是(　　)
A.该函数采用了迭代算法
B.程序实现对m中字符降序排序
C.函数quick被调用4次
D.加框处修改为p=a[-1],st结果不变
3.定义如下函数:
def p(x,y):
　　if x%y==0:
　　　　print(y)
　　else:
　　　　p(y,x%y)
　　　　print(y)
执行语句p(64,18)后,依次输出的结果为(　　)
A.8,10,8,2 B.2,8,10,18
C.4,10,18 D.18,10,4
4.定义如下函数:
def f(a,n,m):
　　if n==0:
　　　　return m
　　elif a[n-1]　　　　return f(a,n-1,m)
　　else:
　　　　return f(a,n-1,a[n-1])
若a的值为[13,83,57,85,78,74,44,80],执行语句k=f(a,len(a),0)后,k的值为(　　)
A.13 B.44
C.80 D.85
5.有如下Python程序段
def code(t):
　　if len(t)==0:
　　　　return ""
　　k=int(t[0])
　　return code(t[1:])+str((k+3)%8)
s=input("输入原始数据:")
answer=code(s)
print("加密结果为:",answer)
若最终输出的加密结果为2174,则输入的原始数据是(　　)
A.7641 B.1467
C.5427 D.7245
6.有如下Python代码段:
from random import randint
def f(lst,x):
　　if len(lst)==0:
　　　　return []
　　if lst[0]%x!=0:
　　　　return [lst[0]]+f(lst[1:],x)
　　else:
　　　　return f(lst[1:],x)
a=[5,8,7,12,10,3]
t=randint(3,5)
a=f(a,t)
运行程序后,a的值不可能是(　　)
A.[5,8,7,10] B.[8,7,12,3]
C.[8,7,10,3] D.[5,7,10,3]
7.定义如下Python函数:
def f(m,n):
　　if m>=n:
　　　　return m
　　else:
　　　　return f(m+m%2+1,n-1)+1
执行语句k=f(6,12)后,k的值为(　　)
A.11 B.12
C.13 D.14
8.定义如下函数:
def chg(k):
　　if k==-1:
　　　　return ""
　　else:
　　　　c=chr(ord("a")+k)
　　　　if k%2==1:
　　　　　　return c+chg(k-1)
　　　　else:
　　　　　　return chg(k-1)+c
执行语句m=chg(4)后,m的值为(　　)
A."ecabd" B."dbace"
C."abcde" D."edcba"
9.定义如下函数:
def f(s):
　　if len(s)==1:
　　　　return s[0]
　　elif len(s)==2:
　　　　return s[0]+s[1]
　　else:
　　　　return f(s[0:len(s)//3])+f(s[len(s)//3:len(s)])
执行语句s=f([1,2,3,4,5,6]),函数f被调用的次数是(　　)
A.3 B.5
C.7 D.15
10.定义如下函数:有如下Python程序段:
def fab(a,b):
　　if a%b==0:
　　　　return b
　　elif a>b:
　　　　return fab(a-b,b)
　　else:
　　　　return fab(a,b-a)
print(fab(8,4)-fab(4,8))
程序运行后,输出的结果为(　　)
A.0 B.2
C.4 D.8
11.有如下Python自定义函数:
def fun(x,i):
　　if x　　　　return i
　　elif x%i==0:
　　　　return x
　　else:
　　　　return fun(x-i,i+1)
执行语句k=fun(37,3)后,k的值为(　　)
A.5 B.6
C.30 D.34
12.定义如下函数:
def f(s,r):
　　if s-r**2<0 or r==0:
　　　　return r+1
　　else:
　　　　return f(s-r**2,r-1)
执行语句k=f(50,5)后,k的值为(　　)
A.4 B.3
C.2 D.1
13.对于任意非空的列表a,甲、乙程序段输出结果相同,则乙程序段加框处的代码为(　　)
甲: a=[3,2,-2,-3,5] tot=0 for i in range(len(a)): 　　if a[i]>0: 　　　　tot+=a[i] print(tot) 乙: def find(a,i): 　　if i==len(a): 　　　　return 0 　　cur=a[i] 　　if cur<0: 　　　　cur=0 　　return cur+ 　　　　 print(find(a,0))
A.find(a,len(a)-i)
B.find(a,len(a)-1-i)
C.find(a,i+1)
D.find(a,i-1)
14.定义如下递归函数,计算正整数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)
则(1)(2)(3)处代码依次为(　　)
A.①②③ B.①②④
C.②①③ D.②①④
15.定义函数isPalidrome用于判断回文字符串:
def isPalidrome(s):
　　if len(s)<=1:
　　　　return True
　　elif s[0]!=s[len(s)-1]:
　　　　return False
　　else:
　　　　return 　　　　　
已知代码划线处可选语句为:
①isPalidrome(s[1:-1])
②isPalidrome(s[2:-1])
③isPalidrome(s[1:len(s)-1])
④isPalidrome(s[2:len(s)-1]),则可填入的语句是(　　)
A.②或③ B.③或④
C.①或② D.①或③
16.定义如下函数:
def search(lst,i,j,key):
　　if i>j:
　　　　return -1
　　m=(i+j)//2
　　if lst[m]>key:
　　　　return search(lst,i,m-1,key)
　　elif lst[m]　　　　return search(lst,m+1,j,key)
　　else:
　　　　return m
若列表lst为[12,31,47,50,55,55,71,76],执行语句search(lst,0,7,51),该函数被调用的次数为(　　)
A.1 B.2
C.3 D.4
17.定义如下函数:
def inquire(x,y,key):
　　m=(x+y)//2
　　if key==a[m]:
　　　　return "M"
　　elif key　　　　return "R"+inquire(m+1,y,key)
　　else:
　　　　return "L"+inquire(x,m-1,key)
数组a的元素为[55,49,37,26,24,14,3,3,1],若执行语句h=inquire(0,8,14),则h的值是(　　)
A.LRM B.RLM
C.MRL D.MLR
1.定义如下函数:
def climb (n):
　　if n==0: return 1
　　if n<=2: return n
　　return climb(n-1)+climb(n-2)+climb(n-3)
执行语句m=climb(4)后,函数climb 被调用的次数(　　)
A.5 B.6
C.7 D.8
2.定义如下函数:
def f(n,c):
　　if n<=c:
　　　　return 1
　　else:
　　　　return f(n//c,c)+2*c
执行语句rt=f(17,2),函数f被调用的次数是(　　)
A.7 B.6
C.5 D.4
3.有如下Python程序:
def re(arr):
　　i=0
　　for j in range(1,len(arr)):
　　　　if arr[j]!=arr[i]:
　　　　　　i+=1
　　　　　　arr[i]=arr[j]
　　return i+1
print(arr[:re(arr)])
输入arr的值,运行程序,输出结果仍然存在重复元素的是(　　)
A.[8,9,9,9,8,8] B.[3,3,3,5,5,7]
C.[8,8,3,3,3,1] D.[2,2,8,8,6,6]
4.定义如下函数:
def g(n):
　　if n==0:
　　　　return 0
　　elif n % 2==0:
　　　　return 1+g(n//2)
　　else:
　　　　return g(n-1)
执行语句m=g(14)后,m的值为(　　)
A.3 B.4
C.5 D.6
5.某python程序段如下:
def ss(a,f):
　　if len(a)==1:
　　　　return a
　　elif f==True:
　　　　a=a[:len(a)-1]
　　else:
　　　　a=a[len(a)//2:]
　　f=not f
　　return ss(a,f)
print(ss([0,1,2,3,4,5,6,7,8,9],True))
执行程序后,输出结果为(　　)
A.[1] B.[8]
C.[4] D.[6]
6.定义如下函数:
def f(s,i):
　　n=len(s)
　　if i>=n//2:
　　　　return n % 2
　　if s[i]==s[n-i-1]:
　　　　return 2+f(s,i+1)
　　else:
　　　　return 0
函数调用f("racecar",0)的返回值是(　　)
A.3 B.4
C.7 D.1
7.定义如下函数:
def f(n):
　　if n<=1:
　　　　return 1
　　elif n%2==0:
　　　　return f(n-3)+1
　　return f(n-1)*2
执行语句s=f(6)后,s的值为(　　)
A.1 B.4
C.5 D.8
8.定义如下函数:
def peach(day):
　　if day==5:
　　　　num=1
　　else:
　　　　num=(peach(day+1)+1)*2
　　return num
print(peach(1))
执行该程序段后,输出的结果是(　　)
A.10 B.22
C.46 D.94
9.定义如下函数:
def f(s):
　　if len(s)==1:
　　　　return s
　　elif"0"<=s[0]<="9":
　　　　return s[0]+f(s[1:])
　　else:
　　　　return f(s[1:])+s[0]
执行语句print(f("1ab2"))后,输出结果为(　　)
A.12ba B.12ab
C.2lab D.2bal
10.有如下函数:
def f(m,n):
　　s=""
　　if m>1:
　　　　if m%n==0:
　　　　　　s=f(m//n,n)+str(n)
　　　　else:
　　　　　　s=f(m,n+1)
　　return s
执行语句k=f(45,2)后,k的值为(　　)
A."533" B."53"
C."35" D."335"
11.定义如下函数:
def f(n,k):
　　if n==k or k==0:
　　　　return 1
　　else:
　　　　return f(n-1,k)+f(n-1,k-1)
执行语句ans=f(5,3)后,ans的值为(　　)
A.2 B.8
C.10 D.20
12.定义如下函数:
def f(x):
　　if x==1:
　　　　return 1
　　else:
　　　　return (f(x-1)+1)*2
执行语句k=f(5)后,k的值为(　　)
A.46 B.22
C.10 D.4
13.有如下Python程序:
def fun(x):
　　if x==1:
　　　　return "1"
　　elif x%2==0:
　　　　return str(x)+'-'+fun(x//2)
　　else:
　　　　return str(x)+'-'+fun(x*3+1)
print(fun(5))
执行该程序后,输出的结果是(　　)
A.5-2-7-3-6-3-1 B.1-2-4-8-16-5
C.5-16-8-4-2-1 D.1-4-8-16-5
14.有如下Python程序:
def hill(n):
　　if n==1 or n==2:
　　　　return 1
　　elif n==3:
　　　　return 2
　　else:
　　　　return hill(n-1)+hill(n-3)
x=int(input())
print(hill(x))
执行该程序,若输入的值为7,输出的结果是(　　)
A.7 B.8
C.9 D.10
15.定义如下函数:
def f(x,y):
　　if x<=2 or y>20:
　　　　return x+y
　　return f(x-1,y+1)
执行语句k=f(5,1)后,k的值为(　　)
A.6 B.7
C.8 D.9
16.有如下Python程序段:
def peach(n):
　　if n==10:
　　　　return 1
　　else:
　　　　return (peach(n+1)+1)*2
print(peach(8))
执行该程序段后,输出的结果是(　　)
A.2 B.6
C.8 D.10
17.有如下两段Python程序:
def fact1(n): 　　s=0 　　while n!=0: 　　　　s+=n % 2 　　　　n=n//2 　　return s def fact2(n): 　　if n==1: 　　　　return 1 　　else: 　　　　return 　　　
对于任意正整数n(n>=2),两个函数的返回值相等,则方框处的代码是(　　)
A.n%2+fact2(n//2)
B.str(n%2)+fact2(n//2)
C.fact2(n%2)+str(n//2)
D.n//2+fact2(n%2)
18.某递归函数,功能是输入一个字符串s,输出其反序字符串。例如输入“hello”时,输出“olleh”。程序代码如下:
def reverse(s):
　　if len(s)<=1:
　　　　return s
　　return 　　　　　
划线处应填入的代码是(　　)
A.s[-1]+reverse(s[1:])
B.reverse(s[1:])+s[-1]
C.s[-1]+reverse(s[:-1])
D.reverse(s[:-1])+s[-1]
19.有如下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.①②③
20.有如下Python程序段:
import random
def bs(key,i,j):
　　m=(i+j)//2
　　v.append(a[m])
　　if a[m]==key or i>j:
　　　　return len(v)
　　elif a[m]>key:
　　　　return bs(key,i,m-1)
　　else:
　　　　return bs(key,m+1,j)
a=[2,4,7,11,13,16,20,25];v=[]
key=random.randint(1,9)*2+1
print(bs(key,0,len(a)-1))
执行该程序段后,输出的结果不可能是(　　)
A.1 B.2
C.3 D.4
21.小明编写程序实现数据升序功能,部分Python程序如下:
def bsort(arr):
　　if len(arr)==1:
　　　　return arr
　　for i in range(len(arr)-1):
　　　　if arr[i]>arr[i+1]:
　　　　　　arr[i],arr[i+1]=arr[i+1],arr[i]
　　return [arr[0]]+bsort(arr[1:])
此程序存在问题,适合作为测试数据的是(　　)
A.[4,6,5,4] B.[4,3,5,6]
C.[4,4,6,5] D.[5,6,4,7]5.1　递归算法思想
学习目标　
1.根据代码的运行次数与n的关系,掌握时间复杂度的计算方法。
2.掌握迭代算法的本质是每一次迭代得到的结果会作为下一次迭代的初始值。
3.掌握递归算法的本质通过重复将问题分解为同类的子问题而解决问题的方法。
　　　　　　 　　　　　 　　　　　
(2023年6月浙江省选考)定义如下函数:
def f(a,s):
　　if a>=s:
　　　　return a
　　else:
　　　　return f(a+1,s-a)
执行语句k=f(6,21)后,k的值为(　　)
A.6 B.7
C.8 D.9
答案　C
解析　本题考查递归函数的应用。递归算法包含递推和回归两部分,函数f(6,21)的值为f(7,15),而f(7,15)的值为f(8,8),函数f(8,8)的值为8,依次回归,最终函数的值为8。
　　一个算法中的语句执行次数称为语句频度或时间频度,算法中基本操作重复执行的次数是问题规模n的某个函数,记为T(n)。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。时间复杂度从小大到依次为常数阶、对数阶、线性阶、平方阶和指数阶。复杂问题的求解过程常常包含基本操作的多次重复进行,重复基本操作的常用方式有迭代和递归。迭代一般采用循环结构,通过某种递推式,不断更新变量新值,直到得到问题的解。递归则是算法中存在自调用,将大问题化为相同结构的小问题来求解,递归是一种有效的算法设计方法。
例1 定义如下函数:
def rf(n):
　　if n<3:
　　　　return n
　　return rf(n-1)+rf(n-3)
执行语句v=rf(5),函数rf被调用的次数是(　　)
A.11 B.5
C.7 D.15
思维点拨
明考向 本题考查递归算法思想
精点拨 当参数n大于等于3时,两次递归调用,否则直接返回值。①rf(5)=rf(4)+rf(2),调用rf函数2次;②rf(4)=rf(3)+rf(1),调用rf函数2次;③rf(3)=rf(2)+rf(0),调用rf函数2次;再加上v=rf(5)本身调用的一次,共7次
答案　C
变式1 有如下Python程序段:
def judge(s):
　　if len(s)==2:
　　　　return s[0]==s[1]
　　res=[];n=len(s)
　　for i in range(n-1):
　　　　r=(s[i]+s[i+1])%10
　　　　res.append(r)　#在res列表末尾添加一个元素r
　　return judge(res)
以下s执行judge(s)后,值为False的是(　　)
A.[2,3,6,9] B.[5,6,7,8]
C.[9,7,4,2] D.[3,9,0,2]
答案　B
解析　本题考查递归算法思想。该程序的功能是判断给定的数字列表经过反复将相邻两数之和取个位数(即模10)的操作,直到剩余两个数字时,这两个数字是否相等。B选项judge([5,6,7,8])返回值为judge([1,3,5]);judge([1,3,5])返回值为judge([4,8]),由于s[0]!=s[1],返回False。A选项返回值依次为judge([5,9,5])和judge([4,4])。C选项返回值依次为judge([6,1,6])和judge([7,7])。D选项返回值依次为judge([2,9,2])和judge([1,1])。
例2 对于任意非空字符串s,甲、乙程序段输出结果相同,则乙程序段加框处的正确代码为(　　)
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
思维点拨
明考向 本题考查递归和迭代的算法思想
精点拨 若s的值依次为"012345"和"01234",分别调用函数f,返回值均为"420",可见函数的功能是获取字符串s奇数位上的字符,并进行返回连接。乙程序中,变量i的值依次为0,2,4…,A选项当i为0时,s[n]越界。B选项若n的值为偶数,i为0时,应获取n-2位置上的字符。C选项将每次获取奇数位字符并按原来顺序进行连接。D选项用迭代算法思想来实现该递归算法
答案　D
变式2 甲、乙程序段的功能相同,则乙程序段加框处的正确代码为(　　)
a=1 b=1 m=int(input("请输入m的值:")) while a+b<=m: 　　c=a+b 　　a=b 　　b=c print(b) def f(a,b): 　　c=a+b 　　if c>m: 　　　　return b 　　else: 　　　　return 　　　　 m=int(input(“请输入m的值:”)) print(f(1,1))
甲程序段 乙程序段
A.f(b,c) B.f(a,b)
C.f(a,c) D.f(c,b)
答案　A
解析　本题考查递归和迭代的算法思想。程序的功能是求斐波纳契数列小于等于m的最后一项的值。在递归函数中,当c大于m时,返回b,因此当前的b和c依次送到函数的a和b中。
1.有如下Python程序段:
def f(n):
　　if n<=1:
　　　　return 1
　　else:
　　　　return f(n-1)+f(n-2)
print(f(3))
程序运行后,函数f被调用的次数是(　　)
A.5 B.4
C.3 D.2
答案　A
解析　f(3)的返回值为f(2)+f(1),而f(2)的返回值为f(1)+f(0),因此共调用了5次。
2.定义如下函数:
def quick(a):
　　if len(a)<=1:
　　　　return a
　　L="";M="";R=""
　　p=a[0]
　　for x in a:
　　　　if x　　　　　　L+=x
　　　　elif x==p:
　　　　　　M+=x
　　　　else:
　　　　　　R+=x
　　return quick(L)+M+quick(R)
若m="gibcb",执行语句st=quick(m),下列说法正确的是(　　)
A.该函数采用了迭代算法
B.程序实现对m中字符降序排序
C.函数quick被调用4次
D.加框处修改为p=a[-1],st结果不变
答案　D
解析　A选项该算法是递归算法。B选项把小于a[0]的值放在前面,大于a[0]的值放在后面,实现升序排列,st的结果为"bbcgi"。C选项第1次返回quick("bcb")+"g"+quick("i"),调用quick("bcb")返回quick("")+"bb"+quick("c"),因此共调用5次。D选项只是修改了p的初值,程序的功能不变,如调用程序,第1次返回quick("")+"bb"+quick("gil"),quick("gil")的值为quick("")+"c"+quick("gi"),quick("gi")的值为quick("gi")+"i"+quick("")最终st的结果为"bbcgi"。
3.定义如下函数:
def p(x,y):
　　if x%y==0:
　　　　print(y)
　　else:
　　　　p(y,x%y)
　　　　print(y)
执行语句p(64,18)后,依次输出的结果为(　　)
A.8,10,8,2 B.2,8,10,18
C.4,10,18 D.18,10,4
答案　B
解析　函数p(x,y)调用四次,依次是p(64,18),p(18,10),p(10,8),p(8,2)。函数每调用一次输出一个y值,输出的顺序跟调用函数的顺序是逆序的,即先输出p(8,2)时的y值2,然后依次是8,10,18。画出递推公式如图所示,回归后得到答案B。
4.定义如下函数:
def f(a,n,m):
　　if n==0:
　　　　return m
　　elif a[n-1]　　　　return f(a,n-1,m)
　　else:
　　　　return f(a,n-1,a[n-1])
若a的值为[13,83,57,85,78,74,44,80],执行语句k=f(a,len(a),0)后,k的值为(　　)
A.13 B.44
C.80 D.85
答案　D
解析　函数的功能求数组a的最大值。f(a,len(a),0)返回值为f(a,7,80),由于44,74,78均比80小,依此类推,当n的值为4时,返回值为f(a,3,85),剩余的数均小于85。
5.有如下Python程序段
def code(t):
　　if len(t)==0:
　　　　return ""
　　k=int(t[0])
　　return code(t[1:])+str((k+3)%8)
s=input("输入原始数据:")
answer=code(s)
print("加密结果为:",answer)
若最终输出的加密结果为2174,则输入的原始数据是(　　)
A.7641 B.1467
C.5427 D.7245
答案　B
解析　程序的功能是将字符串的第1个数字进行加3模8操作,并进行反向连接。2174各个数字在加3模8前依次为7641,对该字符串进行反向可得加密前为1467。
6.有如下Python代码段:
from random import randint
def f(lst,x):
　　if len(lst)==0:
　　　　return []
　　if lst[0]%x!=0:
　　　　return [lst[0]]+f(lst[1:],x)
　　else:
　　　　return f(lst[1:],x)
a=[5,8,7,12,10,3]
t=randint(3,5)
a=f(a,t)
运行程序后,a的值不可能是(　　)
A.[5,8,7,10] B.[8,7,12,3]
C.[8,7,10,3] D.[5,7,10,3]
答案　C
解析　程序的功能是去除列表中能被x 整除的元素。t的值可能是3,4,5。A选项去除被3 整除的元素。B选项去除被5 整除的元素。D选项去除被3 整除的元素。C选项中包含3,4,5的倍数。
7.定义如下Python函数:
def f(m,n):
　　if m>=n:
　　　　return m
　　else:
　　　　return f(m+m%2+1,n-1)+1
执行语句k=f(6,12)后,k的值为(　　)
A.11 B.12
C.13 D.14
答案　D
解析　函数调用过程如下:f(6,12)=f(7,11)+1=(f(9,10)+1)+1=((f(11,9)+1)+1)+1=11+1+1+1=14。
8.定义如下函数:
def chg(k):
　　if k==-1:
　　　　return ""
　　else:
　　　　c=chr(ord("a")+k)
　　　　if k%2==1:
　　　　　　return c+chg(k-1)
　　　　else:
　　　　　　return chg(k-1)+c
执行语句m=chg(4)后,m的值为(　　)
A."ecabd" B."dbace"
C."abcde" D."edcba"
答案　B
解析　依次调用函数时,k的值为4,3,2,1,0,因此对应的字母c依次为edcba。chg(4)=chg(3)+"e";chg(3)="d"+ chg(2);chg(2)=chg(1)+"c";chg(1)="b"+ chg(0);chg(0)=chg(-1)+"a",依次进行回归,chg(1)="ba",chg(2)="bac",chg(3)="dbac",chg(4)="dbace"。
9.定义如下函数:
def f(s):
　　if len(s)==1:
　　　　return s[0]
　　elif len(s)==2:
　　　　return s[0]+s[1]
　　else:
　　　　return f(s[0:len(s)//3])+f(s[len(s)//3:len(s)])
执行语句s=f([1,2,3,4,5,6]),函数f被调用的次数是(　　)
A.3 B.5
C.7 D.15
答案　C
解析　s的长度为6,f(s)返回f([1,2])+f([3,4,5,6]),调用2次,函数f([1,2])值为3,调用1次。f([[3,4,5,6]])返回f([[3,4])+ f([[5,6]]),调用2次。f([[3,4])和f([[5,6]])各调用1次,共调用7次。
10.定义如下函数:有如下Python程序段:
def fab(a,b):
　　if a%b==0:
　　　　return b
　　elif a>b:
　　　　return fab(a-b,b)
　　else:
　　　　return fab(a,b-a)
print(fab(8,4)-fab(4,8))
程序运行后,输出的结果为(　　)
A.0 B.2
C.4 D.8
答案　A
解析　程序的功能是辗转相除法计算两个非负整数的最大公约数。函数fab(4,8)返回fab(4,4),函数fab(4,4)返回4。函数fab(8,4)返回4。
11.有如下Python自定义函数:
def fun(x,i):
　　if x　　　　return i
　　elif x%i==0:
　　　　return x
　　else:
　　　　return fun(x-i,i+1)
执行语句k=fun(37,3)后,k的值为(　　)
A.5 B.6
C.30 D.34
答案　C
解析　函数fun(34,4)=fun(30,5),而30%5的值为0,因此返回30。
12.定义如下函数:
def f(s,r):
　　if s-r**2<0 or r==0:
　　　　return r+1
　　else:
　　　　return f(s-r**2,r-1)
执行语句k=f(50,5)后,k的值为(　　)
A.4 B.3
C.2 D.1
答案　B
解析　分析程序段可知,函数f(s,r)为递归函数,因此 f(50,5)=f(25,4)=f(9,3)=f(0,2)=3。
13.对于任意非空的列表a,甲、乙程序段输出结果相同,则乙程序段加框处的代码为(　　)
甲: a=[3,2,-2,-3,5] tot=0 for i in range(len(a)): 　　if a[i]>0: 　　　　tot+=a[i] print(tot) 乙: def find(a,i): 　　if i==len(a): 　　　　return 0 　　cur=a[i] 　　if cur<0: 　　　　cur=0 　　return cur+ 　　　　 print(find(a,0))
A.find(a,len(a)-i)
B.find(a,len(a)-1-i)
C.find(a,i+1)
D.find(a,i-1)
答案　C
解析　甲程序段功能为统计a中所有大于0的元素之和。乙程序采用递归实现,先考虑递归边界,即if i==len(a)和调用函数是i的初值为0,确定递推过程中,i是递增的(其实从这里及已经把C选出来了),在看到当没有到达边界条件时,通过cur<0的判断将小于0的值全改为0,使最后的结果与甲程序保持一致。
14.定义如下递归函数,计算正整数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)
则(1)(2)(3)处代码依次为(　　)
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。题目代码写得比较细碎,④y+f(n-1)首先可以排除,根据③y+f(x),可以分析得出y=n%10,x=n//10。
15.定义函数isPalidrome用于判断回文字符串:
def isPalidrome(s):
　　if len(s)<=1:
　　　　return True
　　elif s[0]!=s[len(s)-1]:
　　　　return False
　　else:
　　　　return 　　　　　
已知代码划线处可选语句为:
①isPalidrome(s[1:-1])
②isPalidrome(s[2:-1])
③isPalidrome(s[1:len(s)-1])
④isPalidrome(s[2:len(s)-1]),则可填入的语句是(　　)
A.②或③ B.③或④
C.①或② D.①或③
答案　D
解析　本题考查自定义函数及递归函数。递归函数实现判断首尾字符是否相同,若相同,再去除首尾字符调用自身,递归的出口是当去除后的字符长度为0或1时,说明所有的字符是相同的。
16.定义如下函数:
def search(lst,i,j,key):
　　if i>j:
　　　　return -1
　　m=(i+j)//2
　　if lst[m]>key:
　　　　return search(lst,i,m-1,key)
　　elif lst[m]　　　　return search(lst,m+1,j,key)
　　else:
　　　　return m
若列表lst为[12,31,47,50,55,55,71,76],执行语句search(lst,0,7,51),该函数被调用的次数为(　　)
A.1 B.2
C.3 D.4
答案　D
解析　采用递归思想编写二分查找的算法。分别调用函数search(lst,0,7,51),search(lst,4,7,51),search(lst,4,5,51),search(lst,5,4,51),最后得到结果为-1。
17.定义如下函数:
def inquire(x,y,key):
　　m=(x+y)//2
　　if key==a[m]:
　　　　return "M"
　　elif key　　　　return "R"+inquire(m+1,y,key)
　　else:
　　　　return "L"+inquire(x,m-1,key)
数组a的元素为[55,49,37,26,24,14,3,3,1],若执行语句h=inquire(0,8,14),则h的值是(　　)
A.LRM B.RLM
C.MRL D.MLR
答案　B
解析　程序的功能采用二分查找法查找14的过程。依次查找的数据为24,3和14,因此先向右查找,再向左查找,最后一次找到。
1.定义如下函数:
def climb (n):
　　if n==0: return 1
　　if n<=2: return n
　　return climb(n-1)+climb(n-2)+climb(n-3)
执行语句m=climb(4)后,函数climb 被调用的次数(　　)
A.5 B.6
C.7 D.8
答案　C
解析　函数climb(4)返回值climb(3)+climb(2)+climb(1),函数climb(3)返回值climb(2)+climb(1)+climb(0),计算climb(3)本身调用了1次函数,内部调用了3次函数,共计4次。计算climb(4)需调用1次,climb(3)+climb(2)+climb(1)调用次数为4+1+1,合计7次。
2.定义如下函数:
def f(n,c):
　　if n<=c:
　　　　return 1
　　else:
　　　　return f(n//c,c)+2*c
执行语句rt=f(17,2),函数f被调用的次数是(　　)
A.7 B.6
C.5 D.4
答案　D
解析　根据递推公式,f(17,2)→f(8,2)+2*2,f(8,2)→f(4,2)+2*2,f(4,2)→f(2,2)+2*2,而f(2,2)的值为1,因此共调用函数4次。
3.有如下Python程序:
def re(arr):
　　i=0
　　for j in range(1,len(arr)):
　　　　if arr[j]!=arr[i]:
　　　　　　i+=1
　　　　　　arr[i]=arr[j]
　　return i+1
print(arr[:re(arr)])
输入arr的值,运行程序,输出结果仍然存在重复元素的是(　　)
A.[8,9,9,9,8,8] B.[3,3,3,5,5,7]
C.[8,8,3,3,3,1] D.[2,2,8,8,6,6]
答案　A
解析　程序的功能实现对数组进行去重处理,当后一项和当前项不同,当前项向前移动一个,并将不同内容往前移动到当前位置。再去寻找当前项不同并后移,直到遍历到最后一项为止。A选项的结果为[8,9,8],B选项最终结果为[3,5,7],C选项的最终结果为[8,3,1],D选项最终结果为[2,8,6]。
4.定义如下函数:
def g(n):
　　if n==0:
　　　　return 0
　　elif n % 2==0:
　　　　return 1+g(n//2)
　　else:
　　　　return g(n-1)
执行语句m=g(14)后,m的值为(　　)
A.3 B.4
C.5 D.6
答案　A
解析　根据递归的过程,得到递推公式g(14)→return 1+g(14//2)→return g(7-1)→return 1+g(6//2)→return g(3-1)→return 1+g(2//2)→return g(1-1)→return 0。回归得到答案为3。
5.某python程序段如下:
def ss(a,f):
　　if len(a)==1:
　　　　return a
　　elif f==True:
　　　　a=a[:len(a)-1]
　　else:
　　　　a=a[len(a)//2:]
　　f=not f
　　return ss(a,f)
print(ss([0,1,2,3,4,5,6,7,8,9],True))
执行程序后,输出结果为(　　)
A.[1] B.[8]
C.[4] D.[6]
答案　D
解析　每次调用变量a的值依次为[0,1,2,3,4,5,6,7,8,9]、[0,1,2,3,4,5,6,7,8]、[4,5,6,7,8]、[4,5,6,7]、[6,7]、[6],最终得到答案D。
6.定义如下函数:
def f(s,i):
　　n=len(s)
　　if i>=n//2:
　　　　return n % 2
　　if s[i]==s[n-i-1]:
　　　　return 2+f(s,i+1)
　　else:
　　　　return 0
函数调用f("racecar",0)的返回值是(　　)
A.3 B.4
C.7 D.1
答案　C
解析　函数调用过程如下: f("racecar",0)=2+f("racecar",1),f("racecar",1)=2+f("racecar",2),f("racecar",2)=2+f("racecar",3)=3,回归得到f("racecar",1)=5,f("racecar",0)=7。
7.定义如下函数:
def f(n):
　　if n<=1:
　　　　return 1
　　elif n%2==0:
　　　　return f(n-3)+1
　　return f(n-1)*2
执行语句s=f(6)后,s的值为(　　)
A.1 B.4
C.5 D.8
答案　C
解析　画出递推过程如图所示,则回归可得f(2)=2,f(3)=4,f(6)=f(3)+1=5。
8.定义如下函数:
def peach(day):
　　if day==5:
　　　　num=1
　　else:
　　　　num=(peach(day+1)+1)*2
　　return num
print(peach(1))
执行该程序段后,输出的结果是(　　)
A.10 B.22
C.46 D.94
答案　C
解析　peach(1)返回值为(peach(2)+1)*2,peach(2)返回值为(peach(3)+1)*2,peach(3)返回值为(peach(4)+1)*2,peach(4)返回值为(peach(5)+1)*2,peach(5)返回值为1,再进行回归,peach(4)值为4,peach(3)值为10,peach(2)值为22,peach(1)值为46。
9.定义如下函数:
def f(s):
　　if len(s)==1:
　　　　return s
　　elif"0"<=s[0]<="9":
　　　　return s[0]+f(s[1:])
　　else:
　　　　return f(s[1:])+s[0]
执行语句print(f("1ab2"))后,输出结果为(　　)
A.12ba B.12ab
C.2lab D.2bal
答案　A
解析　f("1ab2")返回"1"+ f("ab2"),而f("ab2")的返回值为f("b2")+"a"。而f("b2")的返回值为"2"+f("b")。回归后,f("b2")值为"2b",f("ab2")值为"2ba",最终函数的值为"12ba"。
10.有如下函数:
def f(m,n):
　　s=""
　　if m>1:
　　　　if m%n==0:
　　　　　　s=f(m//n,n)+str(n)
　　　　else:
　　　　　　s=f(m,n+1)
　　return s
执行语句k=f(45,2)后,k的值为(　　)
A."533" B."53"
C."35" D."335"
答案　A
解析　本题考查递归算法思想。函数f(45,2)返回值为f(45,3);函数f(45,3)返回值为f(15,3)+"3";函数f(15,3)返回值为f(5,3)+"3";函数f(5,3)返回值为f(5,4);函数f(5,4)返回值为f(5,5);函数f(5,5)返回值为f(1,5)+"5"。递推的过程如图所示,得到回归结果为"533"。
11.定义如下函数:
def f(n,k):
　　if n==k or k==0:
　　　　return 1
　　else:
　　　　return f(n-1,k)+f(n-1,k-1)
执行语句ans=f(5,3)后,ans的值为(　　)
A.2 B.8
C.10 D.20
答案　C
解析　函数f(5,3)的值为f(4,3)+f(4,2),函数f(4,3)的值为f(3,3)+f(3,2),函数f(3,3)的值1,函数f(3,2)的值为f(2,2)+f(2,1),函数f(2,2)的值为1,函数f(2,1)的值为f(1,1)+f(1,0)=2,函数f(1,1)和函数f(1,0)的值均为1。可得函数f(4,3)的值为4。函数f(4,2)的值为f(3,2)+f(3,1),函数f(3,2)的值为f(2,2)+f(2,1)=1+2=3。函数f(3,1)的值为f(2,1)+f(2,0)=3。可得函数f(4,3)的值为6,而f(4,3)+f(4,2)的值为10。
12.定义如下函数:
def f(x):
　　if x==1:
　　　　return 1
　　else:
　　　　return (f(x-1)+1)*2
执行语句k=f(5)后,k的值为(　　)
A.46 B.22
C.10 D.4
答案　A
解析　函数f(5)的值为(f(4)+1)*2,函数f(4)的值为(f(3)+1)*2,函数f(3)的值为(f(2)+1)*2,函数f(2)的值为(f(1)+1)*2=4。回归可得f(3)=10,f(4)=22,f(5)=46。
13.有如下Python程序:
def fun(x):
　　if x==1:
　　　　return "1"
　　elif x%2==0:
　　　　return str(x)+'-'+fun(x//2)
　　else:
　　　　return str(x)+'-'+fun(x*3+1)
print(fun(5))
执行该程序后,输出的结果是(　　)
A.5-2-7-3-6-3-1 B.1-2-4-8-16-5
C.5-16-8-4-2-1 D.1-4-8-16-5
答案　C
解析　程序的功能是将一个数n转换成1的过程,若n为偶数,n更新为x//2,否则更新为x*3+1,直到n的值为1。
14.有如下Python程序:
def hill(n):
　　if n==1 or n==2:
　　　　return 1
　　elif n==3:
　　　　return 2
　　else:
　　　　return hill(n-1)+hill(n-3)
x=int(input())
print(hill(x))
执行该程序,若输入的值为7,输出的结果是(　　)
A.7 B.8
C.9 D.10
答案　C
解析　函数hill(7)返回值为hill(6)+hill(4);函数hill(6)返回值为hill(5)+hill(3);函数hill(5)返回值为hill(4)+hill(2);函数hill(4)返回值为hill(3)+hill(1);因此hill(4)=3,hill(5)=4,hill(6)=6,hill(7)=9。
15.定义如下函数:
def f(x,y):
　　if x<=2 or y>20:
　　　　return x+y
　　return f(x-1,y+1)
执行语句k=f(5,1)后,k的值为(　　)
A.6 B.7
C.8 D.9
答案　A
解析　f(5,1)=f(4,2)=f(3,3)=f(2,4)=2+4=6。
16.有如下Python程序段:
def peach(n):
　　if n==10:
　　　　return 1
　　else:
　　　　return (peach(n+1)+1)*2
print(peach(8))
执行该程序段后,输出的结果是(　　)
A.2 B.6
C.8 D.10
答案　D
解析　本题考查递归函数应用。peach(8)=(peach(9)+1)*2　peach(9)=(peach(10)+1)*2=4,因此peach(8)的值为10。
17.有如下两段Python程序:
def fact1(n): 　　s=0 　　while n!=0: 　　　　s+=n % 2 　　　　n=n//2 　　return s def fact2(n): 　　if n==1: 　　　　return 1 　　else: 　　　　return 　　　
对于任意正整数n(n>=2),两个函数的返回值相等,则方框处的代码是(　　)
A.n%2+fact2(n//2)
B.str(n%2)+fact2(n//2)
C.fact2(n%2)+str(n//2)
D.n//2+fact2(n%2)
答案　A
解析　程序的功能将十进制数n转换为二进制数的各个位上数字之和,输出的结果为数值类型。右侧每次调用函数产生的余数是n%2,后续剩余元素继续递归部分是fact2(n//2),由于结果为求和,所以两项不需要注意前后关系。
18.某递归函数,功能是输入一个字符串s,输出其反序字符串。例如输入“hello”时,输出“olleh”。程序代码如下:
def reverse(s):
　　if len(s)<=1:
　　　　return s
　　return 　　　　　
划线处应填入的代码是(　　)
A.s[-1]+reverse(s[1:])
B.reverse(s[1:])+s[-1]
C.s[-1]+reverse(s[:-1])
D.reverse(s[:-1])+s[-1]
答案　C
解析　表达式s[-1]指字符串s最后一个字符,s[:-1]指字符串s去除最后一个字符。每次递归需将后面的字符放在前面。
19.有如下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
解析　本题考查递归算法。用2至x-1之间的数y去检测能否被x整除。若条件y>int(sqrt(x))+1成立,表示完成所有数检测,返回True;若能够除通返回False;否则将y加1,调用自身函数再次进行检测。
20.有如下Python程序段:
import random
def bs(key,i,j):
　　m=(i+j)//2
　　v.append(a[m])
　　if a[m]==key or i>j:
　　　　return len(v)
　　elif a[m]>key:
　　　　return bs(key,i,m-1)
　　else:
　　　　return bs(key,m+1,j)
a=[2,4,7,11,13,16,20,25];v=[]
key=random.randint(1,9)*2+1
print(bs(key,0,len(a)-1))
执行该程序段后,输出的结果不可能是(　　)
A.1 B.2
C.3 D.4
答案　B
解析　查找的是3至19之间的奇数,第2次分别查找4和16,因此不可能是2次。当查找的数据不存在时,调用函数比查找次数多一次。
21.小明编写程序实现数据升序功能,部分Python程序如下:
def bsort(arr):
　　if len(arr)==1:
　　　　return arr
　　for i in range(len(arr)-1):
　　　　if arr[i]>arr[i+1]:
　　　　　　arr[i],arr[i+1]=arr[i+1],arr[i]
　　return [arr[0]]+bsort(arr[1:])
此程序存在问题,适合作为测试数据的是(　　)
A.[4,6,5,4] B.[4,3,5,6]
C.[4,4,6,5] D.[5,6,4,7]
答案　D
解析　采用递归调用进行冒泡排序,每一轮从前往后排只能保证最后一个元素有序,但是它把第一个元素切出来当成已经有序元素,是该程序存在的问题。最后一条语句可以改成return bsort([arr[:-1])+[arr[-1]]就可以实现排序了。D选项第一轮排序完成数组为:[5,4,6,7],然后把5取出后面[4,6,7]再递归调用排序,5不是这个序列中的最小值,故不能实现完全排序。其他ABC选项,每一轮切出来都是本轮中已经有序的值,能够实现排序。

展开更多......

收起↑