资源简介

专题五　检测卷
一、选择题(本大题共10小题,每小题2分,共20分。每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)
1.下列有关迭代算法和递归算法的描述,正确的是(　　)
A.迭代算法和递归算法本质上没有什么区别
B.递归中一定有迭代,迭代中也一定有递归
C.通常情况下,迭代算法和递归算法可以相互转换
D.迭代算法效率较低,而递归算法效率较高
2.小王设计了一个算法求3n的值,算法思想是:先把3n转换为3*3n-1,而3n-1又可以转换为3*3n-1-1,如此继续,直到3*30,已知30=1,然后通过30的值又可以求出31的值,如此继续,最终求出了3n的值。小杰采用的算法是(　　)
A.迭代算法 B.递归算法 C.枚举算法 D.解析算法
3.递归过程的实现过程分为两个阶段,分别是(　　)
A.枚举和回归 B.递推和回归 C.递推和递归 D.试探和回归
4.递归算法的函数调用时,处理参数和返回地址通常使用的数据结构是(　　)
A.数组 B.队列 C.栈 D.链表
5.下列Python程序的功能是使用迭代算法求s的值。
n=int(input("n="))
s=1
for i in range(1,n,3):
　 s=s+i
print("s=",s)
程序执行时,输入n的值为20,则输出的结果为(　　)
A.s=51 B.s=70 C.s=71 D.s=93
6.有如下Python程序:
def fx(x):
　if x<=1:
　　　return 1
　 else:
　　　return 2+fx(x-1)
n=int(input("n="))
print(fx(n))
程序运行时,输入n的值为10,则输出的结果为(　　)
A.17 B.18 C.19 D.21
7.有如下Python程序段:
n=int(input("n="))
a,b=1,1
for i in range(1,n):
　 c=a+b
　 a=2*a
　 b=2*b
print(c)
程序执行时,输入n的值为5,则输出的结果为(　　)
A.12 B.20 C.16 D.45
8.执行如下 Python 程序,输出结果为(　　)
def f(s,i):
if i+2 >len(s):
return s
if s[i]==s[i+1]:
s=s[:i]+s[i+2:]
return f(s,max(i-1,0))　　#max(a,b)返回a和b中的较大值
return f(s,i+1)
s="PPTTPAPPTATAAT"
print(f(s,2))
A.PATATT B.PPPATA C.PATA D.PTA
9.对于任意非空字符串s,若甲、乙两个程序段输出结果相同,则乙程序段划线处的正确代码是(　　)
def f(s,t) : if t < 0: return "" return s[t]+f(s,t-2) print(f(s,len(s)-1)) r="" n=len(s) for i in range(n-1,-1,-2) : 　　　　　　　 print(r)
甲程序段 乙程序段
A.r=s[i]+r B.r+=s[i]
C.r=r+s[n-i-1] D.r=s[n-i-1]+r
10.下列Python程序功能是:输入n的值(n≥5),用迭代法求1+(1*2)+(1*2*3)+…+(1*2*…*n)的值。程序运行效果界面如下图所示。
Please input n︰10
1+(1*2)+(1*2*3)+…+(1*2*…*10)=4037913
n=int(input("Please input n:"))
s1=1
s2=0
i=1
while 　　①　　:
　　s1=s1*i
　　　　　②　
　　i+=1
print("1+(1*2)+(1*2*3)+…+(1*2*…*n)","=",s2)
为实现上述功能,程序划线①②处应填入的代码为(　　)
A.①iC.①i<=n　　②s1=s2+s1 D.①i<=n　　②s2=s2+s1
二、非选择题(本大题共3小题,其中第11小题9分,第12小题12分,第13小题9分,共30分)
11.走楼梯。楼梯共有N阶台阶,上楼可以一步上一个台阶,也可以一步上二个台阶,还可以一步上三个台阶。编写Python程序,实现如下功能:输入台阶数,计算走到第N阶台阶的方法数。程序运行界面如下图所示。
请输入台阶数:8
共有走法数为:81
实现上述功能的程序如下,请回答下列问题:
(1)若台阶数为4,则到第4阶台阶的走法共有　　　　种。(3分)
(2)请在程序划线处填入合适的代码。
def fx(n):
　if n==1 or n==2:
　　　return n
　 elif n==3:
　　　return 4
　 elif n>3:
　　　return　　①　
k=int(input('请输入台阶数:'))
　　②　
print('共有走法数为:',ans)
程序划线①处应填入的代码为:　　　　　　　　　　　　　;(3分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　。(3分)
12.科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很强。每对成虫过x(1≤x≤20)个月产y(1≤y≤20)对卵,每对卵要过两个月长成成虫。假设每个成虫不死,第一个月只有一对成虫,且卵长成成虫后的第一个月不产卵(过x个月产卵),求过z(x≤z≤50)个月以后,共有成虫的对数。
程序运行时,输入x、y、z的值,输出过z个月后的成虫对数。程序运行界面如下图所示。
请输入x的值:2
请输入y的值:3
请输入z的值:10
z个月后的成虫对数为:76
实现上述功能的Python程序如下,请回答下列问题。
(1)输入x、y、z的值分别为1,2,8,则过z个月后的成虫对数为　　　　。(3分)
(2)请在程序划线处填入合适的代码。
x=int(input('请输入x的值:'))
y=int(input('请输入y的值:'))
z=int(input('请输入z的值:'))
a=[0]*51
b=[0]*51
for i in range(　　①　　):
　 a[i]=1
for i in range(x,z+1):
　 a[i]=a[i-1]+b[i-2]
　 　　②　　
print('z个月后的成虫对数为:'+　　③　　))
程序划线①处应填入的代码为:　　　　　　　　　　　　　　　　　;(3分)
程序划线②处应填入的代码为:　　　　　　　　　　　　　　　　　;(3分)
程序划线③处应填入的代码为:　　　　　　　　　　　　　　　　　。(3分)
13.下面程序的功能是用类构建二叉树,并进行二叉树的遍历。方框中的程序功能是对二叉树进行中序遍历,请在方框中填入合适的代码。
class Node:
　 def_init_(self, value=None,left=None,right=None):
　　　 self.value=value　#值
　　　 self.left=left　　#左节点
　　　 self.right=right　#右节点
def preTraverse(root):　#前序遍历
　　if root==None:
　　　 return
　　print(root.value)
　　preTraverse(root.left)
　　preTraverse(root.right)
def midTraverse(root):　#中序遍历
(9分)
if_name_=='_main_':
　　root=Node(…)
　　print('前序遍历序列为:')
　　preTraverse(root)
　　print('中序遍历序列为:')
　　midTraverse(root)
专题五　检测卷
一、选择题
1.C　解析:迭代算法和递归算法是两种不同的算法,因此A选项错误;递归中一定有迭代,但迭代中不一定有递归,因此B选项错误;迭代算法效率较高,而递归算法比较占用空间,程序运行效率较低,因此D选项错误;一般情况下,迭代算法和递归算法是可以相互转换的,因此答案为C。
2.B　
3.B　解析:本题主要考查的是递归算法的执行过程。递归算法的执行过程分为两个阶段:递推和回归。在递推阶段,把较复杂的问题的求解递推到一些简单的问题的求解;在回归阶段,当获得简单问题的解后,逐级返回依次得到复杂问题的解。因此答案为B。
4.C　
5.C　解析:本题程序的功能是求s=1+1+4+7+10+13+16+19的和,因此最后输出的结果为s=71,答案为C。
6.C　解析:本题采用递归算法求fx(10)的值,fx(10)=2*9+1=19,因此答案为C。
7.C　
8.C　解析:本题主要考查的是递归算法。递归终止条件为i+2 > len(s),即i指向最后一个字符,递归终止,返回当前s;当s[i] == s[i+1],删除相同的二个相邻字符,同时i前移一位,继续处理(如果i出了边界,回到字符开始)。否则i后移一位,继续处理。此函数的作用是将字符串中相邻相同的字符串删除。将s如上处理,最后输出的结果是PATA,因此答案为C。
9.B　解析:本题主要考查字符串递归与循环等价实现。甲程序为递归函数,从字符串末尾开始,每隔一个字符向前拼接字符,即输出奇数长度字符串的倒序奇数位字符,如 s = "abcdef" 时输出 fdb。其递归逻辑为:从 s[len(s)-1] 开始,每次减 2 索引拼接。乙程序为循环实现,从 i = n-1 开始,步长为 -2,依次访问 s[i],按访问顺序拼接至结果字符串 r 中。为了与甲程序相同,字符应按访问顺序拼接,即使用 r += s[i],对应B选项;A 选项会导致字符逆序拼接;C 选项和 D选项中,s[n-i-1]是错误的索引表达,与i无关,均不符合题意。故答案为B。
10.D　解析:本题主要考查迭代算法的应用。循环变量i的初值为1,终值为n,因此①处的while条件为i<=n,s1为1*2*…*i的积,s2通过不断更新s1的值来更新自己,因此②处的代码为s2=s2+s1,故答案为D。
二、非选择题
11.(1)7　(2)①fx(n-1)+fx(n-2)+fx(n-3)　　②ans=fx(k)
解析:(1)有4个台阶时的走法有:1+1+1+1,1+2+1,1+1+2,2+1+1,2+2,1+3,3+1,共7种,因此答案为7。
(2)当只有1或2个台阶时,走法数为台阶数,当n=3时,共有4种走法,分别为:1+1+1,1+2,2+1,3,当有n(n>3)个台阶时,走法为走到第n个台阶的前一步的位置的各走法之和,走到第n个台阶的前一步的位置有:n-1或n-2或n-3,因此①处代码为fx(n-1)+fx(n-2)+fx(n-3);根据语句“print('共有走法数为:',ans)”,可知走法总数为ans,因此②处代码为ans=fx(k)。
12.(1)37　(2)①0,x 或x　② b[i]=y*a[i-x]　③str(a[z])
解析:(1)根据题意,可推算得到答案为37。(2)a[i]表示第i月的成虫数目,每对卵要过x个月长成成虫,使用数组b存储卵的数目,即b[i]表示第i月的卵的数目,因此可得:b[i]=y*a[i-x],a[i]=a[i-1]+b[i-2]。在计算成虫对数之前,需对前x个月的成虫数目(a[0] ~ a[x-1])初始化为1,因此程序①处代码为0,x或x;因为每对成虫过x个月产y对卵,因此第i个月的卵的数目b[i]= y*a[i-x],故程序②处代码为b[i]=y*a[i-x];要求过z个月以后成虫对数,也就是第z+1个月的成虫对数,a[0]表示第1个月,因此第z+1个月的成虫对数为a[z],字符串“+”运算时,需将a[z]转换为字符串型,故程序③处代码为str(a[z])。
13.if root==None··
　 return
midTraverse(root.left)
print(root.value)
midTraverse(root.right)
解析:本题主要考查的是二叉树构建和遍历的程序实现。观察前序遍历程序代码可知,先输出根节点,然后访问左子树和右子树。因此,中序遍历应先访问左子树,然后输出根节点,最后访问右子树,对左右子树也使用同样的方法,实现的算法是递归算法。

展开更多......

收起↑