“同创杯”全国青少年信息学(计算机)奥林匹克竞赛试题.docx

1、答题 要求一、全部试题答案均应写在答卷纸上，写在试卷纸上一概无效。二、算法描述中，可以使用下列过程、函数或算符：（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 SQR(X)：求 X 的平方值。如：SQR（3）=9SQRT(X)：求 X 的平方根值。如：SQRT(9)=3TRUNC(X)：去掉X 的小数部分：如TRUNC(6.3

2、)=6ROUND(X)：函数值是小数四舍五入后的整数值。ABS(-3.14)=3.14 SQR（-15）=225 SQRT(225)=15TRUNC(-7.9)=-7如：ROUND(3.14)=3ROUND(3.16)=4ROUND(-3.14)=-4ORD(X)：函数值是字符在ASCII 码中的序号。如：ORD(A)=65ORD(B)=66ORD(Z)=90ORD(0)=48CHR(X)：X 表示 ASCII 码中的序号，函数值是该序号代表的字符值。如：CHR(48)=0（5）过程：CHR(65)=ACHR(90)=ZDEC(A,X)：变量递减，A 为有序变量，X 缺省时为 1。INC(A,

3、X)：变量递增，A 为有序变量，X 缺省时为 1。NOI95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组）竞赛用时：2 小时一、基础题： 执行CDIR 命令后，屏幕上显示如下画面：FORMATCOM12145SYSCOM4878PUCBAT126XCOPYEXE112164 FILE（S） 123456bytes free接着又顺序执行了如下几条DOS 命令： CDIR DF.TXT/表示将列表显示的目录作为文件写盘 /CTYPEDF.TXTCDIR试问：执行命令和 在屏幕上显示的结果是否与相同? 列举一个问题，使问题的解能对应相应的算法。例如对算法：X：=10；

4、8可列举出如下的问题：Y：=5； READ（M，N）； S：=X*M-Y*N；学生答题，答对一题可得10 分，答错一题则要扣去5 分，输入答对的题数（M） 与答错的题数（N），求最后得分（S）是多少？现有以下算法：K：=0 ；FOR I：=0TO 10DO K：=K+（50-I*5）DIV 2+1请列出一个相应的问题。 有标号为A、B、C、D 和 1、2、3、4 的 8 个球，每两个球装一盒，分装4 盒。标号为字母的球与标号为数字的球有着某种一一对应的关系（称为匹配），并已知如下条件： 匹配的两个球不能在一个盒子内。 2 号匹配的球与1 号球在一个盒子里。 A 号和 2 号球在一个盒子里。 B

5、 匹配的球和C 号球在一个盒子里。 3 号匹配的球与A 号匹配的球在一个盒子里。 4 号是A 或B 号球的匹配球。 D 号与 1 号或 2 号球匹配。请写出这四对球匹配的情况。 从入口（1）到出口（17）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：123456789 1011 12 13141516 171812187312419851316614 15917 0111222345681011 1111 12 No PRE请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。二、根据题目要求，补充完善以下伪代码程序： 求出二个整形数组错位相加的最大面积。1

6、. 数组面积的定义：（限定数组头尾不为0）设有一个数组C=（4，8，12，0，6）则 C 的面积为：Sc=(4+8)/2 + (8+12)/2 + 12/2 + 6/2也就是说，Sc=各梯形面积之和（其中梯形的高约定为 1，三角形作为梯形的特殊4情况处理）。又如 D=(12, 24, 6)是，其面积的定义为1286111124126Sd=(12+24)/2 + (24+6)/2112. 数组错位相加的定义设有 2 个正整数的数组a，b，长度为n，当 n=5 时：a=(34,26,15,44,12)b=(23,46,4,0,18)对a、b 进行错位相加，可能有下列情况3426154412+)23

7、464018342615441223464018或：3426154412+）234640183426154435464018或：3426154412+）2346401834261567584018或： 最后有：3426154412+)23464018-234640183426154412可以看到：由于错位不同，相加的结果也不同。程序要求：找出一个错位相加的方案，使得输出的数组面积为最大。 算法提要： 设 a，b 的长度为 10，用 a,b: array1.10 of integer表示，其结果用数组 C,D: array1.30 of integer 表示。错位相加的过程可以从开始不重叠，然后

