2024年8月26日发(作者：公冶春海)

第十三届全国青少年信息学奥林匹克联赛初赛试题

（ 普及组 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

NOIP2007 初赛试题（普及组 Pascal）

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．（0）

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[i]);

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)

© 中国计算机学会 2007

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[i]:=0;

n2:=round(sqrt(n));

for i:=2 to n2 do

if (a1[i]=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[i]=0) then

begin

write(i:4); inc(t);

if (t mod 10=0) then writeln;

end;

writeln;

end.

NOIP2007 初赛试题（普及组 Pascal）

输出：_____________________________________________

_____________________________________________

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[i];

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 输出：__________________________

© 中国计算机学会 2007

四、完善程序（前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[i]; s[i]:=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、（棋盘覆盖问题）在一个2

k

×2

k

个方格组成的棋盘中恰有一个方格与其它方格不同（图

中标记为-1的方格），称之为特殊方格。现用L型（占3个小方格）纸片覆盖棋盘上除特殊

方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是（4

k

-1）/3。在下表给出的

一个覆盖方案中，k=2，相同的3各数字构成一个纸片。

下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下

角、右下角，递归进行。请将程序补充完整。

2 2 3 3

2 -1 1 3

4 1 1 5

4 4 5 5

NOIP2007 初赛试题（普及组 Pascal）

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=tc+s) then chessboard(tr,tc+s,dr,dc,s)

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[i][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.

© 中国计算机学会 2007

NOIP2007年普及组（Pascal语言）参考答案与评分标准

一、单项选择题：（每题1.5分）

题号

答案

题号

答案

1

D

11

C

2

D

12

A

3

C

13

A

4

B

14

A

5

B

15

B

6

B

16

D

7

B

17

C

8

C

18

D

9

C

19

A

10

A

20

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

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 初赛试题（普及组 Pascal）

NOIP2007初赛（普及组）解题报告

作为全国性的竞赛，命题自然要对选手的学习与训练发挥一定的导向的作用。从弘扬信

息学奥林匹克文化的角度讲，在对选手的要求方面，是否应突出以下几点：

（1）选手必须掌握程序设计的常用方法与技巧。

（2）选手应对计算机的软硬件环境、主要应用领域、目前流行的新技术有一些初步的了

解。

（3）选手应对计算机科学与技术的一些经典结果有一些初步的了解。

（4）选手必须具有较强的分析问题、解决问题的能力。面对从未见过的问题，能够找出

解决问题的正确途径。

一、 单项选择题

2．在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。

A. 二叉树 B. 多叉树 C.哈希表 D.二维表

答案：D

说明：作为计算机科学与技术的重要分支之一，数据库的有关知识在中学信息技术教材中占

有较大的比重，当前，大多数计算机应用领域都需要有数据库系统的支撑。

8. 冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文

和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往

往会造成数据的不一致，例如，上面4个数据如果都是输入的，由于操作错误使总分不等

于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（ ）。

A. 应该在数据库中消除一切冗余数据

B. 用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数

据

C. 为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检

验

D. 做相容性检验会降低效率，可以不理睬数据库中的冗余数据

答案： C

说明：冗余数据是数据库理论中的重要概念。本题试图引导选手在学习数据库的时候，除了

要掌握一般的操作方法，还要做更深层次的思考。关系数据库的规范化理论主要是为了消除

冗余数据，但冗余数据的消除又造成了查询效率的降低，目前广泛使用的分布式数据库在提

高系统的可靠性、安全性、数据分布场地的透明性等方面充分利用了冗余数据。

11. 在下列关于计算机语言的说法中，正确的有（ ）。

© 中国计算机学会 2007

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

说明：这是可计算理论的一个经典结果：判断“死循环问题”是一个著名的不可计算问题。

也就是说，不论你用运行速度多快的计算机、用多大的内存、用多少运算时间，也不能对这

个问题给出肯定的答复。

NOIP2007 初赛试题（普及组 Pascal）

答案D的大前提也是错误的，死循环与死锁是本质不同的问题，不是差不多。

答案C的大前提是错误的，死循环一般属于逻辑错误，而不是语法错误。

二．问题求解

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)，再分这两种情况对

原固定的数进行分析）。

答案：90

说明：将6单独放到1个子集的方法数是S(5,2)，即在其余的2个子集中放其余5个数。

