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

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

《“同创杯”全国青少年信息学(计算机)奥林匹克竞赛试题.docx》由会员分享，可在线阅读，更多相关《“同创杯”全国青少年信息学(计算机)奥林匹克竞赛试题.docx（8页珍藏版）》请在冰点文库上搜索。

答 题要 求

一、全部试题答案均应写在答卷纸上，写在试卷纸上一概无效。

二、算法描述中，可以使用下列过程、函数或算符：

（1）算术运算：

＋，－，×，／，DIV，MOD

整数除（DIV）：

是取二整数相除的商的整数部分。

如：

11DIV2=5

取模（MOD）：

是取二整数相除的余数。

如：

11MOD2=1

（2）关系运算：

>，<，=，<>，>=，<=

（3）逻辑运算：

AND，OR，NOT

（4）函数：

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）=225SQRT（225）=15

TRUNC（-7.9）=-7

如：

ROUND（3.14）=3 ROUND（3.16）=4 ROUND（-3.14）=-4

ORD（X）：

函数值是字符在ASCII码中的序号。

如：

ORD（‘A’）=65 ORD（‘B’）=66 ORD（‘Z’）=90 ORD（‘0’）=48

CHR（X）：

X表示ASCII码中的序号，函数值是该序号代表的字符值。

如：

CHR（48）=’0’

（5）过程：

CHR（65）=’A’

CHR（90）=’Z’

DEC（A,[X]）：

变量递减，A为有序变量，X缺省时为1。

INC（A,[X]）：

变量递增，A为有序变量，X缺省时为1。

NOI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组） 竞赛用时：

2小时

一、基础题：

<1>执行①C>DIR命令后，屏幕上显示如下画面：

FORMAT

COM

12145

SYS

COM

4878

PUC

BAT

126

XCOPY

EXE

11216

4FILE（S）123456 bytesfree

接着又顺序执行了如下几条DOS命令：

②C>DIR>DF.TXT //表示将列表显示的目录作为文件写盘//

③C>TYPE DF.TXT

④C>DIR

试问：

执行命令③和④在屏幕上显示的结果是否与①相同?

<2>列举一个问题，使问题的解能对应相应的算法。

例如对算法：

X：

=10；

8

可列举出如下的问题：

Y：

=5；READ（M，N）；S：

=X*M-Y*N；

学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M）与答错的题数（N），求最后得分（S）是多少？

现有以下算法：

K：

=0；

FORI：

=0 TO10 DOK：

=K+（50-I*5）DIV2+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）的可行路线图中，数字标号表示关卡：

现将上面的路线图，按记录结构存储如下：

1 2 3 4 5 6 7 8 910 111213 14 15 1617 18

1 2 18 7 3 12 4 19 8 5 13 16 6 1415 9 17…

0 1 1 1 2 2 2 3 4 5 6 8 10 1111 1112…

NoPRE

请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。

二、根据题目要求，补充完善以下伪代码程序：

<1>求出二个整形数组错位相加的最大面积。

1.数组面积的定义：

（限定数组头尾不为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）是，其面积的定义为



12

8 6

1 1 1 1

24

12

6

Sd=（12+24）/2+（24+6）/2

1 1

2.数组错位相加的定义

设有2个正整数的数组a，b，长度为n，当n=5时：

a=（34,26,15,44,12） b=（23,46,4,0,18）

对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

可以看到：

由于错位不同，相加的结果也不同。

程序要求：

找出一个错位相加的方案，使得输出的数组面积为最大。

[算法提要]：

设a，b的长度为10，用a,b:

array[1..10]ofinteger表示，其结果用数组C,D:

array[1..30]ofinteger表示。

错位相加的过程可以从开始不重叠，然后逐步重叠，再到最后的不重叠。

梯形面积的计算公式为：

（上底+下底）×高÷2

其中由于约定高为1，故可写为（上底+下底）÷2。

程序：

n=10;

Functionsea:

real;{计算数组C面积}Begin

J1:

=1;

While ① doj1:

=j1+1;

ENDWHILE;

If j1=3*n thensea:

=0

Elsebegin

J2:

=3*n;

While ② doj2:

=j2-1;

If j1=j2 thensea:

=0

Elsebegin

J3:

=c[j1]+c[j2];

Forj4:

=j1+1toj2-1doINC（j3,c[j4]*2）;

ENDFOR;

Sea:

=j3/2end

ENDIF;

End;

//主程序//

Fori:

=1tondoread（a[I]）;endfor;Forj:

=1tondoread（b[j]）;endfor;

③ ;

for i:

=1to2*n+1do

for j:

=1to3*ndo ④



endfor;

for j:

=1tondoc[j+n]:

=a[j] endfor;for j:

=1tondo

⑤ ;

endfor;p:

=sea;

ifp>sthenbegin

d:

=c;s:

