NOIP题~~

求NOIP复赛的练习题~带参考答案~量越大越好~~

郑重声明：C语言的！~！~~~

全国信息学奥林匹克联赛（NOIP2008）复赛
提高组
一、题目概览
中文题目名称 笨小猴 火柴棒等式 传纸条 双栈排序
英文题目名称 word matches message twostack
可执行文件名 word matches message twostack
输入文件名 word,in matches.in message.in twostack.in
输出文件名 word.out matches.out message.out twostack.out
每个测试点时限 1秒 1秒 1秒 1秒
测试点数目 10 10 10 10
每个测试点分值 10 10 10 10
比较方式 全文比较 全文比较 全文比较 全文比较
题目类型 传统 传统 传统 传统
二、提交源程序文件名
对于Pascal语言 word.pas matches.pas message.pas twostack.pas
对于C语言 word.c matches.c message.c twostack.c
对于C++语言 word.cpp matches.cpp message.cpp twostack.cpp
三、编译命令（不包含任何优化开关）
对于Pascal语言 fpc word.pas fpc matches.pas fpc message.pas fpc twostack.pas
对于C语言 gcc –o word word.c gcc –o matches matches.c gcc –o message message.c gcc –o twostack twostack.c
对于C++语言 g++ -o word word.cpp g++-o matches matches.cpp g++ -o message message.cpp g++ -o twostack twostack.cpp
四、运行内存限制
运行内存上限 50M 50M 50M 50M
注意事项：
1. 文件名（程序名和输入输出文件名）必须使用大写。
2. C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3. 全国统一评测时采用的机器配置为：CPU 1.9GHz，内存512M，上述时限以此配置为准。各省在自测时可根据具体配置调整时限。

1. 笨小猴
(wird.pas/c/cpp)
【问题描述】
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大！
这种方法的具体描述如下：假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数，如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky Word，这样的单词很可能就是正确的答案。
【输入】
输入文件word.in只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
【输出】
输出文件word.out共两行，第一行是一个字符串，假设输入的的单词是Lucky Word，那么输出“Lucky Word”，否则输出“No Answer”；
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。
【输入输出样例1】
word.in word.out
error Lucky Word
2
【输入输出样例1解释】
单词error中出现最多的字母r出现了3次，出现次数最少的字母出现了1次，3-1=2，2是质数。
【输入输出样例2】
word.in word.out
Olympic No Answer
0
【输入输出样例2解释】
单词olympic中出现最多的字母i出现了2次，出现次数最少的字母出现了1次，2-1=1，1不是质数。
2. 火柴棒等式
(matches.pas/c/cpp)
【问题描述】
给你n根火柴棍，你可以拼出多少个形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整数（若该数非零，则最高位不能是0）。用火柴棍拼数字0-9的拼法如图所示：

注意：
1. 加号与等号各自需要两根火柴棍
2. 如果A≠B，则A+B=C与B+A=C视为不同的等式（A、B、C>=0）
3. n根火柴棍必须全部用上
【输入】
输入文件matches.in共一行，又一个整数n（n<=24）。
【输出】
输出文件matches.out共一行，表示能拼成的不同等式的数目。
【输入输出样例1】
matches.in matches.out
14 2
【输入输出样例1解释】
2个等式为0+1=1和1+0=1。
【输入输出样例2】
matches.in matches.out
18 9
【输入输出样例2解释】
9个等式为：
0+4=4
0+11=11
1+10=11
2+2=4
2+7=9
4+0=4
7+2=9
10+1=11
11+0=11
3. 传纸条
(wassage.pas/c/cpp)
【问题描述】
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。
【输入】
输入文件message.in的第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。
接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。
【输出】
输出文件message.out共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。
【输入输出样例】
message.in message.out
3 3
0 3 9
2 8 5
5 7 0 34
【限制】
30%的数据满足：1<=m,n<=10
100%的数据满足：1<=m,n<=50
4. 双栈排序
(twostack.pas/c/cpp)
【问题描述】
Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。
操作a
如果输入序列不为空，将第一个元素压入栈S1
操作b
如果栈S1不为空，将S1栈顶元素弹出至输出序列
操作c
如果输入序列不为空，将第一个元素压入栈S2
操作d
如果栈S2不为空，将S2栈顶元素弹出至输出序列
如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列：<a,c,c,b,a,d,d,b>

当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)，<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。
【输入】
输入文件twostack.in的第一行是一个整数n。
第二行有n个用空格隔开的正整数，构成一个1~n的排列。
【输出】
输出文件twostack.out共一行，如果输入的排列不是“可双栈排序排列”，输出数字0；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。
【输入输出样例1】
twostack.in twostack.out
4
1 3 2 4 a b a a b b a b
【输入输出样例2】
twostack.in twostack.out
4
2 3 4 1 0
【输入输出样例3】
twostack.in twostack.out
3
2 3 1 a c a b b d
【限制】
30%的数据满足： n<=10
50%的数据满足： n<=50
100%的数据满足： n<=1000