将6不单独放到1个子集的方法数是3*S(5,3)，即在3个子集里先放好其余5个数。然

后将6依次放入3个子集中的某一个。即S(6,3)=S(5,2)+3*S(5,3)，类似可得：

S(5,2)=S(4,1)+2*S(4,2)，

S(5,3)=S(4,2)+3*S(4,3)，

已知S(4,2)=7，容易看出，S(4,1)=1，S(4,3)=6（这时，只有一个子集含有两个数，

共6种可能：

(12)，(13)，(14)，(23)，(24)，(34)）。

于是，S(5,2)=1+2*7=15，S(5,3)=7+3*6=25，S(6,3)=15+3*25=90。

S(n,k)通常称为第2类Stirling数，见《组合数学引论》，孙淑玲等著）

2．（最短路线）某城市的街道是一个很规整的矩形网格（见下图），有7条南北向的

纵街，5条东

西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？

_________________.

B

A

答案： 210

© 中国计算机学会 2007

解法1：利用递推公式。设m条纵街与n条横街的最短走法为A(m,n)，易知

A(m,1)=A(1,n)=1，当m>1且n>1时，由于第1步有向上、向右两种走法，因此有

A(m,n)=A(m-1,n)+A(m,n-1)，因此可利用下面的表格计算A(5,7)：

M

1

2

3

4

5

1

1

1

1

1

2

1

2

3

4

3

1

3

6

10

4

1

4

10

20

5

1

5

15

35

6

1

6

21

56

7

1

7

28

84

1 5 15 35 70 126 210

在上表中，除第1行与第1列外，每个格中的数都等于该格上方的数与该格左边的数

之和。注意在题目的表格中，A点的位置是（5,7），B点的位置是（1,1）。

解法2：利用组合公式。由于初中学生还没有学过排列组合，下面的方法仅供参考。对

于m条纵街与n条横街，任何一条可行的路径都包括n-1段纵街（由n条横街分割而成）

和m-1段横街（由m条纵街分割而成）构成，我们可以把一条可行的路径理解为一条线段，

上面共有(n-1)+(m-1)个连续的等距的小格，我们从中选n-1个小格走纵街，其余的m-1

个小格走横街，于是，不同的选择方法共有

1m114

C

(

n

n





C

(

5

5



1)(m1)

C

(n1)(m1)

,于是，所求的解为

1)(71)

C

10



10!10987

210

4!6!1234

三．阅读程序写结果

3．

答案： 2 3 5 7 11 13 17 19 23 29

31 37 41 43 47

说明：此题即利用筛法求素数。

4.

答案： wer2345defghqqq

说明：此题为字符串的扩展操作，对于形如“d-h”、“4-8”的三字符串，去掉中间的减号，

将字母或数字连续写出，即分别输出为“defgh”、“45678”。

NOIP2007 初赛试题（普及组 Pascal）

四．完善程序

1．

说明： 本题是根据计算机名著《C程序设计语言（第2版）》中的例题改写的，该书第2

作者e是C语言的发明人。

2. （棋盘覆盖问题）在一个

2

k

2

k

个方格组成的棋盘中恰有一个方格与其他方格不

同（图中标记为-1的方格），称之为特殊方格。现用L型（占3个小格）纸片覆盖棋盘上

除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是

(41)/3

。在下表

给出的一个覆盖方案中，k=2，相同的3个数字构成一个纸片。

下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下

角、右下角，递归进行。请将程序补充完整。

2

2

4

4

2

-1

1

4

3

1

1

5

3

3

5

5

k

说明：此题选自“王晓东：计算机算法设计与分析（第2版），2.6 棋盘覆盖”。由于采用

分治法，四个模块（左上角、右上角、左下角、右下角）有很多相似之处。选择⑤是递归

结束的处理。为了确定选择⑥，只须对照后面几个if()语句就可以了。而选择⑦至⑩是递

归进一步扩展的处理，弄清每个形参的含义，实参也就不难确定了。虽然程序较长，但很有

规律，如果能较好地把握递归，程序就不难理解了。

© 中国计算机学会 2007

2024年8月26日发(作者：公冶春海)

第十三届全国青少年信息学奥林匹克联赛初赛试题

（ 普及组 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

NOIP2007 初赛试题（普及组 Pascal）

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．（0）

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[i]);

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)