=p

end;

endif;endfor;

forI:

=1to3*ndowrite（d[I],''）; endfor;write（s）;

End. //主程序结束//

<2>表的操作：

设有一个表，记为L=（a1,a2,…,an），其中：

L：

表名

a1,a2,…,an为表中的元素

当ai为0~9数字时，表示元素，ai为大写字母时,表示是另一个表，但不能循环定义。

例如下列表的定义是合法的。

（约定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，表中最大元素及元素求和均采用递归计算。

程序：

PROCEDUREINQUEUE（Q，C）; //过程需要二个参数，Q记录类型，C字符类型//Q.REAR:

= ① ;

Q.BASE[Q.REAR]:

=C；

END; //过程结束//

FUNCTIONOUTQUEUE（Q） //函数需要一个参数，Q记录类型//Q.FRONT:

= ② ;

OUTQUEUE:

=Q.BASE[Q.FRONT]

END； //函数结束//

FUNCTIONMAXNUMBER（C）//函数需要一个参数，C字符类型//Max:

=CHR（0）;

FORi:

=1toT[C].LENGTHDOCH:

=T[C].ELEMENT[i];

IF ③ THEN

M:

=MAXNUMBER（CH）ELSE

M:

=CH

ENDIF;

IF MAX

MAX:

=M

ENDIF;

ENDFOR;

④

END; //函数结束//

FUNCTIONTOTAL（C） //函数需要一个参数，C：

字符类型//K:

=0;

FORi:

=1TOT[C].LENGTHDOCH:

=T[C].ELELMENT[i];

IF ⑤ THEN

M:

=TOTAL（CH）;ELSE

M:

=ORD（CH）-ORD（'0'）;

ENDIF

K:

=K+MENDFOR;TOTAL:

=K;

END; //函数结束//

//主程序//

MAX:

=36;

FORTABNO:

='A'TO'Z'DOT[TABNO].LENGTH:

=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;

WHILES[i]<>'（'DOi:

=i+1;

ENDWHILE;WHILES[i]<>'）'DO

IF（S[i]>='A'）AND（S[i]<='Z'）THENS[i]:

=CHR（ORD（S[i]）+ORD（'A'）-ORD（'a'））;IF（S[i]>='A'）AND（S[i]<='Z'）THEN

INC（T[TABNO].LENGTH）;T[TABNO].ELEMENT[T[TABNO].LENGTH]:

=S[i];INQUEUE（Q,S[i]）;

ENDIF;

ELSE

IF（S[i]>='0'）ANDN（S[i]<='9'）THEN

INC（T[TABNO].LENGTH）;T[TABNO].ELEMENT[T[TABNO].LENGTH]:

=S[i]

ENDIF;

INC（i）

ENDIF;

ENDWHILE;

ENDWHILE;

WRITE（'ThemaxnumberintableLis:

',maxnumber（'L'））;WRITE（'Totalis:

',total（'L'））

END. //主程序结束//

<3>设有一个实数，以字符串形式存放于数组x中，用x：

array[1..N]ofchar表示。

其中x[1]若为'-'，表示负数；若为'+'、'.'或' '，则表示正数。

若为数字，也认为是正数。

例如 x=（'','2','0','','3','.','5','%'） 则表示203.5

x=（'-','1','.','','2','0','%'） 则表示-1.2

约定：

在字符串x中，除x[1]外，其后可以包含有若干个'.'与''，但仅以第一次出现的为准，空格不起任何作用，并以字符'%'作为结束标志。

程序要求：

将输入的字符串还原成实数输出（小数点后无用的0应除去），还原的结果以下列形式存放（不需要输出）。

F：

数符。

正数放0，负数放1。

A：

array[1..N]ofinteger;存放数字，不放小数点。

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:

array[1..10]ofchar;可放长度定为10；首先读入字符串，然后处理数的符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小数点，并约定输入是正确的，不用作出错检查。

程序：

FORI:

=1TO10DOA[I]:

=0; ENDFOR;FORI:

=1TO10DOREAD（X[I]）;ENDFOR;J:

=0;F:

=0;K:

=0;B:

=0;

IFX[1]='-'THENBEGIN

①

②

END

ELSEIFX[1]:

='' THENI:

=2

ELSEI:

=1;

ENDIF;

ENDIF;

WHILE ③ DOI:

=I+1;

ENDWHILE

WHILE ④ DO

IF（X[I]>='0'）AND （X[I]<='9'） THEN

K:

=K+1;

⑤ ;IF B=1 THEN

ELSEIF（X[I]='.'）AND（B=0）THEN



ENDIF

 ⑥

ENDIFI:

=I+1

ENDIF;ENDWHILE;

IF J>0 THEN WHILEA[K]=0DO

B:

=1;

ENDIF.

END. //程序结束//

 ⑦

⑧

ENDWHILE;