首页 › 题库 › 信息学奥赛 › 6.1 递归

信息学奥赛-入门级 题库

共 7 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

以下对递归方法的描述中,正确的是:( )

A
递归是允许使用多组参数调用函数的编程技术
B
递归是通过调用自身来求解问题的编程技术
C
递归是面向对象和数据而不是功能和逻辑的编程语言模型
D
递归是将用某种高级语言转换为机器代码的编程技术
答案与解析
正确答案:B

选项A:不清楚什么叫“多组参数调用函数”,任意一个带参函数,都可以用多组参数来调用。

选项B:论述正确。

选项C:面向对象编程(或者说“类”)是面向对象和数据而不是功能和逻辑的编程语言模型。

选项D:编译是将用某种高级语言转换为机器代码的编程技术

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

设A是n个实数的数组,考虑下面的递归算法:

XYZ (A[1..n])

1.  if n=1 then return A[1]

2.  else temp ← XYZ (A[1..n-1])

3.  if temp < A[n]

4.  then return temp

5.  else return A[n]

请问算法XYZ的输出是什么?()

A
A数组的平均
B
A数组的最小值
C
A数组的最大值
D
A数组的中值
答案与解析
正确答案:B

考察递归程序的理解。从代码的第三行到第五行,我们可以发现,返回值是temp和A[i]中较小的值, 所以代码输出的为A数组的最小值。

题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

以下对递归方法的描述中,正确的是:( )

A
递归是允许使用多组参数调用函数的编程技术
B
递归是通过调用自身来求解问题的编程技术
C
递归是面向对象和数据而不是功能和逻辑的编程语言模型
D
递归是将用某种高级语言转换为机器代码的编程技术
答案与解析
正确答案:B

选项A:不清楚什么叫“多组参数调用函数”,任意一个带参函数,都可以用多组参数来调用。

选项B:论述正确。

选项C:面向对象编程(或者说“类”)是面向对象和数据而不是功能和逻辑的编程语言模型。

选项D:编译是将用某种高级语言转换为机器代码的编程技术

题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

设A是n个实数的数组,考虑下面的递归算法:

XYZ (A[1..n])

1.  if n=1 then return A[1]

2.  else temp ← XYZ (A[1..n-1])

3.  if temp < A[n]

4.  then return temp

5.  else return A[n]

请问算法XYZ的输出是什么?()

A
A数组的平均
B
A数组的最小值
C
A数组的最大值
D
A数组的中值
答案与解析
正确答案:B

考察递归程序的理解。从代码的第三行到第五行,我们可以发现,返回值是temp和A[i]中较小的值, 所以代码输出的为A数组的最小值。

题目详情
5 判断题 偏易 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

当 b 为负数时,customFunction(a,b)会陷入无限递归。( )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
6 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

FBI树

【问题描述】

我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T,递归的构造方法如下:

1) T的根结点为R,其类型与串S的类型相同;

2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1和S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2。

现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历[2]序列。

【输入文件】

输入文件fbi.in的第一行是一个整数N(0 <= N <= 10),第二行是一个长度为2N的“01”串。

【输出文件】

输出文件fbi.out包括一行,这一行只包含一个字符串,即FBI树的后序遍历序列。

【样例输入】

3

10001011

【样例输出】

IBFBBBFIBFIIIFF

【数据规模】

对于40%的数据,N <= 2;

对于全部的数据,N <= 10。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
7 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 6.1 递归

字符串匹配(string)

【题目描述】

小 C 学习完了字符串匹配的相关内容,现在他正在做一道习题。

对于一个字符串 S,题目要求他找到 S 的所有具有下列形式的拆分方案数:S = ABC,S = ABABC,S = ABAB · · · ABC,其中 A,B,C 均是非空字符串,且 A 中出现奇数次的字符数量不超过 C 中出现奇数次的字符数量。

更具体地,我们可以定义 AB 表示两个字符串 A, B 相连接,例如 A = aab,B = ab,则 AB = aabab。

并递归地定义例如 A = abb,则

则小 C 的习题是求的方案数,其中 F(A) ≤ F(C),F(S ) 表示字符串 S中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 A、B、C 中有至少一个字符串不同。

小 C 并不会做这道题,只好向你求助,请你帮帮他。

【输入格式】

从文件 string.in 中读入数据。

本题有多组数据,输入文件第一行一个正整数 T 表示数据组数。

每组数据仅一行一个字符串 S,意义见题目描述。S 仅由英文小写字母构成。

【输出格式】

输出到文件 string.out 中。

对于每组数据输出一行一个整数表示答案。

【样例 1 输入】

3

nnrnnr

zzzaab

mmlmmlo

【样例 1 输出】

8

9

16

【样例 1 解释】

对于第一组数据,所有的方案为:

1. A=n,B=nr,C=nnr。

2. A=n,B=nrn,C=nr。

3. A=n,B=nrnn,C=r。

4. A=nn,B=r,C=nnr。

5. A=nn,B=rn,C=nr。

6. A=nn,B=rnn,C=r。

7. A=nnr,B=n,C=nr。

8. A=nnr,B=nn,C=r。

【样例 2 输入】

5

kkkkkkkkkkkkkkkkkkkk

lllllllllllllrrlllrr

cccccccccccccxcxxxcc

ccccccccccccccaababa

ggggggggggggggbaabab

【样例 2 输出】

156

138

138

147

194

【数据范围】

对于所有测试点,保证

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情