第四届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题

第四届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题

第四届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题（高中组）（PASCAL语言竞赛用时：2小时）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、选择填空（23%）1．操作系统是一类重要的系统软件，下面几个软件中不属于操作系统的是。{1%}（A）MS-DOS（B）UCDOS（C）PASCAL（D）WINDOWS952．在计算机内部，用来传送、存贮、加工处理的数据或指令（命令）都是以形式进行的。（A）十进制码（B）智能拼音码（C）二进制码（D）五笔字型码{1%}3．已知在计算机C:\DOS下有一个正确的FORMAT.COM文件，当执行如下命令：C:\>FORMATA:<回车>得到的回答是BADCOMMANDORFILENAME提示信息，下面解释正确的是_____________。{2%}(A)根目录中没有AUTOEXEC.BAT文件(B)在执行该命令前操作者没执行过PATH命令(C)C:\DOS中的FORMAT.COM文件有错(D)由于AUTOEXEC.BAT或操作者最后执行过的PATH命令缺少路径C:\DOS，或者根本没有执行PATH命令4．将A盘上50个文件用C:\>COPYA:*.*命令复制到C盘的当前目录中，在复制到某个文件时，由于读数据出错，屏幕显示：ABORT,RETRG,IGNORE,FAIL?键入“I”后，继续复制没再出现过错误信息，最后复制的结果是_________。{2%}（A）读数据出错的文件不正确，其他文件正确；（B）读数据出错的文件不正确，其它文件也不正确；（C）读数据出错的文件正确，其它文件不正确；（D）复制的文件完全正确。5．表达式（4MOD（-3））与（-4MOD3）的值为：。{2%}（A）-1，-1（B）1，-1（C）-1，1（D）1，16．小张用十六进制、八进制和十进制写了如下的一个等式：52-19=33式中三个数是各不相同进位制的数，试问52、19、33，分别为_________。{3%}(A)八进制，十进制，十六进制（B）十进制，十六进制，八进制（C）八进制，十六进制，十进制（D）十进制，八进制，十六进制7．某班有50名学生，每位学生发一张调查卡，上面写a，b，c三本书的书名，将读过的书打ü，结果统计数字如下：只读a者8人；只读b者4人；只读c\n者3人；全部读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读过b，c两本书的有3人；{4%}（1）读过a的人数是，（2）一本书也没有读过的人数是。（A）12人（B）30人（C）10人（D）31人8．下列IF语句中，ENDIF表示相应IF的结束：{2%}y=0ifx<0theny=5elseifx<10theny=10ifx<100theny=100endifelsey=200endifendif试指出：当X=80时，运行的结果是______,X=5时，运行结果为_________。{2%}（A）Y=9（B）Y=5（C）Y=10（D）Y=100（E）Y=2009．如果用一个字节来表示整数，最高位用作符号位，其它位表示数值。例如：{4%}表示+1表示-100000001↑符号位表示正10000001　　　↑符号位表示负①试问这样表示法的整数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开始，出栈后不再进栈）：进栈、进栈、进栈，出栈、进栈、出栈、进栈。试问出栈的元素序列是______________。{2%}（A）{5，4，3，2，1}（B）{2，1}（C）{2，3}（D）{3，4}二、问题求解：（21%）1．已知一个数列U1，U2，U3，…，UN，…往往可以找到一个最小的K值和K个数a1，a2，…,an使得数列从某项开始都满足：UN+K=a1UN+K-1+a2UN+K-2+……+akUN(A)\n例如对斐波拉契数列1，1，2，3，5，…可以发现：当K=2，a1=1，a2=1时，从第3项起（即N>=1）都满足Un+2=Un+1+Un。试对数列13，23，33，…，n3,…求K和a1,a2,…,aK使得（A）式成立。{8%}2．给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA画出此二叉树。{8%}3．用邻接矩阵表示下面的无向图：{6%}三、阅读程序，写出程序的正确运行结果：（39%）1．programexp1(imput,output);{6%}VARi,s,max:integer;a：array[1..10]ofinteger;beginfori:=1to10doread(a[i]);max:=a[1]；s:=a[1];fori：=2to10dobeginifs<0thens：=0;s：=s+a[i];ifs>maxthenmax：=send;writeln(‘max=’,MAX)end.输入：89－124651115－289输出：max=2．programexp3(input,output);{9%}CONSTN=10;VARS,I:INTEGER;FUNCTIONCO(I1:INTEGER):INTEGER;VARJ1,S1:INTEGER;BEGINS1:=N;FORJ1:=(N-1)DOWNTO(N-I1+1)DOS1:=S1*J1DIV(N-J1+1);CO:=S1\nEND;BEGINS:=N+1;FORI:=2TONDOS:=S+CO(I);WRITELN(‘S=’,S);END.3．programexp3(input,output);{12%}VARI,J,S:INTEGER;B:ARRAY[0..5]OFINTEGER;BEGINS:=1;FORI:=1TO5DOB[I]:=IJ:=1;WHILEJ>0DOBEGINJ:=5;WHILE(J>0)AND(B[J]=10+J-5)DOJ:=J-1;IFJ>0THENBEGINS:=S+1;B[J]:=B[J]+1;FORI:=J+1TO5DOB[I]:=B[J]+I-JEND;END;WRITELN('S=',S);END.4．ProgramEXP4(input,output);{12%}constn=4;typese=array[1..n*2]ofchar;vari,j,i1,j1,k,s,t,s1,l,swap:integer;temp:char;a:se;beginfori:=1ton*2doread(a[i]);readln;s:=0;t:=0;fori:=1ton*2doifa[i]='1'thens:=s+1elseifa[i]='0'thent:=t+1;if(s<>n)or(t<>n)thenwriteln('error')elsebegins1:=0;fori:=1to2*n-1doifa[i]<>a[i+1]thens1:=s1+1;writeln('jamp=',s1);swap:=0;\nfori:=1to2*n-1doforj:=i+1to2*ndoifa[i]<>a[j]thenbegintemp:=a[i];a[i]:=a[j];a[j]:=temp;s:=0;forl:=1to2*n-1doifa[l]<>a[l+1]thens:=s+1;ifs>swapthenbeginswap:=s;i1:=i;j1:=jend;temp:=a[i];a[i]:=a[j];a[j]:=tempend;ifswap>0thenwriteln('maxswap=',swap-s1,'i=',i1,'j=',j1)endEND.输入：10101100输出：四、根据题意，补充完善以下程序：（17%）1．FBZ串问题。已知一个由0，1字符组成的长度为2n的字符串。请按以下规则将已给出的字符串分解为FBZ串：（1）若其中字符全为'1'，则称其为'B'串；（2）若其中字符全为'0'，则称其为'Z'串；（3）若不全为'0'，同时也不全为'1'，则称'F'串。若此串为F串，则应将此串分解为2个长为2n-1的子串。对分解后的子串，仍按以上规则继续分解，直到全部为B串或为Z串为止。例如n=3时，给出0-1串为：'10111001'FF(1011)F(1001)F(10)F(10)F(01)B(11)111000最后输出：FFFBZBFFBZFZB问题：给出01串，分解成FBZ串。程序如下：ProgramEXP-5;CONSTN=8;VARI,J,ST11,ST12,ST2，S,T:INTEGER;STR1:ARRAY[1..N*2,1..N]OFCHAR;STR2:ARRAY[1..40]OFCHAR;\nBEGINFORI:=1TON*2DOFORJ:=1TONDOSTR1[I,J]:='□';ST11:=1;ST12:=1;ST2:=0;FORI:=1TONDOREAD(STR1[1,I]);READLN;4%WHILE_______1________DOBEGINS:=0;T:=0;FORI:=1TONDOBEGINIFSTR1[ST12,I]='1'THENS:=S+1;IFSTR1[ST12,I]='0'THENT:=T+1END;IF___2_____THENBEGIN2%ST2:=ST2+1;STR2[ST2]:='B'ENDELSEIF___3____THENBEGIN2%ST2:=ST2+1;STR2[ST2]:='Z'ENDELSEBEGINST2:=ST2+1;STR2[ST2]:='F';J:=(S+T)DIV2;FORS:=N*2-2DOWNTO___4___DO3%FORT:=1TONDOSTR1[S+2,T]:=STR1[S,T];ST11:=ST11+2;FORI:=1TOJDOBEGINSTR1[ST12+1,I]:=STR1[ST12,I];STR1[ST12+2,I]:=______5______4%END;FORI:=___6___DOBEGIN2%STR1[ST12+1,I]:='□';STR1[ST12+2,I]:='□'ENDENDST12:=ST12+1END;FORI:=1TOST2DOWRITE(STR2[I]);WRITELNEND.