© 中国计算机学会 2007

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[i]:=0;

n2:=round(sqrt(n));

for i:=2 to n2 do

if (a1[i]=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[i]=0) then

begin

write(i:4); inc(t);

if (t mod 10=0) then writeln;

end;

writeln;

end.

NOIP2007 初赛试题（普及组 Pascal）

输出：_____________________________________________

_____________________________________________

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[i];

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 输出：__________________________

© 中国计算机学会 2007

四、完善程序（前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[i]; s[i]:=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、（棋盘覆盖问题）在一个2

k

×2

k

个方格组成的棋盘中恰有一个方格与其它方格不同（图

中标记为-1的方格），称之为特殊方格。现用L型（占3个小方格）纸片覆盖棋盘上除特殊

方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是（4

k

-1）/3。在下表给出的

一个覆盖方案中，k=2，相同的3各数字构成一个纸片。

下面给出的程序使用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下

角、右下角，递归进行。请将程序补充完整。

2 2 3 3

2 -1 1 3

4 1 1 5

4 4 5 5

NOIP2007 初赛试题（普及组 Pascal）

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=tc+s) then chessboard(tr,tc+s,dr,dc,s)

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[i][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.

© 中国计算机学会 2007

NOIP2007年普及组（Pascal语言）参考答案与评分标准

一、单项选择题：（每题1.5分）

题号

答案

题号

答案

1

D

11

C

2

D

12

A

3

C

13

A

4

B

14

A

5

B

15

B

6

B

16

D

7

B

17

C

8

C

18

D

9

C

19

A

10

A

20

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

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 初赛试题（普及组 Pascal）

NOIP2007初赛（普及组）解题报告

作为全国性的竞赛，命题自然要对选手的学习与训练发挥一定的导向的作用。从弘扬信

息学奥林匹克文化的角度讲，在对选手的要求方面，是否应突出以下几点：

（1）选手必须掌握程序设计的常用方法与技巧。

（2）选手应对计算机的软硬件环境、主要应用领域、目前流行的新技术有一些初步的了

解。

（3）选手应对计算机科学与技术的一些经典结果有一些初步的了解。

（4）选手必须具有较强的分析问题、解决问题的能力。面对从未见过的问题，能够找出

解决问题的正确途径。

一、 单项选择题

2．在关系数据库中，存放在数据库中的数据的逻辑结构以（ ）为主。

A. 二叉树 B. 多叉树 C.哈希表 D.二维表

答案：D

说明：作为计算机科学与技术的重要分支之一，数据库的有关知识在中学信息技术教材中占

有较大的比重，当前，大多数计算机应用领域都需要有数据库系统的支撑。

8. 冗余数据是指可以由其他数据导出的数据，例如，数据库中已存放了学生的数学、语文

和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看作冗余数据。冗余数据往

往会造成数据的不一致，例如，上面4个数据如果都是输入的，由于操作错误使总分不等

于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中，正确的是（ ）。

A. 应该在数据库中消除一切冗余数据

B. 用高级语言编写的数据处理系统，通常比用关系数据库编写的系统更容易消除冗余数

据

C. 为了提高查询效率，在数据库中可以适当保留一些冗余数据，但更新时要做相容性检

验

D. 做相容性检验会降低效率，可以不理睬数据库中的冗余数据

答案： C

说明：冗余数据是数据库理论中的重要概念。本题试图引导选手在学习数据库的时候，除了

要掌握一般的操作方法，还要做更深层次的思考。关系数据库的规范化理论主要是为了消除

冗余数据，但冗余数据的消除又造成了查询效率的降低，目前广泛使用的分布式数据库在提

高系统的可靠性、安全性、数据分布场地的透明性等方面充分利用了冗余数据。

11. 在下列关于计算机语言的说法中，正确的有（ ）。

© 中国计算机学会 2007

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

说明：这是可计算理论的一个经典结果：判断“死循环问题”是一个著名的不可计算问题。

也就是说，不论你用运行速度多快的计算机、用多大的内存、用多少运算时间，也不能对这

个问题给出肯定的答复。

NOIP2007 初赛试题（普及组 Pascal）

答案D的大前提也是错误的，死循环与死锁是本质不同的问题，不是差不多。

答案C的大前提是错误的，死循环一般属于逻辑错误，而不是语法错误。

二．问题求解

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)，再分这两种情况对

