95高初试题

首届“同创杯”全国青少年信息学（计算机）奥林匹克竞赛

分区联赛初赛试题（高中组）竞赛用时：2小时

一、基础题

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

FORMAT	COM	12145
SYS	COM	4878
PUC	BAT	126
XCOPY	EXE	11216

4File(s) 123456 bytes free

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

② C>DIR > DF.TXT
③C> TYPE DF.TXT
④C> DIR
试问：执行命令③和④在屏幕上显示的结果是否与①相同？

<2>．列举一个问题，使问题的解能对应相应的算法
例如对算法 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;
请列出一个相应的问题。

<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>．求出二个整形数组错位相加的最大面积。 1.数组面积的定义：（限定数组头尾不为0） 设有一个数组C=（4, 8 , 12 , 0 , 6），
则C的面积的定义为：

Sc=(4+8) / 2 + (8+12) / 2 + 12 / 2 + 6 / 2

也就是说，Sc=各梯形面积之和（其中梯形的高约定为1，三角形作为梯形的特殊情况处理）。

又如D= ( 12 , 24 , 6 ) 时，其面积的定义为：

Sd= (12+24 ) / 2 + ( 24 + 6 ) / 2

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 ] of integer 表示，其结果用数 组c, d : array [ 1 . . 30 ] of integer表示。

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

梯形面积的计算公式为：(上底+下底)* 高/2，其中约定高为1，故可写为（上底+下底）/2。

程序：
const n = 10;
……
function sea : real; {计算数组C面积}
begin
j1:=1;

if j1 = 3*n then sea:=0
else begin
j2:=3*n;

if j1 = j2 then sea:=0
else begin
j3:=c[j1] + c[ j2 ];
for j4:=j1+1 to j2-1 do j3:= j3 + c[j4]*2; sea:=j3/ 2
end
end;
begin {主程序}
for i:=1 to n do read (a[ i ]);
for j:=1 to n do read (b[ j ]);
③ ;
for i:=1 to 2*n+1 do
begin

for j:=1 to 3*n do	④	;

for j:=1 to n do c[ j+n ]:= a [ j ];

for j:=1 to n do	⑤	;

p:=sea;
if p > s then begin
d:=c;
s:=p
end;
end;
for i:=1 to 3*n do write (d[ i ] , ‘ ’); writeln;
writeln(‘s=’ , s)
end.

<2>．表的操作：设有一个表，记为L＝（a1,a2,…,an），其中：

L：表名； a1,a2,…,an为表中元素；

当ai为0～9数字时，表示元素，为大写字母时表示是另一个表，但不能循环定义。例如下列表的定义是合法的（约定L是第一个表的表名）。

L＝（1，3，K，8，0，4）
K＝（3，P，4，H，7）
P＝（2，3）
H＝（4，0，5，3）

程序要求：

当全部表给出之后，求出表中所有元素的最大元素，以及表中全部元素的和。

【算法提要】表用记录类型定义：设lmax为表中元素最大个数

tabtype= record
length: 0..lmax; {长度}
element: array [1..lmax] of char; {表体}
end;
再定义队列： qtype= record
base: array [0..lmax] of char;
front, rear : 0..lmax;
end;
为此，设计一个字符入队的过程inqueue，出队函数outquere，表中最大元素及元素求和均采用递归计算。

程序：
const lmax = 38 ;
……
var t : array [ ‘A’ . . ‘Z’ ] of tabtype;
s: string [ lmax ];

procedure inqueue ( var q : qtype; c : char ); begin

q.base[ q.rear ] := c
end;

function outqueue ( var q : qtype ) : char;
begin

outqueue:= q.base [ q.front ]
end;

function maxnumber ( c : char ) : char;
var max : char;
begin
max:= chr (0);
for i:=1 to t[c].length do
begin
ch:= t[c].element[i];
if ③ then m := maxnumber (ch)
else m := ch;

if max<m then max:=m
end;
④
end;

function total ( c : char ) : integer;
var k , i : integer;
begin
k:= 0;
for i := 1 to t[c].length do
begin
ch:= t[c]. lelment[ i ];

else m := ord (ch)–ord(‘0’); k:= k + m
end;
total:= k
end;

begin
max: = 36;
for tabno := ’A’ to ‘Z’ do t [tabno]. length := 0;
q.front:= 0; q.rear:= 0;
inqueue(q , ’L’);
while q. front <> q. rear do
begin
tabno:= outqueue (q);
write( tabno , ‘=’ );
readln(s);
i:= 1;
while s[ i ] <> ‘(’ do i:=i+1;
while s[ i ] <> ‘)’ do
begin
if (s[ i ] >= ‘a’) and (s[ i ] < = ’z’)
then s[ i ]:= chr ( ord (s[ i ]) + ord (‘A’)-ord (‘a’) ); if (s[ i ] >= ‘A’) and (s[ i ] < = ‘Z’)
then begin
inc( t [ tabno ]. length );
t[ tabno ]. element [ t [ tabno ]. length ] := s[ i ];

inqueue( q , s[ i ] )
end
else if ( s[ i ] >= ’0’) and (s[ i ] < = ’9’)
then begin
inc( t [ tabno ]. length );
[tabno ]. element [ t [ tabno ]. length ]:= s[ i ] end;
inc( i )
end;
end;
writeln(‘the max number in table L is : ’, maxnumber (‘L’) ); writeln(‘Total is : ’ , total (‘L’) )
end.

中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 ] 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: array [ 1 . . 10 ]ofchar; 可放长度定为10；首先读入字符串，然后处理

数的符号，在还原的过程中，需要判定正数部分与小数部分，同时去除多余的空格和

小数点，并约定输入是正确的，不用作出错检查。

程序：

begin
for i:=1 to 10 do a[ i ]:=0;
for i:=1 to 10 do read (x [ i ]);

if x [1]= ‘-’ then begin
①

②
end
else if x[1]:= ‘ ’ then i := 2
else i := 1;

begin
if ( x[ i ] > = ‘0’ ) and ( x[ i ] < = ‘ 9’ )
then begin
k:= k + 1;
⑤ ;

if b=1 then

⑥

end
else if ( x[ i ] = ’ . ’ ) and ( b = 0 ) then b := 1; i:= i + 1
end
if j > 0 then while a[ k ]=0 do begin
⑦

⑧ end
end.