信息学奥赛-入门级 题库
以下对递归方法的描述中,正确的是:( )
选项A:不清楚什么叫“多组参数调用函数”,任意一个带参函数,都可以用多组参数来调用。
选项B:论述正确。
选项C:面向对象编程(或者说“类”)是面向对象和数据而不是功能和逻辑的编程语言模型。
选项D:编译是将用某种高级语言转换为机器代码的编程技术
设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的输出是什么?()
考察递归程序的理解。从代码的第三行到第五行,我们可以发现,返回值是temp和A[i]中较小的值, 所以代码输出的为A数组的最小值。
以下对递归方法的描述中,正确的是:( )
选项A:不清楚什么叫“多组参数调用函数”,任意一个带参函数,都可以用多组参数来调用。
选项B:论述正确。
选项C:面向对象编程(或者说“类”)是面向对象和数据而不是功能和逻辑的编程语言模型。
选项D:编译是将用某种高级语言转换为机器代码的编程技术
设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的输出是什么?()
考察递归程序的理解。从代码的第三行到第五行,我们可以发现,返回值是temp和A[i]中较小的值, 所以代码输出的为A数组的最小值。
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。
字符串匹配(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
【数据范围】

对于所有测试点,保证