资源简介

专题16　算法思想
知识点　递归算法
1.斐波那契数列：1，1，2，3，5，8，13，…现用递归算法求解第n项，代码如下：
def fib(n)：
if (n> 2)：
return fib(n－ 1)＋ fib(n－2)
return 1
n＝int(input('输入一个整数'))
print(fib(n))
程序执行时，输入一个整数5，则函数fib被第3次调用时的返回值为(　　)
A.2 B.3
C.5 D.8
2.阅读以下程序：
def f(x)：
if x>5 or x<1：
return '无法计算'
elif x＝＝5：
return 1
else：
return (f(x＋1)＋1)*2
若输入的x为2，则函数返回值为(　　)
A.22 B.10
C.11 D.'无法计算'
3.有如下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.①②③
4.运行下列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
5.有两个自定义函数如下：
def p1(a，b)： if b＝＝0： return 1 if b%2＝＝0： return p1(a，b//2)*p1(a，b//2) else： return a*p1(a，b－1)
def p2(a，b)： if b＝＝0： return 1 return a*p2(a，b－1)
下列说法不正确的是(　　)
A.p2(2，3)的返回值为 8
B.函数p2的时间复杂度是O(n)
C.函数p1和函数p2均采用了递归算法
D.计算p1(2，3)，函数p1的调用次数为4
6.有如下Python代码：
def f(num)：
for i in range(2，int (num**0.5)＋1)：
if num%i＝＝0：
　　 　　return str(f(num//i))＋″*″＋str(i)
return num
n＝int(input(″输入n：″))
print(f(n))
程序运行后，输出的结果不可能是(　　)
A.2 B.3
C.2*2 D.2*3
7.定义如下Python函数；
def fn(n)：
if n＝＝0：
return n
else：
return n%10＋fn(n//10)
print(fn(2023))
运行程序，输出的结果是(　　)
A.5 B.6
C.7 D.8
8.有如下Python程序段：
def f(n)：
if n<2：
return 0
elif n % 2＝＝0：
return n＋f(n－2)
else：
return f(n－1)
n＝int(input())
print(f(n))
若输入 n 的值为 101，则程序运行后，输出的内容为(　　)
A.100 B.2500
C.2550 D.5050
9.定义如下函数：
def myfun(a，s)：
if a*2>＝s：
return a
else：
return myfun(a＋3，s－2)
执行语句n＝myfun(4，18)后，n的值为(　　)
A.4 B.7
C.10 D.13
10.执行下列Python代码，输出结果为(　　)
def f(s)：
m＝len(s)
if m＝＝1：
return int(s)
else：
return f(s[：m－1])＋f(s[m－1])
print(f('101'))
A.11 B.2
C.5 D.101
11.有如下Python程序段：
def fun(k)：
if k＝＝0：
return ″″
elif k%2＝＝1：
return chr(k＋ord('A'))＋fun(k－1)
else：
return fun(k－1)＋chr(k＋ord('A'))
有关该程序段，下列说法正确的是(　　)
A.fun(5)的值为″FDBCE″
B.若执行 s＝fun(0)，则函数 fun 的调用次数为 0
C.该算法的时间复杂度为 O(n2)
D.计算机在执行上述递归程序时，是通过树的调用来实现的
12.有如下Python函数：
def trans(num，n)：
s＝″0123456789ABCDEF″
if numreturn s[num]
else：
return trans(num//n，n)＋s[num%n]
执行语句 a＝trans(394，16)后，a 的值为(　　)
A.9A B.1810
C.180 D.18A
13.有如下Python程序段：
def tra(head，a)：
if head＝＝－1：
return
tra(a[head][1]，a)
print(a[head][0]，end＝″ ″)
a＝[[″A″，3]，[″C″，2]，[″D″，4]，[″B″，1]，[″E″，－1]]
head＝0
tra(head，a)
运行该程序段后，输出的结果是(　　)
A.E D C B A B.A B C D E
C.E B D C A D.A C D B E
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”，该程序功能不变
15.有如下程序段：
def bubbleSort(n)：
if n＝＝1：
return
for i in range(n－1)：
if arr[i]>arr[i＋1]：
　　 　　arr[i]，arr[i＋1]＝arr[i＋1]，arr[i]
bubbleSort(n－1)
from random import randint
arr＝[64，34，25，12，22，11，90]
n＝randint(3，5)
bubbleSort(n)
调用函数bubbleSort(n)后，arr[3]的值不可能的是(　　)
A.12 B.25 C.34 D.64
16.有如下Python程序段：
#程序段1 def fac(n)： s＝1 for i in range(1，n＋1)： s＝s*i return s print(fac(5))
#程序段2 def fac(n)： if n＝＝1： return 1 else： return n*fac(n－1)　#① print(fac(5))
下列关于两个程序段的说法，正确的是(　　)
A.程序1和程序2都使用了递归算法
B.若问题规模为n，程序1和程序2的时间复杂度不同
C.若程序1中问题规模为n，则n的值就是其循环执行的次数
D.若程序2中自定义函数内的代码只保留①处语句，也能获取到目标值
专题16　算法思想
知识点
1.A　[本题考查递归算法的相关知识。fib(5)＝fib(4)＋fib(3)，fib(4)＝fib(3)＋fib(2)，fib(3)＝fib(2)＋fib(1)＝1＋1＝2，fib(3)为第3次调用函数fib，第3次调用时返回值为2。]
2.A　[本题考查递归算法。f(2)＝(f(3)＋1)*2＝11*2＝22。]
3.D　[本题考查递归算法。用2至x－1之间的数y去检测能否被x整除。若条件y>int(sqrt(x))＋1成立，表示完成所有数检测，返回True；若能够除通返回False；否则将y加1，调用自身函数再次进行检测。]
4.A　[本题考查递归算法及自定义函数知识。由递推公式可以得到：trans(13)＝trans(6)＋″1″＝trans(3)＋″01″＝trans(1)＋″101″。该递归函数的功能是将参数n转换为二进制输出。]
5.D　[本题考查递归算法思想。A选项返回2的3次方。B选项a的n次方，函数调用n次就能得到结果，时间复杂度O(n)。C选项二段代码都有函数的自我调用，是递归算法。D选项描述成如图所示的二叉树，共6个节点，计算6次。]
6.D　[该算法通过递归实现将一个数分解成质因子的乘积。return str(f(num//i))＋″*″＋str(i)是把大的质因子放在前面。]
7.C　[本题考查递归算法思想。根据算法，fn(2023)＝3＋fn(202)，fn(202)＝2＋ fn(20)，fn(20)＝0＋ fn(2)，fn(2)＝2＋fn(0)，因此算法实现将n上各个数字相加。]
8.C　[本题考查递归算法的应用。f(100)＝100＋f(98)，f(98)＝98＋f(96)，而后面的参数均为偶数，依此类推，可得：f(100)＝100＋98＋96＋94＋…＋2＝2550。]
9.C　[myfun(4，18)＝ myfun(7，16)＝ myfun(10，14)，满足a*2>＝s，因此返回10。]
10.B　[程序的功能是分离各个数字并进行相加。]
11.A　[本题考查递归算法。fun(5)的调用过程如图所示。A选项fun(5)的值为FDBCE；B选项 fun(0)的函数调用次数为 1；C选项，从右图可以看出，该算法的时间复杂度只与 n 有关，应为 O(n)；D选项递归通过栈来实现的。]
12.D　[本题考查递归函数相关知识。该程序考查将十进制的数字转换为十六进制。]
13.A　[本题考查递归算法和链表的遍历。将头指针和链表作为参数传入函数，若头指针不为－1，将下一节点的索引作为头指针和链表a重新进行递推，返回时先输出最后一个节点，即对链表进行逆序输出。]
14.B　[本题考查自定义函数和递归。A选项使用递归算法。B选项递归调用4次。C选项每次至多只调用一次，算法时间复杂度和n相关。D选项该自定义函数功能是计算n的阶乘，乘以1的次数不影响结果。]
15.B　[本题考查冒泡排序的递归实现。函数bubbleSort(n)的功能为对数组arr的前n个元素升序排序。当n分别为3，4，5时，arr[3]的值依次为64，34，12不可能是25。]
16.C　[本题考查算法时间复杂度和递归算法。A选项程序段1没有使用递归算法。B选项这两段程序的算法复杂度都是O(n)。C选项根据循环执行的次数计算时间复杂度。D选项递推阶段必须有终止递推的代码。]

展开更多......

收起↑