2002年全国青少年信息学

第四届全国青少年信息学(计算机)奥林匹克分区联赛初赛试题(高中组)

(PASCAL语言竞赛用时：2小时)

　　一、选择填空：(23%)

1、操作系统是一类重要的系统软件，下面几个软件中不属于操作系统的是____。(1%)

(A)MS－DOS (B)UCDOS (C)PASCAL (D)WINDOWS 95

2、在计算机内部，用来传送、存储、加工处理的数据或指令(命令)都是以_____形式进行的。(1%)

(A)十进制码 (B)智能拼音码 (C)二进制码 (D)五笔字型码

3、已知计算机C:\DOS下有一个正确的FORMAT.COM文件，当执行如下命令：

C:\>FORMAT A:<回车>

得到的回答是bad command or file name提示信息，下面解释正确的是_______。(2%)

(A)根目录中没有AUTOEXEC.BAT文件；

(B)在执行该命令前操作者没执行过PATH命令；

(C)C:\DOS中的FORMAT.COM文件有错

(D)由于AUTOEXEC.BAT或操作者最后执行过的PATH命令中缺少路径C:\DOS，或者根本没有执行过PATH命令。

4、将A盘上50个文件用：C:\>COPY A:*.*命令复制到C盘的当前目录中。在复制到某一个文件时，由于读数据出错，屏幕显示：

Abort, Retry, Ignore, Fail?

键入“I”后，继续复制没再出现过出错信息。最后复制的结果是_______。(2%)

(A)读数据出错的文件不正确，其他文件正确；

(B)读数据出错的文件不正确，其他文件也不正确；

(C)读数据出错的文件正确，其他文件不正确；

(D)复制的文件全正确；

5、表达式(4 MOD (－3))与(－4 MOD 3)的值为：_______。(2%)

(A)－1，－1 (B)1，－1 (C)－1，1 (D)1，1

6、小张用十六进制，八进制和十进制写了如下一个等式：

52－19=33

式中三个数是各不相同进位制的数，试问52，19，33，分别为________。(3%)

(A)八进制，十进制，十六进制 (B)十进制，十六进制，八进制

(C)八进制，十六进制，十进制 (D)十进制，八进制，十六进制

7、某班有50名学生，每位学生发一张调查卡，上写a, b, c三本书的书名，将读过的书打√，结果统计数字如下： (4%)

只读a者8人；只读b者4人；只读c者3人；全部读过的有2人；

读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；

问：(1)读过a的人数是_____。 (2)一本书也没读过的人数是______。

(A)12人 (B)30人 (C)10人 (D)24人 (E)31人

8、下列if语句中，endif表示相应if的结束： (2%)

y=0

if x<0

then y=5

else if x<10

then y=10

if x<100

then y=100

endif

else y=200

endif

试指出：当x=80时，运行的结果为______，x=5时结果为______。 (2%)

(A)y=9 (B)y=5 (C)y=10 (D)y=100 (E)y=200

9、如果用一个字节来表示整数，最高位用作符号位，其他位表示数值。 (4%)

例如：

↑符号位表示正表示+1

↑符号位表示负表示－1

①试问这种表示法的整数a的范围应是_______。

(A)－127≤a≤127 (B)－128≤a≤128

(C)－128≤a<128 (D)－128<a≤128

②在这样表示法中，以下_____说法是正确的。

(A)范围内的每一个数都只有唯一的格式

(B)范围内的每一个数都有两种格式

(C)范围内的一半数有两种格式

(D)范围内只有一个数有两种表示格式

10、设栈S的初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在S栈上依次进行如下操作(从序列中的1开始，出栈后不再进栈)：进栈，进栈，进栈，出栈，进栈，出栈，进栈，试问出栈的元素序列是________。

(A){5，4，3，2，1} (B){2，1} (C){2，3} (D){3，4}

二、问题求解：(21%)

1、已知一个数列U₁，U₂，U₃，…U_n，…往往可以找到一个最小的k值和k个数a₁，a₂，…，a_k，使得数列从某项开始都满足：

u_n+k=a₁u_n+k_－1+a₂u_n+k_－2+…+a_ku_n (A)

例如对斐波拉契数列1，1，2，3，5，…可以发现：当k=2，a₁=1，a₂=1时，从第3项起(即n≥1)都满足u_n+2=u_n+1+u_n。

试对数列1³，2³，3³，…，n³，…求k和a₁，a₂，…，a_k使得(A)成立。 (8%)

2、给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。 (8%)

3、用邻接矩阵表示下面的无向图： (6%)

三、阅读程序写出程序的正确运行结果；(39%)

1. program exp1(input,output); (6%)

VAR i, s, max:integer;

a :array[1..10] of integer;

Begin

for i:=1 to 10 do read(a[i]);

