noi历年测试数据

NOI"95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛
分区联赛初赛试题（高中组） 竞赛用时：2小时
一、基础题：
<1> 执行①C>DIR 命令后，屏幕上显示如下画面：
FORMAT COM 12145
SYS COM 4878
PUC BAT 126
XCOPY EXE 11216
4 FILE（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 2 18 7 3 12 4 19 8 5 13 16 6 14 15 9 17 …
0 1 1 1 2 2 2 3 4 5 6 8 10 11 11 11 12 …
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。

二、根据题目要求，补充完善以下伪代码程序：
<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)是，其面积的定义为

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。

程序： n = 10;
Function sea : real; {计算数组C面积}
Begin
J1 := 1;
While _______①______ do
j1 := j1 + 1;
ENDWHILE;
If j1 = 3 * n then sea := 0
Else begin
J2 := 3 * n;
While _______②______ do
j2 := j2 - 1;
If j1 = j2 then sea := 0
Else begin
J3 := c[j1] + c[j2];
For j4 := j1 + 1 to j2 - 1 do
INC(j3,c[j4]*2);
ENDFOR;
Sea := j3 / 2
end
ENDIF;
End;

//主程序//
For i := 1 to n do read(a[I]); endfor;
For j := 1 to n do read(b[j]); endfor;
__________③____________;
for i := 1 to 2 * n + 1 do
for j := 1 to 3 * n do ________④__________ endfor;
for j := 1 to n do c[j + n] := a[j] 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(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，表中最大元素及元素求和均采用递归计算。
程序：
PROCEDURE INQUEUE(Q，C); //过程需要二个参数，Q记录类型，C字符类型//
Q.REAR := _________①__________;
Q.BASE[Q.REAR] := C；
END; //过程结束//

FUNCTION OUTQUEUE(Q) //函数需要一个参数，Q记录类型//
Q.FRONT := _________②__________;
OUTQUEUE := Q.BASE[Q.FRONT]
END； //函数结束//

FUNCTION MAXNUMBER(C) //函数需要一个参数，C字符类型//
Max := CHR(0);
FOR i:=1 to T[C].LENGTH DO
CH := T[C].ELEMENT[i];
IF _______③________ THEN
M := MAXNUMBER(CH)
ELSE
M := CH
ENDIF;
IF MAX < M THEN
MAX := M
ENDIF;
ENDFOR;
___________④____________
END; //函数结束//

FUNCTION TOTAL(C) //函数需要一个参数，C：字符类型//
K := 0;
FOR i:= 1 TO T[C].LENGTH DO
CH := T[C].ELELMENT[i];
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
T[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;
WHILE S[i] <> "(" DO
i := i+ 1;
ENDWHILE;
WHILE S[i] <> ")" DO
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
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("The max number in table L is:", maxnumber("L"));
WRITE("Total is:", total("L"))
END. //主程序结束//

<3> 设有一个实数，以字符串形式存放于数组x中，用x：array[1..N]of char表示。其中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] of char;可放长度定为10；首先读入字符串，然后处理数的符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小数点，并约定输入是正确的，不用作出错检查。
程序：
FOR I := 1 TO 10 DO A[I] := 0; ENDFOR;
FOR I := 1 TO 10 DO READ(X[I]); ENDFOR;
J := 0; F := 0; K := 0; B := 0;
IF X[1] = "-" THEN BEGIN
____________①____________
____________②____________
END
ELSE IF X[1] := " " THEN I := 2
ELSE I := 1;
ENDIF;
ENDIF;
WHILE ________③_________ DO
I := I + 1;
ENDWHILE
WHILE __________④___________ DO
IF (X[I] >= "0") AND (X[I] <= "9") THEN
K := K + 1;
_________⑤____________;
IF B = 1 THEN
______⑥_________
ENDIF
ELSE IF (X[I]=".") AND (B=0) THEN
B := 1;
ENDIF
I := I + 1
ENDIF;
ENDWHILE;
IF J > 0 THEN WHILE A[K]=0 DO
__________⑦_________
__________⑧_________
ENDWHILE;