第一篇：第十三届全国青少年信息学奥林匹克联赛初赛试题
第十三届全国青少年信息学奥林匹克联赛初赛试题（普及组 Pascal 语言 二小时完成）
●
● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●
一、单项选择题（共20题，每题1.5分，共计30分。每题有且仅有一个正确答案。）
1．在以下各项中，（）不是CPU的组成部分。A．控制器
B．运算器
C．寄存器
D．主板
2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。A．二叉树
B．多叉树
C．哈希表
D．二维表
3．在下列各项中，只有（）不是计算机存储容量的常用单位。A．Byte
B．KB
C．UB
D．TB
4．ASCII码的含义是（）。
A．二→十进制转换码
B．美国信息交换标准代码
C．数字的二进制编码
D．计算机可处理字符的唯一编码
5．一个完整的计算机系统应包括（）。
A．系统硬件和系统软件
B．硬件系统和软件系统
C．主机和外部设备
D．主机、键盘、显示器和辅助存储器
6．IT的含义是（）。
A．通信技术
B．信息技术
C．网络技术
D．信息学
7．LAN的含义是（）。
A．因特网
B．局域网
C．广域网
D．城域网 8．冗余数据是指可以由其它数据导出的数据。例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往往会造成数据的不一致。例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（）。A．应该在数据库中消除一切冗余数据
B．用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据 C．为了提高查询效率，在数据库中可以保留一些冗余数据，但更新时要做相容性检验 D．做相容性检验会降低效率，可以不理睬数据库中的冗余数据
9．在下列各软件，不属于NOIP竞赛（复赛）推荐使用的语言环境有（）。A．gcc
B．g++
C．Turbo C
D．Free Pascal
10．以下断电后仍能保存数据的有（）。
A．硬盘
B．高速缓存
C．显存
D．RAM 11．在下列关于计算机语言的说法中，正确的有（）。A．高级语言比汇编语言更高级，是因为它的程序的运行效率更高
B．随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出了历史舞台 C．高级语言比汇编语言程序更容易从一种计算机上移植到另一种计算机上 D．C是一种面向对象的高级计算机语言
12．近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（）。
A．在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间
B．和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些 C．对于较复杂的问题，用递归方式编程一般比非递归方式更难一些
D．对于已经定义好的标准数学函数 sin(x)，应用程序中的语句“y=sin(sin(x));”就是一种递归调用
13．一个无法靠自身的控制终止的循环成为“死循环”，例如，在C语言程序中，语句“while(1)printf(“*”);”就是一个死循环，运行时它将无休止地打印*号。下面关于死循环的说法中，只有（）是正确的。A．不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检查
B．有些编译系统可以检测出死循环
C．死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环 D．死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的
14．在Pascal语言中，表达式（23 or 2 xor 5）的值是（）。A．18
B．1
C．23
D．32
15．在Pascal语言中，判断整数a等于0或b等于0或c等于0的正确的条件表达式是（）。A．not((a<>0)or(b<>0)or(c<>0))B．not((a<>0)and(b<>0)and(c<>0))C．not((a=0)and(b=0))or(c<>0)D．(a=0)and(b=0)and(c=0)
16．地面上有标号为A、B、C的三根柱，在A柱上放有10个直径相同中间有孔的圆盘，从上到下依次编号为1，2，3……，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为“进、进、出、进、进、出、出、进、进、出、进、出、出”。那么，在C柱上，从下到上的编号为（）。
A．2 4 3 6 5 7
B．2 4 1 2 5 7
C．2 4 3 1 7 6
D．2 4 3 6 7 5
17．与十进制数1770对应的八进制数是（）。
A．3350
B．3351
C．3352
D．3540
18．设A=B=True，C=D=False，一下逻辑运算表达式值为假的有（）。A．(﹁A∧B)∨(C∧D∨A)
B．﹁(((A∧B)∨C)∧D)C．A∧(B∨C∨D)∨D
D．(A∧(D∨C))∧B
19．(2070)16 +(34)8 的结果是（）。A．（8332）10
B．（208A）16
C．（100000000110）2 D．(20212)8
20．已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（）。
A．4 6 5 2 7 3 1
B．4 6 5 2 1 3 7 C．4 2 3 1 5 4 7
D．4 6 5 3 1 7 2
二、问题求解（共2题，每题5分，共计10分）。
1、（子集划分）将n个数（1，2，…，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=______________。（提示：先固定一个数，对于其余的5个数考虑S(5,3)与S(5,2)，再分这两种情况对原固定的数进行分析。）
2、（最短路线）某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？___________
B
A
三、阅读程序写结果（共4题，每题8分，共计32分。）
1、program j301;var i,a,b,c,x,y:integer;
p:array[0..4] of integer;begin
y:=20;
for i:=0 to 4 do read(p);
readln;
a:=(p[0]+p[1])+(p[2]+p[3]+p[4])div 7;
b:=p[0]+p[1] div((p[2]+p[3])div p[4]);
c:=p[0]*p[1] div p[2];
x:=a+b-p[(p[3]+3)mod 4];
if(x>10)
then y:=y+(b*100-a)div(p[p[4] mod 3]*5)
else
y:=y+20+(b*100-c)div(p[p[4] mod 3]*5);
writeln(x,',',y);end.{注：本例中，给定的输入数据可以避免分母为0或数组元素下表越界。} 输入：6 6 5 5 3 输出：______________________
2、program j302;var a,b:integer;var x,y:^integer;procedure fun(a,b:integer);var k:integer;begin k:=a;a:=b;b:=k;end;begin
a:=3;b:=6;
x:=@a;y:=@b;
fun(x^,y^);
writeln(a,',',b);end.输出：_______________________________
3、program j303;var a1:array[1..50] of integer;var i,j,t,t2,n,n2:integer;begin
n:=50;
for i:=1 to n do a1:=0;
n2:=round(sqrt(n));
for i:=2 to n2 do
if(a1=0)then
begin
t2:=n div i;
for j:=2 to t2 do a1[i*j]:=1;
end;
t:=0;
for i:=2 to n do
if(a1=0)then
begin
write(i:4);inc(t);
if(t mod 10=0)then writeln;
end;
writeln;end.输出：_____________________________________________
_____________________________________________
4、Program j304;Type str1=string[100];
Str2=string[200];Var
S1:str1;s2:str2;Function isalpha(c:char):Boolean;Var i:integer;Begin
i:=ord(c);
if((i>=65)and(i<=90))or((i>=97)and(i<=122))then
isalpha:=true
else isalpha:=false;end;function isdigit(c:char):Boolean;var i:integer;begin
i:=ord(c);if(i>=48)and(i<=57)then isdigit:=true
else isdigit:=false;end;procedure expand(s1:str1;var s2:str2);var i,j:integer;a,b,c:char;begin
j:=1;c:=char(1);i:=0;
while(i<=ord(s1[0]))do
begin inc(i);c:=s1;
if c='-' then begin {1}
a:=s1[i-1];b:=s1[i+1];
if(isalpha(a)and isalpha(b))or(isdigit(a)and isdigit(b))then begin
dec(j);
while(ord(upcase(a)) begin s2[j]:=a;inc(j);inc(a);end; end else begin s2[j]:=c;inc(j);end;end{1} else begin s2[j]:=c;inc(j);end;end;s2[0]:=char(j-2);end;begin readln(s1);expand(s1,s2);writeln(s2);end.输入：wer2345d-h454-82qqq 输出：__________________________ 四、完善程序（前4空，每空2.5分，后6空，每空3分，共28分）。 1、（求字符的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入-1终止程序。 请将程序补充完整。Program j401;type str1=string[100];var line:str1;kz:integer;procedure reverse(var s:str1);var I,j:integer;t:char;begin i:=1;j:=length(s); while(i t:=s;s:=s[j];s[j]:=t; ;; end;end;begin writeln(„continue?-1 for end.‟); readln(kz); while()do begin readln(line); ; writeln(line); writeln(„continue?-1 for end.‟); readln(kz); end;end.2 3 3 2-1 1 3 4 1 1 5 4 4 5 5 2、（棋盘覆盖问题）在一个2k×2 k个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为-1的方格），称之为特殊方格。现用L型（占3个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是（4 k-1）/3。在下表给出的一个覆盖方案中，k=2，相同的3各数字构成一个纸片。 下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。请将程序补充完整。 Program j402;type arr1=array[1..65] of integer; arr2=array[1..65] of arr1;var board:arr2;tile:integer;size,dr,dc:integer;procedure chessboard(tr,tc:integer;dr,dc:integer;var size:integer);var t,s:integer;begin if(size=1)then; t:=tile;inc(tile); s:=size div 2; if then chessboard(tr,tc,dr,dc,s)else begin board[tr+s-1]:=t;;end;if(dr else begin board[tr+s-1][tc+s]:=t; ;end;if(dr>=tr+s)and(dc board[tr+s][tc+s]:=t; ;end;if(dr>=tr+s)and(dc>=tc+s)then chessboard(tr+s,tc+s,dr,dc,s)else begin board[tr+s][tc+s]:=t;;end;end;procedure prt1(n:integer);var I,j:integer;begin for I:=1 to n do begin for j:=1 to n do write(board[j]:3); writeln;end;end;begin writeln(„input size(4/8/16/64):‟); readln(size);writeln(„input the position of special block(x,y):‟); readln(dr,dc);board[dr][dc]:=-1; tile:=1;chessboard(1,1,dr,dc,size);prt1(size);end.NOIP2007年普及组（Pascal语言）参考答案与评分标准 一、单项选择题：（每题1.5分） 题号 2 3 4 5 6 7 8 9 10 答案 D D C B B B B C C A 题号 12 13 14 15 16 17 18 19 20 答案 C A A A B D C D A A 二、问题求解：（每题 5分） 1．90 2．210 三、阅读程序写结果 1.15, 46（对1个数给4分，无逗号扣1分）2.3, 6 3.2 3 5 7 11 13 17 19 23 29 47 4.wer2345defgh45456782qqq 四、完善程序(前4空（①--④），每空2.5分，后6空（⑤--⑩），每空3分) （说明：以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查） 1．① inc(i)或i:=i+1 ② dec(j)或 j:=j-1 ③ kz<>-1 ④ reverse(line)2.⑤ exit ⑥(dr 全国青少年信息学奥林匹克联赛 目录 高考加分和保送 联赛命题宗旨 普及的内容 竞赛形式和成绩评定 试题的知识范围 全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Provinces简称NOIP)自1995年至今已举办16次。每年由中国计算机学会统一组织。NOIP在同一时间、不同地点以各省市为单位由特派员组织。全国统一大纲、统一试卷。初、高中或其他中等专业学校的学生可报名参加联赛。联赛分初赛和复赛两个阶段。初赛考察通用和实用的计算机科学知识，以笔试为主。复赛为程序设计，须在计算机上调试完成。参加初赛者须达到一定分数线后才有资格参加复赛。联赛分普及组和提高组两个组别，难度不同，分别面向初中和高中阶段的学生。获得提高组复赛一等奖的选手即可免高考，而通过大学的保送生考试直接被录取。 高考加分和保送 NOIP的部分一等奖具有保送名校或者高考加分(分数的多少视该校自主招生考试结果而定)的资格。NOIP的部分一等奖有参加省队选拔赛的资格，省队的选手可以参加NOI，NOI获奖选手有保送资格。 联赛命题宗旨 全国青少年信息学奥林匹克联赛（NOIP）是一项面向全国青少年的信息学竞赛和普及活动，旨在向那些在中学阶段学习的青少年普及计算机科学知识；给学校的信息技术教育课程提供动力和新的思路；给那些有才华的学生提供相互交流和学习的机会；通过竞赛和相关的活动培养和选拔优秀的计算机人才。 竞赛的目的是为了在更高层次上推动普及。本竞赛及其相关活动遵循开放性原则，任何有条件和有兴趣的学校和个人，都可以在业余时间自愿参加。本活动不和现行的学校教学相冲突，也不列入教学计划，是课外性质的因材施教活动。参加者可为初高中学生或其他中等专业学校的青少年。 普及的内容 ．计算机的基本组成； ．计算机操作系统使用（windows等）； ．计算机工作的基本原理； ．计算机程序设计的基本方法； ．至少一门高级程序设计语言； ．程序设计中常用的数据结构。 普及的重点是根据中学生的特点，培养学生学习计算机的兴趣，使得他们对信息技术的一些本质和核心的东西有更多的了解，提高他们创造性地运用程序设计知识解决实际问题的能力。 对学生的能力培养注重 ．想象力与创造力； ．对问题的理解和分析能力； ．数学能力和逻辑思维能力； ．对客观问题和主观思维的口头和书面表达能力； ．人文精神。包括与人的沟通和理解能力，团队精神与合作能力，恒心和毅力，审美能力等。 竞赛形式和成绩评定 联赛分两个年龄组：初中组和高中组(普及组和提高组)。每组竞赛分两轮：初试和复试。 ．初试形式为笔试，侧重考察学生的计算机基础知识和编程的基本能力，并对知识面的广度进行测试。程序设计的描述语言采用Basic（2005年被取消）、C/C++或Pascal。各省市初试成绩在本赛区前百分之十五的学生进入复赛，其分数不计入复赛的成绩。初赛时间为10月的第二个星期六下午 2:30-4:30举行。 ．复试形式为上机，侧重考察学生对问题的分析理解能力，数学抽象能力，驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用Basic（2005年后被取消）、Pascal、C或C++。各省市竞赛的等第奖在复试的优胜者中产生。时间为 3小时。只进行一试，约在当年的11 月的第三个周六进行。 试题形式 每次联赛的试题分四组：初中组初试赛题；初中组复试赛题；高中组初试赛题；高中组复试赛题。其中，初中组初试赛题和高中组初试赛题类型相同，初中组复试赛题和高中组复试赛题类型相同，但初中组和高中组的题目不完全相同，高中组难度略高；以体现年龄特点和层次要求。 * 初试：初试全部为笔试，满分100分。试题由四部分组成： 1、选择题：共20题，每题1．5分，共30分。每题有4个备选方案。试题内容包括计算机基本组成与原理、计算机基本操作、信息科技与人类社会发展的关系等等。 2、问题求解题：共2题，每题5分，共10分。试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。答案以字符串方式给出，考生给出的答案与标准答案的字符串相同，则得分；否则不得分。 3、程序阅读理解题：共4题，每题8分，共32分。题目给出一段程序（没有关于程序功能的说明），有时也会给出程序的输入，要求考生通过阅读理解该段程序给出程序的输出。输出以字符串的形式给出，如果与标准答案一致，则得分；否则不得分。 4、程序完善题：共 2题，第一题10分，共4空，每空2.5分；第二题18分，共6空，每空3分。两题共28分。题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。填对的，则得分；否则不得分。 （2009年普及组试题为第一题5空，每空3分，第二题前三空每空3分，后两空每空2分） *复试：复试的题型和形式向全国信息学奥赛（NOI）靠拢，全部为上机编程题，但难度略低。复试为决出竞赛成绩的最后一个环节。题目包括 4道题，每题100分，共计400分。难度有易有难，既考虑普及面，又考虑选拔的梯度要求。每一道试题包括：题目、问题描述、样例说明（输入、输出及必要的说明）、数据范围（数据限制条件）。测试时，测试程序为每道题提供了5~10组测试数据，考生程序每答对一组得10~20 分；累计分即为该道题的得分。 试题的知识范围 考试内容主要包括：计算机发展史、计算机组成、计算机基本原理、计算机程序设计、计算机日常应用等。要求考生掌握至少一门高级程序设计语言（详见竞赛大纲）。为了保持竞赛内容的相对连续性，试题涵盖的知识点和题型至少60％应出现在普及类的参考书目中，其余内容可能超出该范围。 为了考核学生的基础知识、综合应用能力，激发学生的求知欲和创新思维，体现“与时俱进”的特点，竞赛题型在保持大纲相对稳定、优秀学生可能接受和理解的基础上，按照下述趋势适当变化 1、增大与课内知识结合的紧密度； 2、增大解题方法的多样性和灵活程度； 3、增大开放性试题的比例。 试题的知识范围具体如下： 一．初赛内容与要求： A．计算机的基本常识： 1．计算机和信息社会（信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化） 2．信息输入输出基本原理（信息交换环境、文字图形多媒体信息的输入输出方式） 3．信息的表示与处理（信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构） 4．信息的存储、组织与管理（存储介质、存储器结构、文件管理、数据库管理） 5．信息系统组成及互连网的基本知识（计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点） 6．人机交互界面的基本概念（窗口系统、人和计算机交流信息的途径（文本及交互操作）） 7．信息技术的新发展、新特点、新应用等。 B．计算机的基本操作： 1.Windows和LINUX的基本操作知识 2.互联网的基本使用常识（网上浏览、搜索和查询等） 3.常用的工具软件使用（文字编辑、电子邮件收发等） C．数据结构： 1．程序语言中基本数据类型(字符、整数、长整数、浮点) 2.浮点运算中的精度和数值比较 3．一维数组（串）与线性表 4．记录类型（PASCAL）/ 结构类型（C） D．程序设计： 1．结构化程序设计的基本概念 2．阅读理解程序的基本能力 3．具有将简单问题抽象成适合计算机解决的模型的基本能力 4．具有针对模型设计简单算法的基本能力 5．程序流程描述（自然语言/伪码/NS图/其他） 6．程序设计语言（PASCAL/C/C++，2003仍允许BASIC） E．基本算法处理： 1．初等算法（计数、统计、数学运算等） 2．排序算法（冒泡法、插入排序、合并排序、快速排序） 3．查找（顺序查找、二分法） 4．回溯算法 二、复赛内容与要求： 在初赛的内容上增加以下内容： A．数据结构： 1．指针类型 2．多维数组 3．单链表及循环链表 4．二叉树 5．文件操作（从文本文件中读入数据，并输出到文本文件中） B．程序设计 1．算法的实现能力 2．程序调试基本能力 3．设计测试数据的基本能力 4．程序的时间复杂度和空间复杂度的估计 C．算法处理 1．离散数学知识的应用（如排列组合、简单图论、数理逻辑） 2．分治思想 3．模拟法 4．贪心法 5．简单搜索算法（深度优先 广度优先）搜索中的剪枝 6．动态规划的思想及基本算法 评测环境 NOIP2010比赛环境规范依照使用Linux平台、统一编译器、提供多种集成开发环境选择的原则制定。 NOIP2010的比赛环境中，操作系统平台选择Linux；在固定的操作系统平台下，对应不同的语言，使用统一的编译器，消除编译器不同给选手带来的不利影响；对应每种语言，提供了多种集成开发环境，选手可以根据自己的习惯选择集成开发环境。 在全国评测时，评测环境保持与比赛环境的操作系统及编译器一致。也就是说全国评测时，使用与选手比赛时一致的平台对选手的程序进行评测，以消除平台不一致带来的不利影响。 以下是NOIP2010比赛环境要求的详细描述： 使用Linux操作系统平台： （1）Linux操作系统必须使用NOI linux,基于ubuntu开发； （2）Pascal语言，必须使用Free Pascal 2.0.4版本作为编译器； （3）C语言，必须使用gcc 3.2.2作为编译器； （4）C++语言，必须使用g++ 3.2.2作为编译器。 第十四届全国青少年信息学奥林匹克联赛初赛试题（提高组 Pascal 语言 二小时完成） ●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●● 一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案）。 1.在以下各项中，（）不是操作系统软件。 Symbian 2．微型计算机中，控制器的基本功能是（）。 A.控制机器各个部件协调工作 B.实现算术运算和逻辑运算 C.存储各种控制信息 D.获取外部信息 3.设字符串S=”Olympic”，S的非空子串的数目是（）。A.29 B.28 C.16 D.17 E.7 4．完全二叉树共有2*N-1个结点，则它的叶节点数是（）。 A.N-1 B.2*N C.N D.2N-1 E.N/2 5．将数组{8, 23, 4, 16, 77,-5, 53, 100}中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（）次。 A.4 B.5 C.6 D.7 E.8 6．设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈S，出栈的序列为b，d，c，f，e，a，则栈S的容量至少应该是（）。A.6 B.5 C.4 D.3 E.2 7.与十进制数28.5625相等的四进制数是（）。 A.123.21 B.131.22 C.130.22 D.130.21 E.130.20 8． 递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）的数据结构。 A.队列 B.多维数组 C.线性表 D.链表 E.栈 E.存放程序和数据 A.Solaris B.Linux C.Sybase D.Windows Vista E.9.TCP/IP是一组构成互联网基础的网络协议，字面上包括两组协议：传输控制协议（TCP）和网际协议（IP）。TCP/IP 协议把Internet网络系统描述成具有四个层次功能的网络模型,其中提供源节点和目的节点之间的信息传输服务，包括寻址和路由器选择等功能的是（）。 A.链路层 B．网络层 C.传输层 D.应用层 E.会话层 10． 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88, 92, 100}进行二分查找，等概率的情况下查找成功的平均查找长度（平均比较次数）是（）。A.35/11 B.34/11 C.33/11 D.32/11 E.34/10 二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。 11.在下列关于图灵奖的说法中，正确的有（）。 A.图灵奖是美国计算机协会于1966年设立的，专门奖励那些对计算机事业作出重要贡献的个人 B.图灵奖有“计算机界诺贝尔奖”之称 C.迄今为止，还没有华裔计算机科学家获此殊荣 D.图灵奖的名称取自计算机科学的先驱、英国科学家阿兰·图灵 12．计算机在工作过程中，若突然停电，（）中的信息不会丢失。A.硬盘 B.CPU C.ROM D.RAM 13.设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 14．Web2.0是近年来互联网的热门概念之一，其核心思想是互动与分享。下列网站中，（是典型的Web2.0应用。A.Sina B.Flickr C.Yahoo D.Google 15.(2008)10 +(5B)16的结果是（）。 A.(833)16 B.(2099)10 C.(4063)8(100001100011)2 16.二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），后根遍历是4 2 7 5 6 3 1，则该二叉树的可能的中根遍历是（）。）D.）A.4 2 1 7 5 3 6 B.2 4 1 7 5 3 6 C.4 2 1 7 5 6 3 D.2 4 1 5 7 3 6 17.面向对象程序设计（Object-Oriented Programming）是一种程序设计的方法论，它将对象作为程序的基本单元，将数据和程序封装在对象中，以提高软件的重用性、灵活性和扩展性。下面关于面向对象程序设计的说法中，正确的是（）。 A.面向对象程序设计通常采用自顶向下设计方法进行设计。 B.面向对象程序设计方法具有继承性（inheritance）、封装性（encapsulation）、多态性（polymorphism）等几大特点。 C.支持面向对象特性的语言称为面向对象的编程语言，目前较为流行的有C++、JAVA、C#等。 D.面向对象的程序设计的雏形来自于Simula语言，后来在SmallTalk语言的完善和标准化的过程中得到更多的扩展和对以前思想的重新注解。至今，SmallTalk语言仍然被视为面向对象语言的基础。 18.设T是一棵有n个顶点的树，下列说法正确的是（）。 A.T是连通的、无环的 B.T是连通的，有n-1条边 C.T是无环的，有n-1条边 D.以上都不对 19.NOIP竞赛推荐使用的语言环境有（）。 A.Dev-C++ B.Visual C++ C.free pascal D.Lazarus 20.在下列防火墙（firewall）的说法中，正确的有（）。 A.防火墙是一项协助确保信息安全的设备，其会依照特定的规则，允许或是限制数据通过 B.防火墙可能是一台专属的硬件或是安装在一般硬件上的一套软件 C.网络层防火墙可以视为一种 IP 数据包过滤器，只允许符合特定规则的数据包通过，其余的一概禁止穿越防火墙 D.应用层防火墙是在 TCP/IP的“应用层”上工作，可以拦截进出某应用程序的所有数据包 三．问题求解（共2题，每题5分，共计10分） 1．有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表所示，则城市1到城市6的最短距离为_____________。 2．书架上有21本书，编号从1到21，从其中选4本，其中每两本的编号都不相邻的选法一共有______种。 四．阅读程序写结果（共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.输入：2 1 3 输出:__________ 3．procedure f(a,b,c:integer);begin write(a, b, c, '/');if(a = 3)and(b = 2)and(c = 1)then exit;if b s:string;i,j,len,k:integer;begin read(s);len:=length(s);for i:=1 to len do if(ord(s[i])>= ord('A'))and(ord(s[i])<= ord('Z'))then s[i] := chr(ord(s[i])-ord('A')+ ord('a'));for i:=1 to len do if(ord(s[i]) 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 if i m:=5;for i:=1 to m do read(a[i]);read(n);ans:= FindKth(1,m,n);writeln(a[ans]);end.2．（矩阵中的数字）有一个n*n(1<=n<=5000)的矩阵a，对于1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1]。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵a中的一个数字k，找出k所在的行列（注意：输入数据保证矩阵中的数各不相同）。 var n,k,answerx,answery:integer;a:array[1..5000,1..5000] of integer;procedure FindKPosition;var i,j:integer;begin i:=n;j:=n;while j>0 do begin if a[n,j] < k then break;dec(j);end;① while a[i,j]<>k do begin while(②)and(i>1)do dec(i);while(③)and(j<=n)do inc(j);end;④ ⑤ end;var i,j:integer; begin read(n);for i:=1 to n do for j:=1 to n do read(a[i,j]);read(k);FindKPosition;writeln(answerx, ' ', answery);end. 第十九届（2013年）全国青少年信息学奥林匹克联赛初赛 答案 普及组Pascal语言试题 AABCD BBCAC AADAC CADAB 二、1.14 2.01 1 1三、1.3+5=8 2.6 3.7 4.4四、1.(1)n-p+i (2)a[i] (3)n (4)i-p+1 (5)a[i-p] 2.(1)cur (2)a[root].right_child (3)cur (4)upper_bound (5)1 第十二届全国青少年信息学奥林匹克联赛初赛试题及答案（普及组、C语言）普及组 C语言 二小时完成) 一、单项选择题(共20题，每题1.5分，共计30分。 1．在下面各世界顶级的奖项中，为计算机科学与技术领域做出杰出贡献的科学家设立的奖项是()。 A．沃尔夫奖 B．诺贝尔奖 C．菲尔兹奖 D．图灵奖 2．在下面各软件中，不属于NOIP竞赛(复赛)推荐使用的语言环境是()。 A．gcc/g++ B．Turbo Pascal C．RHIDE D．free pascal 3．以下断电之后仍能保存数据的有()。 A．寄存器 B．ROM C．RAM D．高速缓存 4．Linux是一种()。 A．绘图软件 B．程序设计语言 C．操作系统 D．网络浏览器 5．CPU是()的简称。 A．硬盘 B．中央处理器 C．高级程序语言 D．核心寄存器 6．在计算机中，防火墙的作用是()。 A．防止火灾蔓延 B．防止网络攻击 C．防止计算机死机 D．防止使用者误删除数据 7．在下列关于计算机语言的说法中，不正确的是()。 A．Pascal和C都是编译执行的高级语言 B．高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上 C．C++是历史上的第一个支持面向对象的计算机语言 D．与汇编语言相比，高级语言程序更容易阅读 8．在下列关于计算机算法的说法中，不正确的是()。 A．一个正确的算法至少要有一个输入 B．算法的改进，在很大程度上推进了计算机科学与技术的进步 C．判断一个算法的好坏的主要标准是算法的时间复杂性与空间复杂性 D．目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法 9．在下列各种排序算法中，不是以“比较”作为主要操作的算法是()。 A．选择排序 B．冒泡排序 C．插入排序 D．基数排序 10．在编程时(使用任一种高级语言，不一定是C)，如果需要从磁盘文件中输入一个很大的二维数组(例如1000*1000的double型数组)，按行读(即外层循环是关于行的)与按列读(即外层循环是关于列的)相比，在输入效率上()。 A．没有区别 B．按行读的方式要高一些 C．按列读的方式要高一些 D．取决于数组的存储方式 11．在C语言中，表达式21^2的值是()。 A．441 B．42 C．23 D．24 12．在C语言中，判断a不等于0且b不等于0的正确的条件表达式是()。 A．！a==0 || !b==0 B．!(a==0)&&(b==0)C．!(a==0&&b==0)D．a&&b 13．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为()。 A．1，2，3，4，5 B．1，2，4，5，7 C．1，4，3，7，6 D．1，4，3，7，2 14．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为()。 A．10 B．11 C．12 D．13 15．与十进制数1770对应的八进制数是()。 A．3350 B．3351 C．3352 D．3540 16．将5个数的序列排序，不论原先的顺序如何，最少都可以通过()次比较。完成从小到大的排序。 A．6 B．7 C．8 D．9 17．设A=B=D=ture，C=false，以下逻辑运算表达式值为真的有()。 A．(﹁A∧B)∨(C∧D)B．﹁((A∨B∨D)∧C)C．﹁A∧(B∨C∨D)D．(A∧B∧C)∨﹁D 18．(2010)16+(32)8的结果是()。 A．(8234)10 B．(202B)16 C．(20056)8 D．(100000000110)2 19．设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有()。 A．a,b,c,e,d B．b,c,a,e,d C．a,e,c,b,d D．d,c,e,b,a 20．已知6个结点的二叉树的先根+遍历是1 6(数字为结点的编号，以下同)，后根遍历是3 1，则该二叉树的可能的中根遍历是()。 A．3 5 B．3 6 C．2 6 D．2 二、问题求解(共2题，每题5分，共计10分) 1．(寻找假币)现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：________________________________________________________________。 2．(取石子游戏)现有5堆石子，石子数依次为3，5，7，19，50，甲乙两人轮流从任一堆中任取(每次只能取自一堆，不能不取)，取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略(即无论乙怎样取，甲只要不失误，都能获胜)？如果有，甲第一步应该在哪一堆里取多少？请写出你的结果：____________________________________________________________________。 三、阅读程序写结果(共4题，每题8分，共计32分) 1.#include int main() { int i,u[4],a,b,x,y=10; for(i=0;i<=3;i++) scanf(“%d“,&u[i]); a=(u[0]+u[1]+u[2]+u[3])/7; b=u[0]/((u[1]-u[2])/u[3]); x=(u[0]+a+2)-u[(u[3]+3)%4]; if(x>10) y+=(b*100-u[3])/(u[u[0]%3]*5); else y+=20+(b*100-u[3])/(u[u[0]%3]*5); printf(“%d,%d＼n“,x,y); return 0; } /*注：本例中，给定的输入数据可以避免分母为0或下标越界。*/ 输入：9 3 9 4 输出：________________ 2.#include main() { int i,j,m[]={2,3,5,7,13}; long t; for(i=0;i<=4;i++) { t=1; for(j=1;j t*=2; printf(“%ld “,(t*2-1)*t); } printf(“＼n“); } 输出：________________ 3.#include “stdio.h“ #define N int fun(char s[],char a,int n) { int j; j=n; while(a && j>0) j--; return j; } int main() { char s[N+1]; int k,p; for(k=1;k<=N;k++) s[k]=＇A＇+2*k+1; printf(“%d＼n“,fun(s,＇M＇,N)); } 输出：________________ 4.#include void digit(long n,long m) { if(m>0) printf(“%2ld“,n%10); if(m>1) digit(n/10,m/10); printf(“%2ld“,n%10); } main() { long x,x2; printf(“Input a number:＼n“); scanf(“%ld“,&x); x2=1; while(x2 x2*=10; x2/=10; digit(x,x2); printf(“＼n“); } 输入：9734526 输出：________________ 四、完善程序(前4空，每空2.5分，后6空，每空3分，共28分) 1．(全排列)下面程序的功能是利用递归方法生成从1到n(n<10)的n个数的全部可能的排列(不一定按升序输出)。例如，输入3，则应该输出(每行输出5个排列)： 123 132 213 231 321 312 程序： #include int n,a[10];/*a[1],a[2],…,a[n]构成n个数的一个排列*/ long count=0;/*变量count记录不同排列的个数，这里用于控制换行*/ void perm(int k) { int j,p,t; if(______①______) { count++; for(p=1;p<=n;p++) printf(“%1d“,a[p]);/* “%1d“ 中是数字1，不是字母l */ printf(“ “); if(______②______) printf(“＼n“); return; } for(j=k;j<=n;j++) { t=a[k]; a[k]=a[j];a[j]=t; ______③______; t=a[k]; ______④______; } } main() { int i; printf(“Entry n:＼n“); scanf(“%d“,&n); for(i=1;i<=n;i++) a[i]=i; ______⑤______; } 2.由键盘输入一个奇数P(P<100,000,000)，其个位数字不是5，求一个整数S，使P×S=1111...1(在给定的条件下，解s必存在)。要求在屏幕上依次输出以下结果： (1) S的全部数字。除最后一行外，每行输出50位数字。(2)乘积的数字位数。 例1：输入P=13，由于13*8547=111111，则应输出(1) 8547，(2) 例2：输入P=147，则输出结果应为(1) 7558578987******613(2) 42，即等式的右端有42个1。 程序： #include main() { long p,a,b,c,t,n; int bl; while(1) { printf(“输入p,最后一位为1或3或7或9：＼n“); scanf(“%ld“,&p); if((p%2!=0)&&(p%5!=0))/* 如果输入的数符合要求，结束循环 */ ______⑥______; } a=0; n=0; while(a { a=a*10+1; n++;/* 变量a存放部分右端项，n为右端项的位数 */ } t=0; do { b=a/p; printf(“%1ld“,b); t++; if(______⑦______) printf(“＼n“); c=______⑧______;a=______⑨______;n++; }while(c>0); printf(“＼nn=%ld＼n“,______⑩______); } 一、选择一个正确答案代码（A/B/C/D/E）,填入每题的括号内(每题1.5分,多选无分, 共30 分) 题号 ３ 选择 D B B C B B C A D D 题号 选择 C D C B C B B A C B 二、问题求解(共2题，每题5分，共计10分) 1.4次(1分)第一步：分成3组：27，27，26，将前2组放到天平上（4分）。 2.有获胜策略(1分)第1次在第5堆中取32颗石子(4分)。 三、阅读程序写结果(共4题，每题8分，共计32分) 1.10，10（对1个数给4分，无逗号扣1分） 2.6 28 496 8128 33550336 (前2个对1个数给1分，后3个对1个数给2分) 3.5 4.6 6（数字之间无空格扣2分） 四、完善程序(前4空，每空2.5分，后6空，每空3分，共28分) 1.① k==n ② count%5==0 ③ perm(k+1)④ a[k]=a[j]; a[j]=t ⑤ perm(1) 2.⑥ break ⑦ t%50==0 ⑧ a-p*b ⑨ c*10+1 ⑩ n-1第二篇：全国青少年信息学奥林匹克联赛
第三篇：第十四届全国青少年信息学(计算机)奥林匹克分区联赛初赛汇总
第四篇：第十九届(2013年)全国青少年信息学奥林匹克联赛初赛 答案
第五篇：第十二届全国青少年信息学奥林匹克联赛初赛试题及答案普及组、C语言
点击咨询 