全国青少年信息学奥林匹克竞赛(高中组)初赛试题及答案.docx
NOF95 “同创杯”全国青少年信息学(计算机)奥林匹克竞赛分区联赛初赛试题(高中组) 竞赛用时：2小时答题要求一、全部试题答案均应写在答卷纸上，写在试卷纸上一概无效。 二、算法描述中，可以使用下列过程、函数或算符：(1)算术运算：+, X,/ , DIV, MOD整数除(DIV)：是取二整数相除的商的整数部分。 取模(MOD)：是取二整数相除的余数。如：11 DIV 2 = 5如：11 MOD 2= 1(2)(3)(4)关系运算：>,<,=,<>,>=,<=逻辑运算：AND, OR, NOT函数：ABS(X)：求 X 的绝对值。如：ABS (3.14) =3.14SQR(X)：求X的平方值。如：SQR (3) =9 SQRT(X)：求X的平方根值。如：SQRT(9)=3 TRUNC(X)：去掉X的小数部分：如TRUNC(6.3)=6 ROUND(X)：函数值是小数四舍五入后的整数值。ABS(-3.14)=3.14SQR (-15) =225 SQRT(225)=15 TRUNC(-7.9)=-7如：ROUND(3. 14)=3 ROUND(3. 16)=4 ROUND(-3.14)=-4 ORD(X)：函数值是字符在ASCII码中的序号。ORD(U)=48如：ORD('A')=65 ORD('B')=66 ORD(Z)=90CHR(X)： X表示ASCII码中的序号，函数值是该序号代表的字符值。如：CHR(48)=，(rCHR(65)='A'CHR(90)=Z(5)过程：DEC(A,X)：变量递减，A为有序变量, INC(A,X)：变量递增，A为有序变量,X缺省时为loX缺省时为lo一、基础题：<1>执行ODIR命令后，屏幕上显示如下画面:FORMATSYSPUC XCOPY4 FILE (S)COMCOMBATEXE12345612145487812611216bytes free接着又顺序执行了如下几条DOS命令：C>DIR> DF.TXT表示将列表显示的目录作为文件写盘/ OTYPE DF.TXT ODIR试问：执行命令和在屏幕上显示的结果是否与相同？<2>列举一个问题，使问题的解能对应相应的算法。X： =10；例如对算法:MAXNUMBER： =MAX；(CH>=W) AND (CHv=Z)<3>共32分(每空四分) F：二1； I： =2；')AND (K10) XI AK:=ORD(XI-ORD(,0,); J:=J+1; K:=K-l;Y：二5；READ （M, N）；S：=X*M-Y*N；可列举出如下的问题：学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M） 与答错的题数（N）,求最后得分（S）是多少？现有以下算法：K：=0 ；FOR I： =0 TO 10 DOK：=K+ （50-1*5） DIV 2+1 请列出一个相应的问题。<3>有标号为A、B、C、D和1、2、3、4的8个球，每两个球装一盒，分装4盒。标号为 字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： 匹配的两个球不能在一个盒子内。2号匹配的球与1号球在一个盒子里。A号和2号球在一个盒子里。B匹配的球和C号球在一个盒子里。3号匹配的球与A号匹配的球在一个盒子里。4号是A或B号球的匹配球。D号与1号或2号球匹配。请写出这四对球匹配的情况。<4>从入口（1）到出口 （17）的可行路线图中，数字标号表示关卡：(18)(12)k (1)(2)(3)(')(I-(I)(19)(15)164(13)(14)(9)U0)(6)(17)<8)现将上面的路线图，按记录结构存储如下：123456789 1011 12 13 1415 16 17 181218731241985131661415917 0111222345681011111112 NoPRE请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。二、根据题目要求，补充完善以下伪代码程序：<1>求出二个整形数组错位相加的最大面积。1 .数组面积的定义：(限定数组头尾不为0) 设有一个数组c=(4, 8, 12, 0, 6) 则C的面积为：Sc=(4+8)/2 + (8+12)/2 + 12/2 + 6/2 也就是说，Sc=各梯形面积之和(其中梯形的高约定为1,三角形作为梯形的特殊 一 情况处理)。Sd=(12+24)/2 + (24+6)/2又如D=(12,24,6)是，其面积的定义为2 .数组错位相加的定义设有2个正整数的数组a, b,长度为n,当n=5时：a=(34,26,15,44,12)b=(23,46,4,0/8)对a、b进行错位相加，可能有下列情况 3426154412+)23464018342615441223464018成.3426154412+ )234640183426154435464018或3426154412+ )2346401834261567584018或最后有：3426154412+)23464018-234640183426154412可以看到：由于错位不同，相加的结果也不同。程序要求：找出一个借位相加的方案，使得输出的数组面积为最大。算法提要:设a, b的长度为10,用a,b: array口.10 of integer表示，其结果用数组C,D:array1.30 of integer 表示。错位相加的过程可以从开始不重叠，然后逐步重叠，再到最后的不重叠。梯形面积的计算公式为：(上底+下底)X高+2其中由于约定高为1,故可写为(上底+下底) + 2。程序： n = 10;Function sea : real; 计算数组 C 面积BeginJI := 1;Whiledojl ：=jl + 1；ENDWHILE;If j 1 = 3 * n then sea := 0Else beginJ2 := 3 * n;While doj2 ：=j2-l;If jl =j2 then sea := 0Else beginJ3 := cjl + cj2;For j4 := jl + 1 to j2 - 1 do INC(j3M4*2);ENDFOR;Sea := j3 / 2endENDIF;End;主程序For i := 1 to n do read(aI); endfor;For j := 1 to n do read(bj); endfor;for i := 1 to 2 * n + 1 dofor j := 1 to 3 * n do endfor;for j := 1 to n do cj + n := ajendfor;for j := 1 to n do；endfor;p := sea;if p > s then begind := c;s := p end;endif;endfor;for I := 1 to 3 * n do write(dI/ *); endfor;write(s);End. 主程序结束<2>表的操作：设有一个表，记为L= (ai, az, an),其中：L：表名ai, a2, .,an为表中的兀素当图为。9数字时，表示元素，比为大写字母时，表示是另一个表，但不能循环 定义。例如下列表的定义是合法的。(约定L是第一个表的表名)L二(l,3,K,8,0,4)K=(3,P4H,7)P=(2,3)H二(4,0,5,3)程序要求：当全部表给出之后，求出表中所有元素的最大元素，以及表中全部元素的和。算法提要:表用记录类型定义：长度(LENGTH)表体(是元素为字符类型的数组ELEMENT)队列用数组BASE表示；队列指针用整型变量FRONT与REAR。为此，设计一个字符入队的过程inqueue,出队函数outqueue,表中最大元素及元素求 和均采用递归计算。程序：PROCEDURE INQUEUE(Q, C);过程需要二个参数，Q记录类型，C字符类型Q.REAR :二;Q.BASEQ.REAR :=C；END; 过程结束FUNCTION OUTQUEUE(Q)函数需要一个参数，Q记录类型Q.FRONT :=;OUTQUEUE :二 Q.BASEQ.FRONTEND；/函数结束FUNCTION MAXNUMBER(C) /函数需要一个参数，C字符类型Max := CHR(O);FOR i:=l to TC.LENGTH DOCH :=TC.ELEMENTi;IFTHENM := MAXNUMBER(CH)ELSEM := CHENDIF;IF MAX < M THENMAX := MENDIF;ENDFOR;END; 函数结束FUNCTION TOTAL(C)/函数需要一个参数，C：字符类型K:=0;FOR i:= 1 TO TC.LENGTH DOCH := TC.ELELMENTi;IFTHENM := TOTAL(CH); ELSEM := ORD(CH)-ORDCO');ENDIFK := K + MENDFOR;TOTAL K;END; 函数结束主程序MAX := 36;FOR TABNO := A TO Z DOTTABNO.LENGTH := 0;ENDFOR；Q.FRONT := 0; Q.REAR := 0;INQUEUE(Q,L);WHILE (Q.FRONT <>Q .REAR ) DOTABNO := OUTQUEUE(Q);WRITE(TABNO, '=*);READLN(S);i := 1; WHILE Si <> '(' DO i - i+ 1;ENDWHILE;WHILE Si <> y DOIF (Si>=W) AND (Siv=Z) THEN Si:=CHR(ORD(Si)+ORD(,A,)-ORD(,a,); IF (Si>='A') AND (Siv=Z) THEN INC(TTABNO.LENGTH);TTABNO.ELEMENTTTABNO.LENGTH := Si; INQUEUE(Q, Si);ENDIF;ELSEIF (Si>=V) ANDN (Sik=9) THEN INC(TTABNO.LENGTH);TTABNO.ELEMENTTTABNO.LENGTH := Si ENDIF;INC(i)ENDIF;ENDWHILE;ENDWHILE;WRITE('The max number in table L is:', maxnumber('L');WRITE('Total is:*, totaRV)END. /主程序结束<3>设有一个实数，以字符串形式存放于数组x中，用x： arrayL.Nof char表示。其中xl 若为二表示负数；若为中、？或;则表示正数。若为数字，也认为是正数。例如 x=(<2,O,3，？57%') 则表示 203.5x=(m ?2?07%)则表示-1.2约定：在字符串x中，除xl外，其后可以包含有若干个？与，但仅以第一次出现的 为准，空格不起任何作用，并以字符'作为结束标志。程序要求：将输入的字符串还原成实数输出(小数点后无用的0应除去)，还原的结果 以下列形式存放(不需要输出)。F：数符。正数放0,负数放loA： array1.N of integer;存放数字，不放小数点。K：表示A中有效数字的个数。J：表示小数点后的位数。例如：数203.24,还原后结果的存放是：F=0A二(2, 0, 3, 2, 4)K=5J=2又如：数-33.0740,还原后结果的存放是：F=1A二(3, 3, 0, 7, 4)K=5J=3算法提要:乂：皿丫1100*1;可放长度定为10；首先读入字符串，然后处理数的 符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小数点，并 约定输入是正确的，不用作出错检查。程序：FOR I := 1 TO IODOAI := 0; ENDFOR;FOR I:= 1 TO IODO READ(XI); ENDFOR;J := 0; F := 0; K := 0; B := 0;IFX1 =THEN BEGINENDELSE IFX1 ' THEN I 2ELSE I:= 1;ENDIF;ENDIF;WHILE DO :=I + 1; ENDWHILEWHILE ®DOIF (XI >= O) AND (XI <= 9) THENK:=K+ 1;IF B = 1 THEN ®_ENDIFELSE IF (XI=V) AND (B=0) THENB := 1; ENDIFI :=I+ 1ENDIF;ENDWHILE;IF J>0 THEN WHILE AK=0 DO END WHILE;ENDIF.END. /程序结束NOF95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组） 试题参考答案一、基础题：共33分<1>本题共4分显示结果不相同，和比多出一个文件目录。<2>本题共9分列出的一个相应问题是：（能列出类似的问题均可）用五角钱换成5分、2分与1分的硬币，有多少种换法。<3>本题共8分这四对球匹配的情况为：ABCD4312<4>本题共12分从存贮数据中求出从入口到出口经过最少关卡路径的算法及输出结果:算法：输出结果:1:=1;(17)WHILE NOI W17D0t(16)ENDWHILE;tREPEAT(19)WRITEC(NOI,);tWRITE('t');(18)I-PREI;tUNTIL 1=0;1二、根据题目要求，补充完善以下伪代码程序：(共67分)<1>共10分(每空二分) CJ1=OAND J1<3*N CJ2 =0 AND J2>J1 S:=0 CJ:=O; CI-+-J-1:=CI+J-1+BJ;<2>共25分(每空五分)(Q.REAR+1) MOD (MAX+1);(Q.FRONT+l) MOD(MAX+1);(CH='A')AND (CHv='Z')