max:=a[1]; s:=a[1];

for i:=2 to 10 do

begin if s<0 then s:=0;

s:=s+a[i];

if s>max then max:=s

end;

writeln('max=',MAX)

End.

输入：8 9 －1 24 6 5 11 15 －28 9

输出：max=

2. program exp2(input,output); (9%)

CONST N=10;

VAR S,I:INTEGER;

FUNCTION CO(I1:INTEGER):INTEGER;

VAR J1,S1:INTEGER;

BEGIN

S1:=N;

FOR J1:=(N-1) DOWNTO (N-I1+1) DO S1:=S1*J1 DIV (N-J1+1);

CO:=S1;

END;

BEGIN

S:=N+1;

FOR I:=2 TO N DO S:=S+CO(I);

WRITELN('S=',S);

END.

3. Program exp3(input,output); (12%)

VAR I,J,S:INTEGER;

B :ARRAY[0..5] OF INTEGER;

BEGIN

S:=1;

FOR I:=1 TO 5 DO B[I]:=I;

J:=1;

WHILE J>0 DO

BEGIN

J:=5;

WHILE (J>0) AND (B[J]=10+J-5) DO J:=J-1;

IF J>0 THEN

BEGIN

S:=S+1; B[J]:=B[J]+1;

FOR i:=J+1 TO 5 DO B[i]:=B[J]+i-J

END;

WRITELN('S=',S);

END.

4. Program EXP4(input,output); (12%)

const n=4;

type se=array[1..n*2] of char;

var i,j,i1,j1,k,s,t,s1,L,swap:integer;

temp :char;

a :se;

Begin

for i:=1 to n*2 do read(a[i]); readln;

s:=0; t:=0;

for i:=1 to n*2 do

if a[i]='1' then s:=s+1 else if a[i]='0' then t:=t+1;

if (s<>n) or (t<>n) then writeln('error')

else begin s1:=0;

for i:=1 to 2*n-1 do if a[i]<>a[i+1] then s1:=s1+1;

writeln('jamp=',s1); swap:=0;

for i:=1 to 2*n-1 do

for j:=i+1 to 2*n do

if a[i]<>a[j] then

begin

temp:=a[i];a[i]:=a[j];a[j]:=temp;

s:=0;

for L:=1 to 2*n-1 do

if a[L]<>a[L+1] then s:=s+1;

if s>swap

then begin swap:=s; i1:=i; j1:=j end;

temp:=a[i];a[i]:=a[j];a[j]:=temp

end;

if swap>0

then writeln('maxswap=',swap-s1,' i=',i1,' j=',j1)

end

End.

输入：10101100 输出：

四、根据题意，补充完善以下程序：(17%)

FBZ串问题。已知一个由0，1字符组成的长为2ⁿ的字符串。请按.以下规则将已给出的字符串分解成FBZ串：

①若其中字符全为‘1’，则称其为‘B’串；

②若其中字符全为‘0’，则称其为‘Z’串；

③若不全为‘0’，同时也不全为‘1’，则称‘F’串。若此串为F串。则应将此串分解为2个长为2ⁿ^－1的子串。

对分解后的子串，仍按以上规则继续分解，直到全部为B串或为Z串为止。

例如n=3时，给出0—1串为：‘10111001’

最后输出：FFFBZBFFBZFZB

问题：给出0，1串，分解成FBZ串。

程序如下：(17%)

Program EXP5;

const n=8;

var

i,j,st11,st12,st2,s,t:integer;

str1 :array[1..n*2,1..n] of char;

str2 :array[1..40] of char;

Begin

for i:=1 to n*2 do

for j:=1 to n do str1[i,j]:=‘ ’;

st11:=1; st12:=1; st2:=0;

for i:=1 to n do read(str1[1,i]); readln;

while ① do (4%)

begin

s:=0; t:=0;

for i:=1 to n do

begin

if str1[st12,i]=’1’ then s:=s+1;

if str1[st12,i]=’0’ then t:=t+1;

end;

if ② then begin (2%)

st2:=st2+1; str2[st2]:=’B’

end

else if ③ then begin (2%)

st2:=st2+1; str[st2]:=’Z’

end

else begin

st2:=st2+1; str2[st2]:=’F’; j:=(s+t) div 2;

for s:=n*2－2 downto ④ do (3%)

for t:=1 to n do

str1[s+2,t]:=str1[s,t];

st11:=st11+2;

for i:=1 to j do

begin

str1[st12+1,i]:=str1[st12,i];

str1[st12+2,i]:= ⑤ ； (4%)

end;

for i:= ⑥ do begin (2%)

str1[st12+1,i]:=’ ’; str1[st12+2,i]:=’ ’

end;

st12:=st12+1;

end;

for i:=1 to st2 do write(str2[i]); writeln;

End.