首页 › 题库 › Python编程考级 › 3 递归与递推

Python编程四级 题库

共 65 道题 ,第 1 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3 递归与递推 清除
1 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

以下选项中关于递归算法的描述,错误的是?( )

A
书写简单
B
一定要有基例(指不需要递归就能求解的解)
C
递归算法都可以用非递归的方法实现
D
执行效率高
答案与解析
正确答案:D

知识点:递归与递推

题目详情
2 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

有 2*n的一个长方形方格,用一个1*2的骨牌铺满方格,当n=5时,铺法总数为多少?( )

A
5
B
6
C
7
D
8
答案与解析
正确答案:D

对一般的n,要求xn可以这样来考虑,若第一个骨牌是竖排列放置,剩下有n-1个骨牌需要排列,这时排列方法数为xn-1;若第一个骨牌是横排列,整个方格至少有2个骨牌是横排列(1*2骨牌),因此剩下n-2个骨牌需要排列,这是骨牌排列方法数为xn-2。从第一骨牌排列方法考虑,只有这两种可能,所以有: 

 xn=xn-1+xn-2 (n>2) 

 x1=1 

 x2=2 

 xn=xn-1+xn-2就是问题求解的递推公式,任给n都可以从中获得解答。例如n=5, 

 x3=x2+x1=3 

 x4=x3+x2=5 

 x5=x4+x3=8


题目详情
3 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

下列有关循环和递归的描述正确的是?( )

A
递归思想代码清晰简洁,可读性强
B
递归代码中不能有循环结构的语句
C
递归是从问题的起点出发,逐渐将复杂问题化为简单问题,最终求得问题
D
能用递归实现的,一定能用循环代码实现
答案与解析
正确答案:A

递归是从问题的目标出发,逐渐将复杂问题化为简单问题,最终求得问题

题目详情
4 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

对自然数1至n求和,如果将递推式f(n)=f(n-1)+n(n>1)转化成递归函数,则递归出口是?( )

A
f(1)=1
B
f(1)=0
C
f(0)=1
D
f(0)=0
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
5 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子。假如兔子都不死,要求输出一年内兔子的数量是多少。如果采用递归算法来编程,则核心的递归逻辑应该是?( )

A
f(n) =n*f(n-1)
B
f(n) = f(n-1)+n
C
f(n) = f(n-1)+f(n-2)
D
f(n) = f(n-1)+ (n-1)f(n-2)
答案与解析
正确答案:C

只有C是符合题意的递推式。

题目详情
6 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

下面关于递归的描述不正确的是?( )

A
递归思想是将大型复杂的问题转化为一个与原问题相似的规模较小的问题来求解
B
递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,它不是分治策略的具体体现
C
递归必须有终止递归的条件
D

递归是在过程或函数里调用自身

答案与解析
正确答案:B

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,它是分治策略的具体体现

题目详情
7 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

下面关于递归算法的描述,错误的是?( )

A
任何递归程序都可以改写成非递归程序
B
定义简单,逻辑清晰
C
算法的执行效率较高
D
原问题与子问题在结构上必须相似
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
8 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

关于递归与递推方法的比较,错误的观点是?( )

A
递归是将复杂问题降解成若干个子问题,依次降解,求出低阶规模的解,代入高阶问题中,直至求出原问题的解;
B
递推是构造低阶的问题,并求出解,依次推导出高阶的问题以及解,直至求出问题的解;
C
数学上的递推关系可以通过递归的方法来实现;
D
递归算法代码简洁,运行速度比递推快,因此应该尽量采用递归的方法;
答案与解析
正确答案:D

递归的运行开销大。

题目详情
9 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

对于下列递归式子,当n=4时,F的值是?( )

F(n)=F(n-1)+3    F(1)=2

A
2
B
5
C
11
D
14
答案与解析
正确答案:C

用递归式子推导得出。

题目详情
10 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

下列关于递归的描述不正确的是? ( )

A
递归函数一定包含条件控制语句
B
递归函数一定包含调用自身的语句
C
在调用自身函数时需要明确的边界终止条件
D
递归算法一般代码简洁,执行效率高,空间复杂度低
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
11 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

以下关于递归与递推方法的比较,正确的观点是? ( )

A
递推是将复杂问题分解成若干个子问题,依次降解,求出低阶规模的解,代入高阶问题中,直至求出原问题的解
B
递归是构造低阶规模的问题,并求出解,依次推导出高阶的问题以及解,直至求出问题的解
C
数学上的递推关系可以通过递归的方法来实现
D
递归算法代码简洁,运行速度比递推快,因此应该尽量采用递归的方法
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
12 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

