NOIP2010提高组初赛试题+答案C++

2.已知 a, b, c, d, e, f, g 七个人中， a 会讲英语； b 会讲英语和汉语； c 会讲英语、意大利语和俄语； d 会讲汉语和日语； e 会讲意大利语和德语； f 会讲俄语、日语和法语； g 会讲德语和法语。

能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“ a b ”开头写出你的安排方案： 。

.答： a b d f g e c第十一届（2005）a-b-d-fc-e-g-f g-e-c-f第十二届（2006）三．问题求解（共 2 题，每题 5 分，共计10 分）1．将2006 个人分成若干不相交的子集，每个子集至少有3 个人，并且：（1）在每个子集中，没有人认识该子集的所有人。

（2）同一子集的任何 3 个人中，至少有2 个人互不认识。

（3）对同一子集中任何 2 个不相识的人，在该子集中恰好只有 1 个人认识这两个人。

则满足上述条件的子集最多能有___________个？分析：要使子集数最多，每一子集的人数应最少。

每一子集的人数为3，不符合要求，为4也不符合要求，为5可符合要求。

2．将边长为n 的正三角形每边n 等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。

正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。

在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5 时一条通路的例子）。

设n=10，则该正三角形的不同的通路的总数为_____________。

分析与解：如果n=2，存在的不同的通路总数为1如果n=3，存在的不同的通路总数为2=1*2=2！如果n=4，存在的不同的通路总数为6=1*2*3=3！如果n=5，存在的不同的通路总数为24=1*2*3*4=4！……如果n=10，存在的不同的通路总数为9！第十三届（2007）三．问题求解（共2 题，每题5 分，共计10 分）1．给定n 个有标号的球，标号依次为1，2，…，n。

3. 某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站 状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出， 出，进，出”。假设车辆入站的顺序为 1，2，3，……，则车辆出站的顺序为（ ）。 A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 3, 5, 4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7
( A B) (~ C B) 为（ ）。
A. {a, b, c, d} B. {a, b, d, e} C. {b, d, e} D. {b, c, d, e} E. {d, f, g}
2. 由 3 个 a，5 个 b 和 2 个 c 构成的所有字符串中，包含子串“abc”的共有（ ）个。 A. 40320 B. 39600 C. 840 D. 780 E. 60
第十届全国青少年信息学奥林匹克联赛初赛试题 （ 提高组 C 语言 二小时完成 ）
●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●
一、 单项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题有且仅有一个正确答案.）。
1. 设全集 I = {a, b, c, d, e, f, g}，集合 A = {a, b, c}，B = {b, d, e}，C = {e, f, g}，那么集合
4. 满二叉树的叶结点个数为 N，则它的结点总数为（ ）。 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1
5. 二叉树 T，已知其前序遍历序列为 1 2 4 3 5 7 6，中序遍历序列为 4 2 1 5 7 3 6，则其后 序遍历序列为（ ）。 A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1

第十六届全国青少年信息学奥林匹克联赛初赛试题（提高组C 语言二小时完成）一.单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确选项。

）1.与16进制数A1.2等值的10进制数是（）A.101.2B.111.4C.161.125D.177.252.一个字节（byte）由（）个二进制位组成。

A.8B.16C.32D.以上都有可能3.一下逻辑表达式的值恒为真的是（）A.P∨（┐P∧Q)∨（┐P∧┐Q)B.Q∨（┐P∧Q)∨(P∨┐Q)C.P∨Q∨(P∧┐Q)∨(┐P∧Q)D.P∨┐Q∨(P∧┐Q)∨(┐P∧┐Q)4.Linux下可执行文件的默认扩展名为（）A.exeC.dllD.都不是5.如果在某个进制下等式7*7=41成立，那么在该进制下等式12*12=（）也成立。

A.100B.144C.164D.1966.提出“存储程序”的计算机工作原理的是（）。

A.克劳德·香农B.戈登·摩尔C.查尔斯·巴比奇D.冯·诺依曼7.前缀表达式“+3*2+5 12”的值是（）A.23B.25C.37D.658.主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。

而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。

于是，为了提高系统整体的执行效率，在CPU中引入了（）A.寄存器B.高速缓存C.闪存D.外存9.完全二叉树的顺序存储方案，是指将完全二叉树的结点从上至下、从左至右一次存放到一个顺序结构的数组中。

假定根结点存放在数组的1号位置，则第K号结点的父结点如果存在的话，应当存放在数组的（）号位置。

A.2kB.2k+1C.k/2下取整D.(k+1)/2下取整10.一下竞赛活动中历史最悠久的是（）A.全国青少年信息学奥林匹克联赛（NOIP）B.全国青少年信息学奥林匹克竞赛（NOI）C.国际信息学奥林匹克竞赛（IOI）D.亚太地区信息学奥林匹克竞赛（APIO）二.不定项选择题（共10题，每题1.5分，共计15分。

NOIP2010 初赛 提高组 C++
5
for(i=1;i<=NUM;i++) if(r(n-i)<0) return i; return -1; } int main() { int n; cin>>n; cout<<r(n)<<endl; return 0; } （1）输入：7 输出： （2）输入：16 输出：
NOIP2010 初赛 提高组 C++
2
A．2k
B．2k+1
C．k/2 下取整
D．（k+1）/2 下取整
20．全国青少年信息学奥林匹克系列活动的主办单位是（ ）。 A．教育部 B．科技部 C．共青团中央 D．中国计算机协会 二．问题求解（共 2 题，每空 5 分，共计 10 分） 1．LZW 编码是一种自适应词典编码。在编码的过程中，开始时只有一部基础构造元素的编码词典， 如果在编码的过程中遇到一个新的词条，则该词条及一个新的编码会被追加到词典中，并用于后继 信息的编码。 举例说明，考虑一个待编码的信息串：“xyx yy yy xyx”。初始词典只有 3 个条目，第一个为 x,编码为 1；第二个为 y，编码为 2；第三个为空格，编码为 3；于是串“xyx”的编码为 1-2-1（其 中-为编码分隔符），加上后面的一个空格就是 1-2-1-3。但由于有了一个空格，我们就知道前面的 “xyx”是一个单词，而由于该单词没有在词典中，我们就可以自适应的把这个词条添加到词典里， 编码为 4，然后按照新的词典对后继信息进行编码，以此类推。于是，最后得到编码： 1-2-1-3-2-2-3-5-3-4。 现在已知初始词典的 3 个条目如上述，则信息串“yyxy xx yyxy xyx xx xyx”的编码 是 。 2．队列快照是指某一时刻队列中的元素组成的有序序列。例如，当元素 1、2、3 入队，元素 1 出队 后，此刻的队列快照“2 3”。当元素 2、3 也出队后，队列快照是“ ”，即为空。现有 3 个正整数 元素依次入队、出队。已知它们的和为 8，则共有 种可能的不同的队列快照（不同队列 的相同快照只计一次）。例如，“5 1”，“4 2 2”，“”都是可能的队列快照；而“7”不是可能 的队列快照，因为剩下的 2 个正整数的和不可能为 1。 三．阅读程序写结果（共 4 题，每题 8 分，共计 32 分） 1． #include<iostream> using namespace std; void swap(int &a,int &b) { int t; t=a; a=b; b=t; } int main() { int a1,a2,a3,x; cin>>a1>>a2>>a3; if(a1>a2) swap(a1,a2);