1、全国青少年信息学奥林匹克竞赛高中组初赛试题及答案NOI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组） 竞赛用时：2小时答 题 要 求一、 全部试题答案均应写在答卷纸上，写在试卷纸上一概无效。二、 算法描述中，可以使用下列过程、函数或算符：（1） 算术运算：，DIV，MOD整数除（DIV）：是取二整数相除的商的整数部分。如：11 DIV 2 = 5取模（MOD）：是取二整数相除的余数。 如：11 MOD 2 = 1（2） 关系运算：，=，=，=（3） 逻辑运算：AND，OR，NOT（4） 函数：ABS(X)：求X的绝对值。如：ABS（3.14）=3.14 ABS
2、(-3.14)=3.14SQR(X)：求X的平方值。如：SQR（3）=9 SQR（-15）=225SQRT(X)：求X的平方根值。如：SQRT(9)=3 SQRT(225)=15TRUNC(X)：去掉X的小数部分：如TRUNC(6.3)=6 TRUNC(-7.9)=-7ROUND(X)：函数值是小数四舍五入后的整数值。 如：ROUND(3.14)=3 ROUND(3.16)=4 ROUND(-3.14)=-4ORD(X)：函数值是字符在ASCII码中的序号。 如：ORD(A)=65 ORD(B)=66 ORD(Z)=90 ORD(0)=48CHR(X)：X表示ASCII码中的序号，函数值是该序
3、号代表的字符值。 如：CHR(48)=0 CHR(65)=A CHR(90)=Z（5） 过程： DEC(A,X)：变量递减，A为有序变量，X缺省时为1。INC(A,X)：变量递增，A为有序变量，X缺省时为1。一、基础题： 执行CDIR 命令后，屏幕上显示如下画面： FORMAT COM 12145 SYS COM 4878 PUC BAT 126 XCOPY EXE 11216 4 File（s） 123456 bytes free接着又顺序执行了如下几条DOS 命令： CDIR DF.TXT /表示将列表显示的目录作为文件写盘 /CTYPE DF.TXT CDIR 试问：执行命令和 在屏幕上
4、显示的结果是否与相同? 列举一个问题，使问题的解能对应相应的算法。 例如对算法： X：=10； Y：=5； READ（M，N）； S：=X*M-Y*N；可列举出如下的问题： 学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M）与答错的题数（N），求最后得分（S）是多少？现有以下算法： K：=0 ； FOR i：=0 TO 10 DO K：=K+（50-I*5）DIV 2+1 请列出一个相应的问题。 有标号为A、B、C、D和1、2、3、4的8个球，每两个球装一盒，分装4盒。标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件：1 匹配的两个球不能在
5、一个盒子内。2 2号匹配的球与1号球在一个盒子里。3 A号和2号球在一个盒子里。4 B匹配的球和C号球在一个盒子里。5 3号匹配的球与A号匹配的球在一个盒子里。6 4号是A或B号球的匹配球。7 D号与1号或2号球匹配。请写出这四对球匹配的情况。 从入口（1）到出口（17）的可行路线图中，数字标号表示关卡： 现将上面的路线图，按记录结构存储如下：12187312419851316614159170111222345681011111112NoPRE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算
6、法。二、根据题目要求，补充完善以下伪代码程序： 求出二个整形数组错位相加的最大面积。 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)是，其面积的定义为2461211 2数组错位相加的定义 设有2个正整数的数组a，b，长度为n，当n=5时： a=(34,26,15,44,12) b=(23,46,4,0,18) 对
7、a、b进行错位相加，可能有下列情况 34 26 15 44 12 +) 23 46 4 0 18 34 26 15 44 12 23 46 4 0 18 或： 34 26 15 44 12 +） 23 46 4 0 18 34 26 15 44 35 46 4 0 18 或： 34 26 15 44 12 +） 23 46 4 0 18 34 26 15 67 58 4 0 18 或： 最后有： 34 26 15 44 12 +) 23 46 4 0 18 - 23 46 4 0 18 34 26 15 44 12 可以看到：由于错位不同，相加的结果也不同。 程序要求：找出一个错位相加的方案，
8、使得输出的数组面积为最大。 算法提要： 设a，b的长度为10，用a,b: array1.10 of integer表示，其结果用数组C,D: array1.30 of integer表示。 错位相加的过程可以从开始不重叠，然后逐步重叠，再到最后的不重叠。 梯形面积的计算公式为：(上底+下底)高2 其中由于约定高为1，故可写为(上底+下底)2。 程序： n = 10; Function sea : real; 计算数组C面积 Begin J1 := 1; While _ do j1 := j1 + 1; ENDWHILE; If j1 = 3 * n then sea := 0 Else beg
9、in J2 := 3 * n; While _ do j2 := j2 - 1; If j1 = j2 then sea := 0 Else begin J3 := cj1 + cj2; For j4 := j1 + 1 to j2 - 1 do INC(j3,cj4*2); ENDFOR; Sea := j3 / 2 end ENDIF; 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 do for j := 1 to
10、 3 * n do _ endfor; for j := 1 to n do cj + n := aj endfor; for j := 1 to n do _; endfor; p := sea; if p s then begin d := c; s := p end; endif; endfor; for I := 1 to 3 * n do write(dI, ); endfor; write(s); End. /主程序结束/ 表的操作：设有一个表，记为L=（a1, a2, , an），其中： L：表名 a1, a2, , an为表中的元素 当ai为09数字时，表示元素，ai为大写字母
11、时, 表示是另一个表，但不能循环定义。 例如下列表的定义是合法的。（约定L是第一个表的表名） L=(1,3,K,8,0,4) K=(3,P,4,H,7) P=(2,3) H=(4,0,5,3) 程序要求：当全部表给出之后，求出表中所有元素的最大元素，以及表中全部元素的和。 算法提要：表用记录类型定义： 长度（LENGTH） 表体（是元素为字符类型的数组ELEMENT） 队列用数组BASE表示； 队列指针用整型变量 FRONT 与REAR。 为此，设计一个字符入队的过程inqueue，出队函数outqueue，表中最大元素及元素求和均采用递归计算。 程序： PROCEDURE INQUEUE(Q
12、，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(0); FOR i:=1 to TC.LENGTH DO Ch := tc.elementi; If _ then m := maxnumber(ch) Else m := ch
13、ENDIF; If max m then max := m EndIF; ENDFOR; _ End; /函数结束/ Function total(c) /函数需要一个参数，C：字符类型/ K := 0; For i:= 1 to tc.length do Ch := tc.Elelmenti; If _ then m := total(ch); Else m := ord(ch)-ord(0); endif K := k + m Endfor; Total := k;End; /函数结束/ /主程序/ Max := 36; For tabno := A to Z do ttabno.leng
14、th := 0; ENDFOR； q.front := 0; q.rear := 0; inqueue(q,L); while (q.front Q .rear ) do tabno := outqueue(q); write(tabno, =); readln(s); i := 1; While si ( do i := i+ 1; ENDWHILE; While si ) do If (si=a) and (si=A) and (si=0) andn (si=9) then inc(ttabno.length); ttabno.elementttabno.length := si endi
15、f; inc(i) Endif; endwhile; endwhile; WRITE(The max number in table L is:, maxnumber(L); WRITE(Total is:, total(L) END. /主程序结束/ 设有一个实数，以字符串形式存放于数组x中，用x：array1.Nof char表示。其中x1若为-，表示负数；若为+、.或 ，则表示正数。若为数字，也认为是正数。 例如 x=( ,2,0, ,3,.,5,%) 则表示203.5 x=(-,1,., ,2,0,%) 则表示-1.2 约定：在字符串x中，除x1外，其后可以包含有若干个.与 ，但仅以第
16、一次出现的为准，空格不起任何作用，并以字符%作为结束标志。 程序要求：将输入的字符串还原成实数输出（小数点后无用的0应除去），还原的结果以下列形式存放（不需要输出）。 F：数符。正数放0，负数放1。 A：array1.N of integer; 存放数字，不放小数点。 K：表示A中有效数字的个数。 J：表示小数点后的位数。 例如：数203.24，还原后结果的存放是： F=0 A=(2, 0, 3, 2, 4) K=5 J=2 又如：数-33.0740，还原后结果的存放是： F=1 A=(3, 3, 0, 7, 4) K=5 J=3 算法提要：x : array1.10 of char;可放长度
17、定为10；首先读入字符串，然后处理数的符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小数点，并约定输入是正确的，不用作出错检查。 程序： For I := 1 to 10 do aI := 0; ENDFOR; For I := 1 to 10 do read(xI); ENDFOR; J := 0; f := 0; k := 0; b := 0; If x1 = - then begin _ _ End Else if x1 := then I := 2 Else I := 1; ENDIF; ENDIF; While _ do I := I + 1; ENDWHIL
18、E While _ do If (xI = 0) and (xI 0 then while ak=0 do _ _ EndWHILE; EndIF.END. /程序结束/NOI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组） 试题参考答案一、 基础题：共33分 本题共4分显示结果不相同，和比多出一个文件目录。 本题共9分列出的一个相应问题是：（能列出类似的问题均可）用五角钱换成5分、2分与1分的硬币，有多少种换法。 本题共8分这四对球匹配的情况为：ABCD4312 本题共12分从存贮数据中求出从入口到出口经过最少关卡路径的算法及输出结果：算法： 输出结果：I:=
19、1; （17） WHILE NOI 17 DO I:=I+1; （16） ENDWHILE; REPEAT （19） WRITE(,NOI,); WRITE(); （18） I:=PREI; UNTIL I=0; 1二、 根据题目要求，补充完善以下伪代码程序：（共67分） 共10分（每空二分）1 CJ1=0 AND J1J13 S:=04 CJ:=O;5 CI+J-1:=CI+J-1+BJ; 共25分（每空五分）（Q.REAR+1） MOD (MAX+1);（Q.FRONT+1） MOD (MAX+1);（CH=A）AND （CH=A）AND （CH=Z） 共32分（每空四分）1 F：=1；2 I：=2；3 （XI ）AND （I10）4 XI %5 AK:=ORD(XI-ORD(0);6 J:=J+1;7 J:=J-1;8 K:=K-1;