原固定的数进行分析）。

答案：90

说明：将6单独放到1个子集的方法数是S(5,2)，即在其余的2个子集中放其余5个数。

将6不单独放到1个子集的方法数是3*S(5,3)，即在3个子集里先放好其余5个数。然

后将6依次放入3个子集中的某一个。即S(6,3)=S(5,2)+3*S(5,3)，类似可得：

S(5,2)=S(4,1)+2*S(4,2)，

S(5,3)=S(4,2)+3*S(4,3)，

已知S(4,2)=7，容易看出，S(4,1)=1，S(4,3)=6（这时，只有一个子集含有两个数，

共6种可能：

(12)，(13)，(14)，(23)，(24)，(34)）。

于是，S(5,2)=1+2*7=15，S(5,3)=7+3*6=25，S(6,3)=15+3*25=90。

S(n,k)通常称为第2类Stirling数，见《组合数学引论》，孙淑玲等著）

2．（最短路线）某城市的街道是一个很规整的矩形网格（见下图），有7条南北向的

纵街，5条东

西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？

_________________.

B

A

答案： 210

© 中国计算机学会 2007

解法1：利用递推公式。设m条纵街与n条横街的最短走法为A(m,n)，易知

A(m,1)=A(1,n)=1，当m>1且n>1时，由于第1步有向上、向右两种走法，因此有

A(m,n)=A(m-1,n)+A(m,n-1)，因此可利用下面的表格计算A(5,7)：

M

1

2

3

4

5

1

1

1

1

1

2

1

2

3

4

3

1

3

6

10

4

1

4

10

20

5

1

5

15

35

6

1

6

21

56

7

1

7

28

84

1 5 15 35 70 126 210

在上表中，除第1行与第1列外，每个格中的数都等于该格上方的数与该格左边的数

之和。注意在题目的表格中，A点的位置是（5,7），B点的位置是（1,1）。

解法2：利用组合公式。由于初中学生还没有学过排列组合，下面的方法仅供参考。对

于m条纵街与n条横街，任何一条可行的路径都包括n-1段纵街（由n条横街分割而成）

和m-1段横街（由m条纵街分割而成）构成，我们可以把一条可行的路径理解为一条线段，

上面共有(n-1)+(m-1)个连续的等距的小格，我们从中选n-1个小格走纵街，其余的m-1

个小格走横街，于是，不同的选择方法共有

1m114

C

(

n

n





C

(

5

5



1)(m1)

C

(n1)(m1)

,于是，所求的解为

1)(71)

C

10



10!10987

210

4!6!1234

三．阅读程序写结果

3．

答案： 2 3 5 7 11 13 17 19 23 29

31 37 41 43 47

说明：此题即利用筛法求素数。

4.

答案： wer2345defghqqq

说明：此题为字符串的扩展操作，对于形如“d-h”、“4-8”的三字符串，去掉中间的减号，

将字母或数字连续写出，即分别输出为“defgh”、“45678”。

NOIP2007 初赛试题（普及组 Pascal）

四．完善程序

1．

说明： 本题是根据计算机名著《C程序设计语言（第2版）》中的例题改写的，该书第2

作者e是C语言的发明人。

2. （棋盘覆盖问题）在一个

2

k

2

k

个方格组成的棋盘中恰有一个方格与其他方格不

同（图中标记为-1的方格），称之为特殊方格。现用L型（占3个小格）纸片覆盖棋盘上

除特殊方格的所有部分，各纸片不得重叠，于是，用到的纸片数恰好是

(41)/3

。在下表

给出的一个覆盖方案中，k=2，相同的3个数字构成一个纸片。

下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下

角、右下角，递归进行。请将程序补充完整。

2

2

4

4

2

-1

1

4

3

1

1

5

3

3

5

5

k

说明：此题选自“王晓东：计算机算法设计与分析（第2版），2.6 棋盘覆盖”。由于采用

分治法，四个模块（左上角、右上角、左下角、右下角）有很多相似之处。选择⑤是递归

结束的处理。为了确定选择⑥，只须对照后面几个if()语句就可以了。而选择⑦至⑩是递

归进一步扩展的处理，弄清每个形参的含义，实参也就不难确定了。虽然程序较长，但很有

规律，如果能较好地把握递归，程序就不难理解了。

© 中国计算机学会 2007