`

~

-

=

+

.

去这个网站看看

www.rqnoj.cn

www.vijos.cn

一、单项选择题（共20题，每题1.5分。每题有且仅有一个正确答案。） 1．微型计算机中，控制器的基本功能是（ ）。 A．控制机器各个部件协调工作 B．实现算术运算和逻辑运算 C．获取外部信息 D．存放程序和数据 2．设A=True，B=False，C=True，D=False，以下逻辑运算表达式值为真的是（ ）。 A．(A∧B)∨(C∧D∨﹁A) B．((﹁A∧B) ∨C)∧﹁D C．(B∨C∨D) ∧D∧A D．A∧（D∨﹁C）∧B 3．在下列关于图灵奖的说法中，不正确的是（ ）。 A．图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B．图灵奖有“计算机界诺贝尔奖”之称 C．迄今为止，还没有华裔计算机科学家获此殊荣 D．图灵奖的名称取自计算机科学的先驱、英国科学家阿兰&#8226;图灵 4．计算机在工作过程中，若突然停电，（ ）中的信息不会丢失。 A．ROM 和 RAM B．CPU C．ROM D．RAM 5．完全二叉树共有2*N-1个结点，则它的叶节点数是（ ）。 A．N-1 B．N C．2*N D．2N-1 6．在以下各项中，( ）不是操作系统软件。 A．Solaris B．Linux C．Windows Vista D．Sybase 7．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，f，e，c，a，则栈S的容量至少应该是（ ）。 A．6 B．5 C．4 D．3 8．与十进制数28.5625相等的四进制数是（ ）。 A．123.21 B．131.22 C．130.22 D．130.21 9．设字符串S=”Olympic”，S的非字串的数目是（ ）。 A．28 B．29 C．16 D．17 10．Web2.0 是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（ ）是典型的Web 2.0应用。 A．Sina B．Flicker C．Yahoo D．Google 11．递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．线性表 D．栈 12．(2008)10+(5B)16的结果是（ ）。 A．（833）16 B．（2089）10 C．（4163）8 D．（100001100011）2 13．二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为节点的编号，下同），中根遍历2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。 A．4 2 5 7 6 3 1 B．4 2 7 5 6 3 1 C．7 4 2 5 6 3 1 D．4 2 7 6 5 3 1 14．将数组{8，23，4，16，77，-5，53，100}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。 A．4 B．5 C．6 D．7 15．对有序数组{ 5，13，19，21，37，56，64，75，88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。 A．1 B．2 C．3 D．4 16 ．面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象设计的说法中，不正确的是（ ) A．面向对象程序设计通常采用自顶向下设计方法进行设计。 B．面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性 (polymorphism）等几大特点。 C．支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C++，JAVA，C# 等。 D．面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk语言仍然被视为面向对象语言的基础 17．在32*32点阵的“字库”中，汉字“北”与“京”的字模占用字节数之和是（ ）。 A．512 B．256 C．384 D．128 18．设T是一棵有n个顶点的树，下列说法不正确的是（ ）。 A．T有n条边 B．T是连通的 C．T是无环的 D．T有n-1条边 19．下列不属于NOIP竞赛推荐使用的语言环境的是（ ）。 A．Dev-C++ B．Visual C++ C．Free Pascal D．Lazarus 20．在Pascal程序中，表达式（200 or 10）的值是（ ）。 A．20 B．1 C．220 D．202 二、问题求解（共2题，每题5分，共计10分） 1．书架上有4本不同的书A、B、C、D。其中A和B是红皮的，C和D是黑皮的。把这4本书摆在书架上，满足所有黑皮的书都排在一起的摆法有_________种。满足A必须比C靠左，所有红皮的书要摆在一起，所有黑皮的书要摆放在一起，共有_________种摆法。 2．有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为__________________。 城市1 城市2 城市3 城市4 城市5 城市6 城市1 0 2 3 1 12 15 城市2 2 0 2 5 3 12 城市3 3 2 0 3 6 5 城市4 1 5 3 0 7 9 城市5 12 3 6 7 0 2 城市6 15 12 5 9 2 0 三、阅读程序写结果（共4题，每题8分，共计32分） 1．VAR i,a,b,c,d:integer; f:array[0..3] of integer; BEGIN for i:=0 to 3 do read(f[i]); a:=f[0]+f[1]+f[2]+f[3]; a:=a div f[0]; b:=f[0]+f[2]+f[3]; b:=b div a; c:=(b*f[1]+a) div f[2]; d:=f[(b div c) mod 4]; if (f[(a+b+c+d) mod 4]>f[2]) then begin a:=a+b; writeln(a); end else begin c:=c+d; writeln(c); end; END. 输入：9 19 29 39 输出：__________________________ 2．procedure foo(a,b,c:integer); begin if a>b then foo(c,a,b) else writeln(a,',',b,',',c); end; var a,b,c:integer; begin read(a,b,c); foo(a,b,c); end. 输入：3 1 2 输出：_________________________ 3．type TT=array[0..20]of integer; prodecure func(var ary:TT;n:integer); var i,j,x:integer; begin i:=0;j:=n-1; while i<j do begin while (i<j) and (ary>0) do inc(i); while (i<j) and (ary[j]<0) do dec(j); if i<j then begin x:=ary; ary:=ary[j]; ary[j]:=x; inc(i); dec(j); end; end; end; var a:TT; i,m:integer; begin m:=10; for i:=0 to m-1 do read(a); func(a,m); for i:=1 to m-1 do write(a,' ');liyilong.net writeln; end. 输入：5 4 -6 -11 6 -59 22 -6 1 10 输出：___________________________________________ 4．procedure solve(first:string;spos_f,epos_f:integer;mid:string;spos_m,epos_m:integer); var i,root_m:integer; begin if spos_f > epos_f then exit; for i:=spos_m to epos_m do if first[spos_f]=mid[i] then begin root_m:=i; break; end; solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1); solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+1,epos_m); write(first[spos_f]); end; var first,mid:string; len:integer; begin readln(len); readln(first); readln(mid); solve(first,1,len,mid,1,len); writeln; end. 输入：7 ABDCEGF BDAGECF 输出：_________________________________ <br /> 四．完善程序（前四空，每空2.5分，后6空，每空3分，共28分） 1．（字符串替换）给定一个字符串S（S仅包含大小写字母），下面的程序将S中的每个字母用规定的字母替换，并输出S经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串S，第二个字符串S’由26个字母组成，它是a~z的任一排列，大小写不定，S’规定了每个字母对应的替换字母：S’中的第一个字母是字母A和a的替换字母，即 S中的A用该字母的大写替换，S中的a用该字母的小写替换；S’中的第二个字母是字母B 和b的替换字母，即S中的B用该字母的大写替换，S中的b用该字母的小写替换；… …以此类推。 Var change:string; Str:string; Procedure CheckChangeRule; Var i:integer; Begin for i:=1 to 26 do begin if ____①_____ then change[i]:=chr(ord(change[i])-ord('A')+ord('a')); end; end; Procedure ChangeString; Var len,i:integer; begin len:=length(str); for i:=1 to len do begin if ______②______ then begin str[i]:=upcase(change[ord(str[i]-ord('A')+1]); end; else begin _______④_______ end; end; end; begin readln(str); readln(change); CheckChangeRule; _______⑤_______ writeln(str); end. 2．（找第k大的数）给定一个长度为1,000,000的无序正整数序列，以及另一个数n（1≤n≤1000000），然后以类似快速排序的方法找到序列中第n大的数（关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4。） VAR a:array[1..1000000] of integer; n,m,ans:integer; Procedure swap(var a,b:integer); var t:integer; begin if (a<>b) then begin t:=a; a:=b; b:=t; end; end; function FindKth(left,right,n:integer):integer; var tmp,value,i,j:integer; begin if left=right then exit(left); tmp:=random(right-left)+left; swap(a[tmp],a[left]); value:=_____①______; i:=left; j:=right; while i<j do begin while (i<j) and (____②_____) do dec(j); if i<j then begin a[i]:=a[j]; inc(i); end else break; while (i<j) and (____③_____) do inc(i); if i<j then begin a[j]:=a[i]; dec(j); end else break; end; ______④_______ if i<n then begin inc(i); exit(FindKth(______⑤______)); end; if i>n then begin dec(i); exit(_____⑥_____); end; exit(i); end; var i:integer; begin randomize; m:=1000000; for i:=1 to m do read(a[i])); read(n); ans:=FindKth(1,m,n); writeln(a[ans]); end.

NOIP2008年普及组（Pascal语言）参考答案与评分标准 一、单项选择题：（每题1.5分） 1. A 2. B 3. C 4. C 5. B 6. D 7. C 8. D 9. A 10. B 11. D 12. A 13. B 14. B 15. B 16. A 17. B 18. A 19. B 20. D 二、问题求解：（共2题，每题5分，共计10分） 1．12 4 2．7(1->2->5->6) 三、阅读程序写结果（共4题，每题8分，共计32分） 1. 23 2. 2,3,1 3. 5 4 10 1 6 22 -59 -6 -11 -6 4. DBGEFCA （求树的后序遍历） 四．完善程序 (前4空，每空2.5分，后6空，每空3分，共28分) （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1. ① (change[i] >= 'A') and (change[i] <= 'Z') (只写(change[i] <= 'Z')也对) ② (str[i] >= 'A') and (str[i] <= 'Z') （只写str[i] <= 'Z'也对） ③ str[i] := change[ord(str[i]) - ord('a') +1]; ④ ChangeString; 2． ① a[left] ② a[j] < value (或a[j] <= value) ③ a[i] > value （或a[i] >= value） ④ a[i] := value; ⑤ i,right,n ⑥ FindKth(left, i, n)