递归算法的执行过程,一般来说,可先后分成以下哪两个阶段?( )

A
穷举和回归
B
递推和回归
C
穷举和回溯
D
递推和回溯
答案与解析
正确答案:B

用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成一些规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模稍大问题的解。特别地,当规模N=1时,能直接得到解。 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题的求解推到比原问题简单一些的问题的求解;在回归阶段,当获得最简单情况的解后,逐级返回,依次获得稍复杂问题的解。

题目详情
13 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

设某算法的计算时间表示为递推关系式T(n)=T(n-1)+n(n为正整数)及T(0)=1,该算法的时间复杂度为以下哪一项?( )

A
O(log2n)
B
O(nlog2n)
C
O(n)
D
O(n2)
答案与解析
正确答案:D

T(n) = T(n-1)+n 

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

T(n) = T(0) .... n-2+ n-1 + n = n * (n+1)/2,当n趋近于无穷大的时候,T(n) =n*n。

题目详情
14 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

以下关于递归与递推的说法,错误的是?( )

A
递归算法不涉及高深的数学知识,比较容易理解。
B

递归过程一般通过函数或子过程来实现。

C

递归算法是递推分解问题,然后再将最简单情况的解回归成大问题的解。

D

存在既可以用递归算法解决,也可以用递推算法解决的问题。

答案与解析
正确答案:A

递归算法虽然不涉及高深的数学知识,但是递归思想和模型并不容易理解。

题目详情
15 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

一般来说,递归需要有边界条件、递归前进段和递归返回段。当不满足边界条件时,(?);当满足边界条件时,(?)。

A
返回,前进
B
中断,前进
C
前进,返回
D
中断,返回
答案与解析
正确答案:C

递归运行的条件,不满足边界条件前进,满足返回。

题目详情
16 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

下列有关递归的描述中,正确的是?( )

A
递归函数中肯定有循环结构;
B
递归没有体现“大事化小”的思想;
C
递归有明确的结束递归的边界条件;
D
递归执行效率较高。
答案与解析
正确答案:C

递归有明确的结束递归的边界条件以及结束时的边界值,递归体现了“大事化小”的思想。

题目详情
17 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。问第n年的时候,共有多少头母牛?

由递推法可推测,当年数小于等于4的时候,第几年就是有几头牛,即a[1]=1;a[2]=2;a[3]=3;a[4]=4。当n大于4的时候,这时候第一年出生的那个小母牛就也可以生出小母牛了,也就是该考虑小母牛是否可以生了,所以n>4的时候,a[n]=?

A
a[n-1]+a[n-3]
B
a[n-1]+a[n-4]
C
a[1]+a[3]
D
a[-1]+a[-3]
答案与解析
正确答案:A

前四年共有四只,从第五年开始,第二年出生的小母牛也会生一只母牛(而且以后每年初都会生一只母牛),加上第一年那只母牛生的小母牛,共有六只母牛;第六年的时候得加上第三年那只母牛生的母牛,共九只母牛;依次类推。

题目详情
18 单选题 适中 Python编程考级 ·Python编程四级 · 3.1 递归

下列有关递归的描述中,正确的是?

A
递归函数中肯定有循环结构
B
递归没有体现“大事化小”的思想
C
递归有明确的结束递归的边界条件
D
递归执行效率较高
答案与解析
正确答案:C

递归有明确的结束递归的边界条件以及结束时的边界值,递归体现了“大事化小”的思想。

题目详情
19 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推

小方的妈妈分苹果方法如下,第一天分掉其中一半加一个苹果,第二天分掉剩下的一半加一个苹果,以后每天都分掉剩下的一半加一个苹果。到第8天的时候妈妈发现只剩一个苹果了。请问小方妈妈一开始有多少个苹果? 这个问题我们可以用以下什么算法解决?

A
查找
B
递推
C
枚举
D
排序
答案与解析
正确答案:B

从第8天往前计算第7天剩余的苹果数,然后再计算第6天的,依次递推解决问题。这是递推问题

题目详情
20 单选题 适中 Python编程考级 ·Python编程四级 · 3.2 递推
自然界的规律:花瓣的个数大多数花瓣的个数有1、1、2、3、5、8、13、21、......,仔细观察这些数的顺序,会发现这些数的排列是有规律的,即斐波那契数列。小李同学编写程序求该数列的第n项的值。方框中的代码由以下三部分组成:① a=b  ② b=c  ③ c=a+b,下列选项中代码顺序正确的是?
A
①②③
B

①③②

C

③②①

D

③①②

答案与解析
正确答案:D

递推法求斐波那契数列,选D。

题目详情