1、全国青少年信息学奥林匹克分区联赛初赛模拟题高中组信息学奥林匹克分区联赛初赛模拟题(PASCAL语言 竞赛历时：2小时)一、选择填空：(30%，每题%)一、操作系统是一类重要的系统软件，下面几个软件中不属于操作系统的是_。(A)MS-DOS (B)UNUX (C)PASCAL (D)WINDOWS 98二、在运算机内部，用来传送、存储、加工处置的数据或指令(命令)都是以_形式进行的。(A)十进制码 (B)智能拼音码(C)二进制码 (D)五笔字型码3、已知运算机C:DOS下有一个正确的文件，当执行如下命令：C:FORMAT A:取得的回答是bad command or file name提示信息，
2、下面解释正确的是_。(A)根目录中没有文件；(B)在执行该命令前操作者没执行过PATH命令；(C)C:DOS中的文件有错(D)由于或操作者最后执行过的PATH命令中缺少路径C:DOS，或根本没有执行过PATH命令。4、将A盘上50个文件用：C:COPY A:*.*命令复制到C盘的当前目录中。在复制到某一个文件时，由于读数据犯错，屏幕显示：Abort, Retry, Ignore, Fail?键入“I”后，继续复制没再出现过犯错信息。最后复制的结果是_。(A)读数据犯错的文件不正确，其他文件正确；(B)读数据犯错的文件不正确，其他文件也不正确；(C)读数据犯错的文件正确，其他文件不正确；(D)复
3、制的文件全正确；五、表达式(4 MOD (3)与(4 MOD 3)的值为：_。(A)1，1 (B)1，1(C)1，1 (D)1，1六、小张用十六进制，八进制和十进制写了一个等式：5219=33，式中三个数是各不相同进位制的数，试问52，19，33，别离为_。(A)八进制，十进制，十六进制(B)十进制，十六进制，八进制(C)八进制，十六进制，十进制(D)十进制，八进制，十六进制7、某班有50名学生，每位学生发一张调查卡，上写a, b, c三本书的书名，将读过的书打，结果统计数字如下：只读a者8人；只读b者4人；只读c者3人；全数读过的有2人；读过a，b两本书的有4人；读过a，c两本书的有2人；读
4、过b，c两本书的有3人。则读过a的人数是_。(A)12人 (B)30人 (C)10人 (D)24人八、下列if语句中，endif表示相应if的结束：y=0if x0 then y=5 else if x10 then y=10if x100 then y=100 endif else y=200 endif endif则当x=80时，运行的结果为_。(A)y=5 (B)y=100 (C)y=10 (D)y=2009、若是用一个字节来表示整数，最高位用作符号位，其他位表示数值。例如：试问这种表示法的整数a的范围应是_。00000001 符号位表示正 表示+110000001 符号位表示负 表示1
5、(A)-127a127 (B)-128a128(C)-128a128 (D)-128k then begin writeln(error);halt;end; end; counting(a,b,n,k); readln;end.键盘输入：8 63 6 4 1 3 4 1 4输出：2六、（7%）设数组a1，a2，an，已存入了数据，挪用不同的排序程序，则数据比较的次数将会不同，试计算别离挪用下列不同的排序进程的比较运算的次数。其中swap(i，j)表示ai与aj进行互换。(1)procedure sort1(n：integer)； var i，j：integer； begin for i：=1
6、 to n-1 do fOr j：=1 to n do if ajai then swap(i，j) end； 挪用该进程的语句为sort1(n)，比较运算的次数为：_(2)procedure sort2(i，n：integer)； var j：integer； begin if i=n then write(an) else for j：=i+1 to n do if ajai then swap(i，j); wrrite(ai)； sort2(i+1，n)； end 挪用该进程的语句为sort2(0，n)，比较运算的次数为：_(3)procedure sort3(i，j：integer)；
7、 var m：integer； begin if ij then begin m：=(i+j) div 2； sort3(i，m)；sort3(m+1，j)； merge；假设归并的元素别离为p、q个，需要比较p+q次 end； end； 挪用该进程的语句为sort3(0，n)，比较运算的次数为：_27、(7%）program EXP3(input,output); const n=4;type se=array1.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
8、 do read(ai); readln; s:=0; t:=0; for i:=1 to n*2 do if ai=1 then s:=s+1 else if ai=0 then t:=t+1;if (sn) or (tn) then writeln(error) else begin s1:=0; for i:=1 to 2*n-1 do if aiai+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 aiaj then begintemp:=ai;ai:=a
9、j;aj:=temp; s:=0; for L:=1 to 2*n-1 do if aLaL+1 then s:=s+1;if sswap then begin swap:=s; i1:=i; j1:=j end;temp:=ai;ai:=aj;aj:=tempend;if swap0 thenwriteln(maxswap=,swap-s1,i=,i1,j=,j1) end;End.输入： 输出：四、按照题意，补充完善以下程序：(30%)28金蝉素数【问题描述】某古寺的一块石碑上依稀刻有一些三位与四位的神秘自然数。专家研究发觉：这些数是素数，且从低位去掉一名，或两位，后都仍为素数，从高位去掉
10、一名，或两位，后也都仍为素数，更奇妙的是同时去掉它的最高位与最低位数字后仍是素数。因此，人们把这些神秘的素数称为金蝉素数，喻意金蝉脱壳以后仍为美丽的金蝉。试求出石碑上的金蝉素数。【程序清单】var a: array1.400of integer; s,u,i,j,k,l,v,t,m,w,n:integer;begina1:= 2; a2 := 3; a3 := 5; a4:= 7; u := 4;For k:= 11 To 9999 do if k mod 2=1 then begin j:=3;while (1) and(k mod j0) do j:=j+1; If j trunc(Sqr
11、t(k) Then begin IF au100 THEN beginL:=trunc(ln(k)/ln(10)+1;t:=1;s:=0;For i := 1 To (2) do begint := t * 10; w := trunc(k / t);m := k - w * t;V := 1; n := 10000;IF i=L-1 THEN n:=trunc(m/10);WHiLE (av=W) OR (3) do beginIf aV = w Then s := s + 1;IF av=m THEN S:=S+1;IF av=n THEN S:=S+1;(4);end;end;If (5
12、) Then writeln(k);ENDendend; End.2九、多项式乘法运算【问题描述】多项式乘法运算：p(x)=2x2-x+1，q(x)=x+1 p(x)*q(x)=(2x2-x+1)(x+1)=2x3+x2+1【程序说明】多项式的表示：系数、指数如上例：p(x) 系数 指数 q(x) 系数 指数 2 2 1 1 -1 1 1 0 1 0 0 0 0 0p*q的结果存入c中。其输出格式是：依次用一对括号内的(系数、指数)别离来表示。如上例的输出结果表示为：(2，3)(1，2)(1，0)【程序清单】begin jp:=0; readln(x,y); while x 0 do begi
13、n jp:=jp+l; pjp,1:=x; pjp,2:=y;readln(x,y); end; jq:=0; readln(x,y); while x 0 do begin jq:=jq+1; qjq,1:=x; qjq,2:=y; readln(x,y); end; jc:=1;cjc,1:=0; cjc,2:=-1000; for i:= 1 to jp do begin _(1)_ y:=pi,2; for j:= 1 to jq do begin _(2)_ y1:=y+qj,2; k:=1; while y1 ck,2 do k:=k+1; if y1 = ck,2 then _(
14、3)_ else begin for l:= jc downto k do begin cl+1,1:=cl,1; cl+1,2:=cl,2; end; ck,1:=x1;ck,2:=y1; _(4)_ end; end; for i:=1 to jc do if _(5)_ then write(,ci,1,ci,2,) ;end.30、求最长不下降序列【问题描述】设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)且a(i)a(j) (ij)，例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)则称为长度
15、为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出以后，求出最长的不下降序列。【算法分析】按照动态计划的原理，由后往前进行搜索。1对a(n)来讲，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；2若从a(n-1)开始查找，则存在下面的两种可能性：若a(n-1)a(n)则存在长度为1的不下降序列a(n-1)或a(n)。3一般若从a(i)开始，现在最长不下降序列应该按下列方式求出:在a(i+1),a(i+2),a(n)中，找出一个比a(i)大的且最长的不下降序列，
16、作为它的后继。4为算法上的需要，概念一个数组整数类型二维数组d（N，3）d（I，1）表示点a（i）d（I，2）表示从I位置抵达N的最长不下降序列长度d（I，3）表示从I位置开始最长不下降序列的下一个位置【程序清单】PROGRAM MAX_RISE(INPUT,OUTPUT);CONST MAXN=100;FNAME=;TYPE TLIST=ARRAY1.MAXN,1.3 OF INTEGER;VAR D:TLIST;N:BYTE;PROCEDURE INIT; VAR I:INTEGER; F:TEXT;BEGIN ASSIGN(F,FNAME); RESET(F); READLN(F,N);
17、 FOR I:=1 TO N DO BEGIN READ(F,DI,1);DI,2:=1; DI,3:=0 END; _(1)_END;PROCEDURE MAKE;VAR I,J,P:BYTE;L:INTEGER;BEGIN FOR I:=_(2)_ DO BEGIN L:=0;P:=0; FOR J:=I+1 TO N DO IF (DI,1L) THEN BEGIN L:=DJ,2;_(3)_;END; IF _(4)_ THEN BEGIN DI,2:=L+1;DI,3:=P;END; END;END;PROCEDURE OUTPUT;VAR I,L,DMAX:BYTE;BEGIN W
18、RITE(SOURCE:); FOR I:=1 TO N DO WRITE(DI,1:5); WRITELN; DMAX:=D1,2;L:=1; FOR I:=2 TO N-1 DO IF DI,2DMAX THEN BEGIN _(5)_;L:=I;END; WRITE(RESULT IS: ); WHILE L0 DO BEGIN WRITE(DL,1:5);L:=DL,3;END; WRITELN; WRITELN(MAX LENGTH=,DDMAX,2);END;BEGIN INIT; MAKE; OUTPUT;END.信息学奥林匹克分区联赛初赛模拟题答题纸班级：_ 姓名：_(参考答案
19、)一、选择填空：(30%，每小题%)题号12345678910答案CCDABBADAD题号11121314151617181920答案DABBACAB116位码： 二、问题求解：(20%，每题小题5%)2一、能不能，因为C与四个城市邻接，不可能一次遍历2二、注意：先依中缀或前缀表达式画出表达式树，再按照后序遍历方式写出后缀表达式1）前缀：+A/*BCD，后缀：ABC*D/+；2）中缀：-A+B*(-C)；后缀：ABC*+23、1）K=I+J(J-1)/2 2）K=I+(J-1)N24、1 2 3 4 5 6 7 1 0 1 0 0 0 0 0 2 1 0 1 1 0 0 0 3 0 三、阅读程
20、序写出运行结果（20%）:2五、（6%）输出： 1 1 3 3 4 4 4 62六、（7%）(1)挪用进程sort1(n)，比较运算的次数为： n(n-1) (2)挪用进程sort2(0，n)，比较运算的次数为： n(n+3)/2 (3)挪用进程sort3(0，n)，比较运算的次数为： log2(n-1)+log2(n/2-1)(p+q)+2 27、(7%)输出：jamp=5 maxswap=2 I=6 j=7四、按照题意，补充完善程序：(30%，每空2%)28金蝉素数(1)j=trunc(sqrt(k) (2)L-1 (3) av=m (4)inc(v) (5)s=2*L-12九、多项式乘法运算(1)x:=pI,1 (2)x1:=x*qj,1 (3)ck,1:=ck,1+x1 (4)inc(v) (5)cI,j030、求最长不下降序列(1)close(F) (2)n-1 downto 1 (3)p:=j (4)L0 (5)DMAX:=DI,2
