您所在位置：主题：[讨论]第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
sirvipceo
[专家分：0] 发布于 2005-04-03 19:04:00
第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
（提高组PASCAL语言 二小时完成）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一． 选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1.下列无符号数中，最小的数是（ ）
A.（11011001）2 B.(75)10 C.(37)8 D.(2A)16
2.在外部设备中，绘图仪属于（ ）
A. 输入设备 B.输出设备 C. 辅（外）存储器 D.主（内）存储器
3.计算机主机是由CPU与（ ）构成的
A. 控制器 B. 输入、输出设备 C. 运算器 D.内存储器
4.计算机病毒的特点是（ ）
A. 传播性、潜伏性、易读性与隐蔽性 B. 破坏性、传播性、潜伏性与安全性
C. 传播性、潜伏性、破坏性与隐蔽性 D. 传播性、潜伏性、破坏性与易读性
5.WINDOWS 9X是一种（ ）操作系统
A. 单任务字符方式 B. 单任务图形方式 C. 多任务字符方式 D. 多任务图形方式
6.Internet的规范译名应为（ ）
A. 英特尔网 B. 因特网 C. 万维网 D. 以太网
7.计算机网络是一个（ ）系统
A.管理信息系统 B.管理数据系统 C.编译系统 D. 在协议控制下的多机互连系统
8.计算机系统总线上传送的信号有（ ）
A.地址信号与控制信号 B. 数据信号、控制信号与地址信号
C.控制信号与数据信号 D. 数据信号与地址信号
9.计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。 已知64位的奔腾处理器一次能处理64个信息位，相当于（ ）字节。
A.8个 B.1个 C.16个 D. 2个
10.某种计算机的内存容量是640K，这里的640K容量是指（ ）个字节
A.640 B. 640*1000 C. 640*1024 D. 640*1024*1024
11.下面哪些计算机网络不是按覆盖地域划分的（ ）
A.局域网 B. 都市网 C.广域网 D. 星型网
12.在有N个叶子节点的哈夫曼树中，其节点总数为（ ）
A.不确定 B. 2N-1 C. 2N+1 D. 2N
13.已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内
存时是从地址SA开始连续按行存贮分配的。
试问：A（5，8）的起始地址为（ ）
A.SA+141 B. SA+180 C. SA+222 D. SA+225
14.不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（ ）
A.快存/辅存/主存 B. 外存/主存/辅存 C. 快存/主存/辅存 D. 主存/辅存/外存
15.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（ ）个单元。
A.1000 B. 10 C. 100 D. 500
16.请仔读下列程序段：
PASCAL语言
Var
a:array[1..3,1..4]of integer;1631638
b:array[1..4,1..3]of integer;
x,y:integer;
begin
for x:=1to3do
for y:=1to4do
a[x,y]:=x-y;
for x:=4 downto 1 do
for y:=1 to 3 do
b[x,y]:=a[y,x];
writeln(b[3,2]);
end.
BASIC语言
DIM A(3,4),B(4,3)
FOR X=1 TO 3
FOR Y=1 TO 4
A(X,Y)=X-Y
NEXT Y,X
FOR X=4 TO 1 STEP --1
FOR Y=1 TO 3
B(X,Y)=A(Y,X)
NEXT Y,X
PRINT B(3,2)
END
上列程序段的正确揄出是（ ）
A.-1 B. -2 C. -3 D. -4
17.线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）
A.必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
18.下列叙述中，正确的是（ ）
A.线性表的线性存贮结构优于链表存贮结构 B.队列的操作方式是先进后出
C.栈的操作方式是先进先出 D. 二维数组是指它的每个数据元素为一个线性表的线性表
19.电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类；
一类是两端的小鸟相同；另一类则是两端的小鸟不相同。
已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（ ）。
A.奇数 B. 偶数 C. 可奇可偶 D. 数目固定
20.一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每
一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，内屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（ ）
A.（Y*80+X）*2-1 B.（（Y-1）*80+X-1）*2
C.（Y*80+X-1）*2 D.（（Y-1）*80+X）*2-1
二.问题求解：（6+6=12分）
1.已知，按中序遍历二叉树的结果为：abc
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2.设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。
三、阅读程序，并写出正确的运行结果（每题10分，共20分）
1.PROGRAM NOI_003;
CONST N=7; M=6;
VAR I,J,X0,Y0,X1,Y1,X2,Y2:INTEGER;
D:REAL; P:BOOLEAN; G:ARRAY[0..N,0..M] OF 0..1;
FUNCTION DISP(X1,Y1,X2,Y2:INTEGER):REAL;
BEGIN DISP:=SQRT((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); END;
BEGIN
FOR I:=0 T0 N DO FOR J:=0 TO M DO G[I,J]:=0
READLN(X1,Y1,X2,Y2); G[X1,Y1]:=1; G[X2,Y2]:=1; P:=TRUE;
WHILE P DO
BEGIN
P:=FALSE; D:=DISP(X1,Y1,X2,Y2); X0:=X1; Y0:=Y1;
FOR I:=4 TO N DO FOR J:=0 TO M DO
IF (D>DISP(I,J,X2,Y2))AND(G[I,J]=0)THEN
BEGIN D:=DISP(I,J,X2,Y2); X0:=I; Y0:=J; END;
IF(X0<>X1) OR (Y0<>Y1) THEN
BEGIN X1:=X0; Y1:=Y0; P:=TRUE; G[X1,Y1]:=1; END;
D:=DISP(X1,Y1,X2,Y2); X0:=X2; Y0:=Y2;
FOR I:=0 TO 3 DO FOR J:=0 TO M DO
IF（D<DISP(X1,Y1,I,J)AND(G[I,J]=0) THEN
BEGIN D:=DISP(X1,Y1,I,J); X0:=I; Y0:=J END;
IF(X0<>X2)OR(Y0<>Y2) THEN
BEGIN X2:=X0;Y2=Y0;P:=TRUE; G[X2,Y2]:=1; END;
END; WRITELN(X1,Y1,X2,Y2)
END.
输入：7 6 0 0 输出：
2.PROGRAM NOI_002;
VAR I,J,L,N,K,S,T:INTEGER; B:ARRAY[1..10] OF 0..9;
BEGIN
READLN(L,N); S:=L; K:=1; T:=L;
IF N>L THEN BEGIN
WHILE S<N DO
BEGIN K:=K+1;T:=T*L;S:=S+T END;
S:=S-T;N:=N-S-1;
FOR I:=1 TO 10 DO B[I]:=0;
J:=11;
WHILE N>0 DO
BEGIN J:=J-1; B[J]:=N MOD L; N:=N DIV L END;
FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD(’A ’)+B[I]));
READLN;
END
ELSE WRITELN(CHR(ORD(’A’)+N-1))
END
输入： 4 167 输出：
四、完善程序（共38分）
1.问题描述：
将2n个0和2n个1，排成一个圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。
例如，当n=2时，即22个0和22个1排成如下一圈：
比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，…可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明
以N=4为例，即有16个0，16个1，数组A用以记录32个0，1的排法，数组B统计二进制数是否已出现过。
程序清单
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1;
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1;A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27;
WHILE A[J]=1 DO J:=J-1;
（ ① ）
FOR I:=J+1TO 27 DO（ ② ）
FOR I:=0 TO 31 DO B[1]:=O;
FOR I:=1 TO 32 DO
BEGIN
（ ③ ）
FOR K:=I TO I+4 DO S:=S*2+A[K];
（ ④ ）
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF（ ⑤ ）THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.
（提高组PASCAL语言 二小时完成）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一． 选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1.下列无符号数中，最小的数是（ ）
A.（11011001）2 B.(75)10 C.(37)8 D.(2A)16
2.在外部设备中，绘图仪属于（ ）
A. 输入设备 B.输出设备 C. 辅（外）存储器 D.主（内）存储器
3.计算机主机是由CPU与（ ）构成的
A. 控制器 B. 输入、输出设备 C. 运算器 D.内存储器
4.计算机病毒的特点是（ ）
A. 传播性、潜伏性、易读性与隐蔽性 B. 破坏性、传播性、潜伏性与安全性
C. 传播性、潜伏性、破坏性与隐蔽性 D. 传播性、潜伏性、破坏性与易读性
5.WINDOWS 9X是一种（ ）操作系统
A. 单任务字符方式 B. 单任务图形方式 C. 多任务字符方式 D. 多任务图形方式
6.Internet的规范译名应为（ ）
A. 英特尔网 B. 因特网 C. 万维网 D. 以太网
7.计算机网络是一个（ ）系统
A.管理信息系统 B.管理数据系统 C.编译系统 D. 在协议控制下的多机互连系统
8.计算机系统总线上传送的信号有（ ）
A.地址信号与控制信号 B. 数据信号、控制信号与地址信号
C.控制信号与数据信号 D. 数据信号与地址信号
9.计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。 已知64位的奔腾处理器一次能处理64个信息位，相当于（ ）字节。
A.8个 B.1个 C.16个 D. 2个
10.某种计算机的内存容量是640K，这里的640K容量是指（ ）个字节
A.640 B. 640*1000 C. 640*1024 D. 640*1024*1024
11.下面哪些计算机网络不是按覆盖地域划分的（ ）
A.局域网 B. 都市网 C.广域网 D. 星型网
12.在有N个叶子节点的哈夫曼树中，其节点总数为（ ）
A.不确定 B. 2N-1 C. 2N+1 D. 2N
13.已知数组中A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内
存时是从地址SA开始连续按行存贮分配的。
试问：A（5，8）的起始地址为（ ）
A.SA+141 B. SA+180 C. SA+222 D. SA+225
14.不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（ ）
A.快存/辅存/主存 B. 外存/主存/辅存 C. 快存/主存/辅存 D. 主存/辅存/外存
15.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary-search），在最坏的情况下，需检视（ ）个单元。
A.1000 B. 10 C. 100 D. 500
16.请仔读下列程序段：
PASCAL语言
Var
a:array[1..3,1..4]of integer;1631638
b:array[1..4,1..3]of integer;
x,y:integer;
begin
for x:=1to3do
for y:=1to4do
a[x,y]:=x-y;
for x:=4 downto 1 do
for y:=1 to 3 do
b[x,y]:=a[y,x];
writeln(b[3,2]);
end.
BASIC语言
DIM A(3,4),B(4,3)
FOR X=1 TO 3
FOR Y=1 TO 4
A(X,Y)=X-Y
NEXT Y,X
FOR X=4 TO 1 STEP --1
FOR Y=1 TO 3
B(X,Y)=A(Y,X)
NEXT Y,X
PRINT B(3,2)
END
上列程序段的正确揄出是（ ）
A.-1 B. -2 C. -3 D. -4
17.线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）
A.必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可
18.下列叙述中，正确的是（ ）
A.线性表的线性存贮结构优于链表存贮结构 B.队列的操作方式是先进后出
C.栈的操作方式是先进先出 D. 二维数组是指它的每个数据元素为一个线性表的线性表
19.电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类；
一类是两端的小鸟相同；另一类则是两端的小鸟不相同。
已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（ ）。
A.奇数 B. 偶数 C. 可奇可偶 D. 数目固定
20.一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每
一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，内屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（ ）
A.（Y*80+X）*2-1 B.（（Y-1）*80+X-1）*2
C.（Y*80+X-1）*2 D.（（Y-1）*80+X）*2-1
二.问题求解：（6+6=12分）
1.已知，按中序遍历二叉树的结果为：abc
问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。
2.设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。
三、阅读程序，并写出正确的运行结果（每题10分，共20分）
1.PROGRAM NOI_003;
CONST N=7; M=6;
VAR I,J,X0,Y0,X1,Y1,X2,Y2:INTEGER;
D:REAL; P:BOOLEAN; G:ARRAY[0..N,0..M] OF 0..1;
FUNCTION DISP(X1,Y1,X2,Y2:INTEGER):REAL;
BEGIN DISP:=SQRT((X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2)); END;
BEGIN
FOR I:=0 T0 N DO FOR J:=0 TO M DO G[I,J]:=0
READLN(X1,Y1,X2,Y2); G[X1,Y1]:=1; G[X2,Y2]:=1; P:=TRUE;
WHILE P DO
BEGIN
P:=FALSE; D:=DISP(X1,Y1,X2,Y2); X0:=X1; Y0:=Y1;
FOR I:=4 TO N DO FOR J:=0 TO M DO
IF (D>DISP(I,J,X2,Y2))AND(G[I,J]=0)THEN
BEGIN D:=DISP(I,J,X2,Y2); X0:=I; Y0:=J; END;
IF(X0<>X1) OR (Y0<>Y1) THEN
BEGIN X1:=X0; Y1:=Y0; P:=TRUE; G[X1,Y1]:=1; END;
D:=DISP(X1,Y1,X2,Y2); X0:=X2; Y0:=Y2;
FOR I:=0 TO 3 DO FOR J:=0 TO M DO
IF（D<DISP(X1,Y1,I,J)AND(G[I,J]=0) THEN
BEGIN D:=DISP(X1,Y1,I,J); X0:=I; Y0:=J END;
IF(X0<>X2)OR(Y0<>Y2) THEN
BEGIN X2:=X0;Y2=Y0;P:=TRUE; G[X2,Y2]:=1; END;
END; WRITELN(X1,Y1,X2,Y2)
END.
输入：7 6 0 0 输出：
2.PROGRAM NOI_002;
VAR I,J,L,N,K,S,T:INTEGER; B:ARRAY[1..10] OF 0..9;
BEGIN
READLN(L,N); S:=L; K:=1; T:=L;
IF N>L THEN BEGIN
WHILE S<N DO
BEGIN K:=K+1;T:=T*L;S:=S+T END;
S:=S-T;N:=N-S-1;
FOR I:=1 TO 10 DO B[I]:=0;
J:=11;
WHILE N>0 DO
BEGIN J:=J-1; B[J]:=N MOD L; N:=N DIV L END;
FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD(’A ’)+B[I]));
READLN;
END
ELSE WRITELN(CHR(ORD(’A’)+N-1))
END
输入： 4 167 输出：
四、完善程序（共38分）
1.问题描述：
将2n个0和2n个1，排成一个圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。
例如，当n=2时，即22个0和22个1排成如下一圈：
比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，…可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。
程序说明
以N=4为例，即有16个0，16个1，数组A用以记录32个0，1的排法，数组B统计二进制数是否已出现过。
程序清单
PROGRAM NOI00;
VAR
A :ARRAY[1..36] OF 0..1;
B :ARRAY[0..31] OF INTEGER;
I,J,K,S,P:INTEGER;
BEGIN
FOR I:=1 TO 36 DO A[I]:=0;
FOR I:=28 TO 32 DO A[I]:=1;
P:=1;A[6]:=1;
WHILE (P=1) DO
BEGIN
J:=27;
WHILE A[J]=1 DO J:=J-1;
（ ① ）
FOR I:=J+1TO 27 DO（ ② ）
FOR I:=0 TO 31 DO B[1]:=O;
FOR I:=1 TO 32 DO
BEGIN
（ ③ ）
FOR K:=I TO I+4 DO S:=S*2+A[K];
（ ④ ）
END;
S:=0;
FOR I:=0 TO 31 DO S:=S+B[I];
IF（ ⑤ ）THEN P:=0
END;
FOR I:=1 TO 32 DO FOR J:=I TO I+4 DO WRITE(A[J]);
WRITELN
END.
