NOIP试题+答案+解析学生版.docx
《NOIP试题+答案+解析学生版.docx》由会员分享，可在线阅读，更多相关《NOIP试题+答案+解析学生版.docx（20页珍藏版）》请在冰点文库上搜索。
NOIP试题+答案+解析学生版
第十三届全国青少年信息学奥林匹克联赛初赛试题
（普及组Pascal语言二小时完成）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一、单项选择题（共20题，每题1.5分，共计30分。
每题有且仅有一个正确答案。
）
1．在以下各项中，（）不是CPU的组成部分。
A．控制器B．运算器C．寄存器D．主板
2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。
A．二叉树B．多叉树C．哈希表D．二维表
3．在下列各项中，只有（）不是计算机存储容量的常用单位。
A．ByteB．KBC．UBD．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．gccB．g++C．TurboCD．FreePascal
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语言中，表达式（23or2xor5）的值是（）。
A．18B．1C．23D．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．243657B．241257C．243176D．243675
17．与十进制数1770对应的八进制数是（）。
A．3350B．3351C．3352D．3540
18．设A=B=True，C=D=False，一下逻辑运算表达式值为假的有（）。
A．（﹁A∧B）∨（C∧D∨A）B．﹁（（（A∧B）∨C）∧D）
C．A∧（B∨C∨D）∨DD．（A∧（D∨C））∧B
19．（2070）16+（34）8的结果是（）。
A．（8332）10B．（208A）16C．（0）2D．（20212）8
20．已知7个节点的二叉树的先根遍历是1245637（数字为节点的编号，以下同），中根遍历是4265173，则该二叉树的后根遍历是（）。
A．4652731B．4652137C．4231547D．4653172
二、问题求解（共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、programj301;
vari,a,b,c,x,y:
integer;
p:
array[0..4]ofinteger;
begin
y:
=20;
fori:
=0to4doread（p[i]）;
readln;
a:
=（p[0]+p[1]）+（p[2]+p[3]+p[4]）div7;
b:
=p[0]+p[1]div（（p[2]+p[3]）divp[4]）;
c:
=p[0]*p[1]divp[2];
x:
=a+b-p[（p[3]+3）mod4];
if（x>10）
theny:
=y+（b*100-a）div（p[p[4]mod3]*5）
else
y:
=y+20+（b*100-c）div（p[p[4]mod3]*5）;
writeln（x,',',y）;
end.
{注：
本例中，给定的输入数据可以避免分母为0或数组元素下表越界。
}
输入：
66553输出：
______________________
2、programj302;
vara,b:
integer;
varx,y:
^integer;
procedurefun（a,b:
integer）;
vark:
integer;
begink:
=a;a:
=b;b:
=k;end;
begin
a:
=3;b:
=6;
x:
=@a;y:
=@b;
fun（x^,y^）;
writeln（a,',',b）;
end.
输出：
_______________________________
3、programj303;
vara1:
array[1..50]ofinteger;
vari,j,t,t2,n,n2:
integer;
begin
n:
=50;
fori:
=1tondoa1[i]:
=0;
n2:
=round（sqrt（n））;
fori:
=2ton2do
if（a1[i]=0）then
begin
t2:
=ndivi;
forj:
=2tot2doa1[i*j]:
=1;
end;
t:
=0;
fori:
=2tondo
if（a1[i]=0）then
begin
write（i:
4）;inc（t）;
if（tmod10=0）thenwriteln;
end;
writeln;
end.
输出：
_____________________________________________
_____________________________________________
4、Programj304;
Typestr1=string[100];
Str2=string[200];
Var
S1:
str1;s2:
str2;
Functionisalpha（c:
char）:
Boolean;
Vari:
integer;
Begin
i:
=ord（c）;
if（（i>=65）and（i<=90））or（（i>=97）and（i<=122））then
isalpha:
=true
elseisalpha:
=false;
end;
functionisdigit（c:
char）:
Boolean;
vari:
integer;
begin
i:
=ord（c）;if（i>=48）and（i<=57）thenisdigit:
=true
elseisdigit:
=false;
end;
procedureexpand（s1:
str1;vars2:
str2）;
vari,j:
integer;a,b,c:
char;
begin
j:
=1;c:
=char
（1）;i:
=0;
while（i<=ord（s1[0]））do
begininc（i）;c:
=s1[i];
ifc='-'thenbegin{1}
a:
=s1[i-1];b:
=s1[i+1];
if（isalpha（a）andisalpha（b））or（isdigit（a）andisdigit（b））thenbegin
dec（j）;
while（ord（upcase（a））begin
s2[j]:
=a;inc（j）;inc（a）;end;
end
else
begins2[j]:
=c;inc（j）;end;
end{1}
elsebegins2[j]:
=c;inc（j）;end;end;s2[0]:
=char（j-2）;end;
beginreadln（s1）;expand（s1,s2）;writeln（s2）;
end.
输入：
wer2345d-h454-82qqq输出：
__________________________
四、完善程序（前4空，每空2.5分，后6空，每空3分，共28分）。
1、（求字符的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入-1终止程序。
请将程序补充完整。
Programj401;
typestr1=string[100];
varline:
str1;kz:
integer;
procedurereverse（vars:
str1）;
varI,j:
integer;t:
char;
begin
i:
=1;j:
=length（s）;
while（it:
=s[i];s[i]:
=s[j];s[j]:
=t;
;
;
end;
end;
begin
writeln（‘continue?
-1forend.’）;
readln（kz）;
while（
）do
begin
readln（line）;
;
writeln（line）;
writeln（‘continue?
-1forend.’）;
readln（kz）;
end;
end.
2
2
3
3
2
-1
1
3
4
1
1
5
4
4
5
5
2、（棋盘覆盖问题）在一个2k×2k个方格组成的棋盘中恰有一个方格与其它方格不同（图中标记为-1的方格），称之为特殊方格。
现用L型（占3个小方格）纸片覆盖棋盘上除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是（4k-1）/3。
在下表给出的一个覆盖方案中，k=2，相同的3各数字构成一个纸片。
下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角，递归进行。
请将程序补充完整。
Programj402;
typearr1=array[1..65]ofinteger;
arr2=array[1..65]ofarr1;
varboard:
arr2;tile:
integer;size,dr,dc:
integer;
procedurechessboard（tr,tc:
integer;dr,dc:
integer;varsize:
integer）;
vart,s:
integer;
begin
if（size=1）then
;
t:
=tile;inc（tile）;
s:
=sizediv2;
if
thenchessboard（tr,tc,dr,dc,s）elsebegin
board[tr+s-1]:
=t;
;
end;
if（dr=tc+s）thenchessboard（tr,tc+s,dr,dc,s）
elsebeginboard[tr+s-1][tc+s]:
=t;
;end;
if（dr>=tr+s）and（dcboard[tr+s][tc+s]:
=t;
;end;
if（dr>=tr+s）and（dc>=tc+s）thenchessboard（tr+s,tc+s,dr,dc,s）
elsebeginboard[tr+s][tc+s]:
=t;
;end;
end;
procedureprt1（n:
integer）;
varI,j:
integer;
begin
forI:
=1tondobegin
forj:
=1tondowrite（board[i][j]:
3）;
writeln;
end;
end;
begin
writeln（‘inputsize（4/8/16/64）:
’）;
readln（size）;writeln（‘inputthepositionofspecialblock（x,y）:
’）;
readln（dr,dc）;board[dr][dc]:
=-1;
tile:
=1;chessboard（1,1,dr,dc,size）;prt1（size）;
end.
NOIP2007年普及组（Pascal语言）参考答案与评分标准
一、单项选择题：
（每题1.5分）
题号
1
2
3
4
5
6
7
8
9
10
答案
D
D
C
B
B
B
B
C
C
A
题号
11
12
13
14
15
16
17
18
19
20
答案
C
A
A
A
B
D
C
D
A
A
二、问题求解：
（每题5分）
1．902．210
三、阅读程序写结果
1.15,46（对1个数给4分，无逗号扣1分）
2. 3,6
3. 2 3 5 7 11 13 17 19 23 29
31 37 41 43 47
4. wer2345defghqqq
四、完善程序（前4空（①--④），每空2.5分，后6空（⑤--⑩），每空3分）
（说明：
以下各程序填空可能还有一些等价的写法，各省可请本省专家审定和上机验证，不一定上报科学委员会审查）
1．
① inc（i）或i:
=i+1
② dec（j）或j:
=j-1
③ kz<>-1
④ reverse（line）
2.
⑤exit
⑥（dr⑦chessboard（tr,tc,tr+s-1,tc+s-1,s）
⑧chessboard（tr,tc+s,tr+s-1,tc+s,s）
⑨chessboard（tr+s,tc,tr+s,tc+s-1,s）
⑩chessboard（tr+s,tc+s,tr+s,tc+s,s）
NOIP2007初赛（普及组）解题报告
作为全国性的竞赛，命题自然要对选手的学习与训练发挥一定的导向的作用。
从弘扬信息学奥林匹克文化的角度讲，在对选手的要求方面，是否应突出以下几点：
（1）选手必须掌握程序设计的常用方法与技巧。
（2）选手应对计算机的软硬件环境、主要应用领域、目前流行的新技术有一些初步的了解。
（3）选手应对计算机科学与技术的一些经典结果有一些初步的了解。
（4）选手必须具有较强的分析问题、解决问题的能力。
面对从未见过的问题，能够找出解决问题的正确途径。
一、单项选择题
2．在关系数据库中，存放在数据库中的数据的逻辑结构以（）为主。
A.二叉树B.多叉树C.哈希表D.二维表
答案：
D
说明：
作为计算机科学与技术的重要分支之一，数据库的有关知识在中学信息技术教材中占有较大的比重，当前，大多数计算机应用领域都需要有数据库系统的支撑。
8.冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。
冗余数据往往会造成数据的不一致，例如，上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。
下面关于冗余数据的说法中，正确的是（）。
A.应该在数据库中消除一切冗余数据
B.用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数据
C.为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检验
D.做相容性检验会降低效率，可以不理睬数据库中的冗余数据
答案：
C
说明：
冗余数据是数据库理论中的重要概念。
本题试图引导选手在学习数据库的时候，除了要掌握一般的操作方法，还要做更深层次的思考。
关系数据库的规范化理论主要是为了消除冗余数据，但冗余数据的消除又造成了查询效率的降低，目前广泛使用的分布式数据库在提高系统的可靠性、安全性、数据分布场地的透明性等方面充分利用了冗余数据。
11.在下列关于计算机语言的说法中，正确的有（）。
A.高级语言比汇编语言更高级，是因为它的程序的运行效率更高
B.随着Pascal、C等高级语言的出现，机器语言和汇编语言已经退出了历史舞台
C.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上
D.C是一种面向对象的高级计算机语言
答案：
C
说明：
选择A:
高级语言比汇编语言更高级，是针对计算机语言的发展阶段讲的。
人们使用高级语言编写程序，要比汇编语言容易得多。
优秀的程序设计人员用汇编语言编写的程序，往往效率更高一些。
选择B:
当今，机器语言和汇编语言并没有退出历史舞台。
一些和硬件操作（特别是涉及到外部设备的操作）关系十分密切的程序，往往还用汇编语言编写。
12.近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。
在下列关于递归算法的说法中，正确的是（）。
A.在1977年前后形成标准的计算机高级语言“FORTRAN77”禁止在程序使用递归，原因之一是该方法可能会占用更多的内存空间
B.和非递归算法相比，解决同一个问题，递归算法一般运行得更快一些
C.对于较复杂的问题，用递归方式编程一般比非递归方式更难一些
D.对于已经定义好的标准数学函数sin（x），应用程序中的语句“y=sin（sin（x））;”就是一种递归调用
答案：
A
说明：
如果一个选手对递归有了较深入的理解，并能用来解决一些较复杂的问题，就说明他有了应对NOIP赛题的基本能力。
选择D中的“y=sin（sin（x））;”一般称为函数的嵌套引用，而不是递归调用。
13.一个无法靠自身的控制终止的循环称为“死循环”，例如，在C语言程序中，语句“while
（1）printf（“*”）;”就是一个死循环，运行时它将无休止地打印*号。
下面关于死循环的说法中，只有（）是正确的。
A.不存在一种算法，对任何一个程序及相应的输入数据，都可以判断是否会出现死循环，因而，任何编译系统都不做死循环检验
B．有些编译系统可以检测出死循环
C.死循环属于语法错误，既然编译系统能检查各种语法错误，当然也应该能检查出死循环
D.死循环与多进程中出现的“死锁”差不多，而死锁是可以检测的，因而，死循环也可以检测的
答案：
A
说明：
这是可计算理论的一个经典结果：
判断“死循环问题”是一个著名的不可计算问题。
也就是说，不论你用运行速度多快的计算机、用多大的内存、用多少运算时间，也不能对这个问题给出肯定的答复。
答案C的大前提是错误的，死循环一般属于逻辑错误，而不是语法错误。
答案D的大前提也是错误的，死循环与死锁是本质不同的问题，不是差不多。
二．问题求解
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）=______
升级会员 