8、逐步重叠，再到最后的不重叠。梯形面积的计算公式为：(上底+下底)高2其中由于约定高为1，故可写为(上底+下底)2。程序：n = 10;Function sea : real; 计算数组 C 面积 BeginJ1 := 1;While do j1 := j1 + 1;ENDWHILE;Ifj1 = 3 * nthen sea := 0Else beginJ2 := 3 * n;While do j2 := j2 - 1;Ifj1 = j2then sea := 0Else beginJ3 := cj1 + cj2;For j4 := j1 + 1 to j2 - 1 do INC(j3,cj4*

9、2);ENDFOR;Sea := j3 / 2 endENDIF;End;/主程序/For i := 1 to n do read(aI); endfor; For j := 1 to n do read(bj); endfor; ;fori := 1 to 2 * n + 1 doforj := 1 to 3 * n do endfor;forj := 1 to n do cj + n := ajendfor; forj := 1 to n do ;endfor; p := sea;if p s then begind := c; s := pend;endif; endfor;for I

10、:= 1 to 3 * n do write(dI, );endfor; write(s);End./主程序结束/ 表的操作：设有一个表，记为L=（a1, a2, , an），其中： L：表名a1, a2 , , an 为表中的元素当 ai 为 09 数字时，表示元素，ai 为大写字母时, 表示是另一个表，但不能循环定义。例如下列表的定义是合法的。（约定 L 是第一个表的表名）L=(1,3,K,8,0,4)K=(3,P,4,H,7) P=(2,3) H=(4,0,5,3)程序要求：当全部表给出之后，求出表中所有元素的最大元素，以及表中全部元素的和。算法提要：表用记录类型定义：长度（LENGTH

11、）表体（是元素为字符类型的数组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 M

12、AXNUMBER(C) /函数需要一个参数，C 字符类型/ Max := CHR(0);FOR i:=1 to TC.LENGTH DO CH := TC.ELEMENTi;IF THENM := MAXNUMBER(CH) ELSEM := CHENDIF;IFMAX MTHENMAX := MENDIF;ENDFOR; END;/函数结束/FUNCTION TOTAL(C)/函数需要一个参数，C：字符类型/ K := 0;FOR i:= 1 TO TC.LENGTH DO CH := TC.ELELMENTi;IF THENM := TOTAL(CH); ELSEM := ORD(CH)-

13、ORD(0);ENDIFK := K + M ENDFOR; TOTAL := K;END;/函数结束/主程序/MAX := 36;FOR TABNO := A TO Z DO TTABNO.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 ) DOIF (Si=A) AND (

14、Si=A) AND (Si=0) ANDN (Si=9) THENINC(TTABNO.LENGTH); TTABNO.ELEMENTTTABNO.LENGTH := SiENDIF;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=(

15、,2,0, ,3,.,5,%)则表示 203.5x=(-,1,., ,2,0,%)则表示-1.2约定：在字符串x 中，除 x1外，其后可以包含有若干个.与 ，但仅以第一次出现的为准，空格不起任何作用，并以字符%作为结束标志。程序要求：将输入的字符串还原成实数输出（小数点后无用的0 应除去），还原的结果以下列形式存放（不需要输出）。F：数符。正数放0，负数放 1。A：array1.N of integer; 存放数字，不放小数点。K：表示A 中有效数字的个数。J：表示小数点后的位数。例如：数 203.24，还原后结果的存放是： F=0A=(2, 0, 3, 2, 4) K=5J=2又如：数-33

16、.0740，还原后结果的存放是：F=1A=(3, 3, 0, 7, 4) K=5J=3 算法提要：x : array1.10 of char;可放长度定为 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 ENDELSE IF X1 := THEN I := 2ELSE I := 1;ENDIF;ENDIF;WHILE DO I := I + 1;ENDWHILEWHILE DOIF (XI = 0) AND(XI 0THENWHILE AK=0 DOB := 1;ENDIF.END./程序结束/ ENDWHILE;