96高初试题

第二届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题 （高中组）Pascal语言 竞赛用时：2小时
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、基础知识部分（44分）
1．已知A盘上的目录和文件组织如下：

TP D11 F1.TXT TB F2.TXT DOS D31 F3.DOC F4.DOC FORMAT.COM
其中TP、TB、DOS、D11、D31都是子目录名。

设当前命令提示符为A:\TB>，请写出完成如下操作的DOS命令：
①在DOS运行中，没有执行过PATH命令，现要用DOS子目录中FORMAT命令，对插入在 B驱动器（5.25英寸高密）中的360KB软盘进行格式化工作，请写出相应的操作命令。

② 交换F2.TXT与F3.DOC两个文件的内容，要求使用的命令不得超过三条；2．请用等号或不等号联接表示下列不同进位制数值的大小。

例如： (3)10 <(4)4 ＝(100)2 <(A)16
其中圆括号外右下角的下标，表示圆括号内数的进位制。

(98.375)10 (142.3)8 (58.5)16 (1011000.0101)23．阅读程序，写出程序段运行后数组元素a1, a2 , …,a11 中的值。

a[1]:=1; a[2]:=1; k:=1;
repeat
a[k+2]:=1;
fori:=k＋1downto 2 do a[i]:=a[i]+a[i-1]; k:=k+1;
untilk>=10;
4．已知：ack(m,n)函数的计算公式如下：

请计算：ack( 1 , 3 )、ack( 2 , 4 )、ack( 3 , 3 )、ack( 3 , 4 ) 的值

5．有N×N个数据组成如下方阵：

	A11 A12 A13…… A1N
	A21 A22 A23…… A2N
	A31 A32 A33…… A3N
	…………
	AN1 AN2 AN3…… ANN

并已知：AIJ=AJI
现将A11，A12，…，A1N，A22，A23，…，A2N，A33，A34，…，A3N，…，ANN存储在一维数组A[1]，A[2]，…，A[N*(N+1) / 2 ]中。

试问：任给I, J 怎样求出K来，使得A[K]的值正好是AIJ，请写出由I, J计算K的表 达式。

6．已知：A1, A2, …, A81共有81个数，其中只有一个数比其他数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这

三种情况）请将以下算法补充完整。

第一步： s1=A1+A2+ …+ A27
s2=A28+A29+ …+ A54
第一次比较(s1 , s2 )：
s1> s2 取K= 0
s1< s2 取K= 27
s1= s2 取K= 54

第二步： s1=AK+1+AK+2+ …+ AK+9
s2=AK+10+AK+11+ …+ AK+18
第二次比较(s1 , s2 )：

s1 > s2	取K = ①
s1 < s2	取K = ②
s1 = s2	取K = ③

第三步： s1=AK+1+AK+2+ AK+3
s2=AK+4+AK+5+ AK+6
第三次比较(s1 , s2 )：

s1 > s2	取K = ④
s1 < s2	取K = ⑤
s1 = s2	取K = ⑥

第四步： s1=AK+1
s2=AK+2
第四次比较(s1 , s2 )：

s1 > s2	⑦ 为最大数
s1 < s2	⑧ 为最大数
s1 = s2	⑨ 为最大数

要求画出对应该存储结构的二叉树示意图。

A B C # # D E # # # # # G F @

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

1．[[题 目]：
积木游戏：设有n个小木块排成一排，如下图：

□□□ …………□

游戏开始时，每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种（约定：0表示红色，1表示黄色，2表示蓝色）。要求通过翻看与交换方式对小木块重新排列（翻

看的规则为每个小木块只能看一次），最终成为下面的形状：

□□□ ……□ □□□ ……□ □□□ ……□

红

蓝

黄

即相同颜色的木块排列在一起，设计一个翻看与交换的方案，使得用最少的交换次

数实现上面的要求。

此时，可以从两个方向看，即从a或b处开始：
1．若看a则有三种可能性：
为红色，则不用交换
为蓝色，交换一次，即a与b交换
为黄色，交换两次，即c与b交换一次，然后a与c再交换一次 此时，平均交换次数为1
2．若看b也有三种可能性：
为蓝色，则不用交换
为红色，交换一次，即b与a交换
为黄色，交换一次，即b与c交换
此时，平均交换次数为2/3
由此可见，从b处翻看直到游戏结束，次数最少符合题目要求。

[程 序]： program exp1 (input , output);

const n = 20;
var i , tem , r , b , y : integer;

a: array [ 1 . . n ] of 0 . . 2;

begin

for i := 1 to n do read (a[ i ]);	r := 1;	① ; y := n;

while ② do

if	③ then begin

tem:= a[ r ]; a[ r ]:= a[ b ]; a[ b ] := tem; r := r + 1

end

else if	④	then begin
	tem := a[ b ];		a[ b ] := a[ y ];	a[ y ]:= tem;

begin
for i := 1 to n do begin
for j:=1 to n do read ( r [ i , j ]); readln; end;

① ;

i := 2;

j := 1;

while i < = n do begin
while ( j < =4 ) and (i < = n) do begin
k:= 1;
while ② do k := k + 1;
if k < i then ③
else begin
④ ; i:= i + 1; j := 1; end;
end;
if j > 4 then begin

i := i - 1;

⑤

end;
end;
for i := 1 to n do writeln ( i , ‘→’, s[ i ]) end.

3．[问 题]：

多项式加法运算：一个仅含有x的多项式可以用下列的方式表示：

(系数，指数)，(系数，指数)，……，(0，0)。其中(0, 0) 作为结束标志。

例如：P( x ) = 4x6–3x3+ 2x2–1可表示为：(4, 6)，(-3, 3)，(2, 2)，(-1, 0)，(0, 0)

Q( x ) = x4–x+1 可表示为：(1, 4)，(-1, 1)，(1, 0)，(0, 0)

当用上面的方式给出2个多项式之后，程序对这两个多项式进行加法运算，结果也用上面的方式给出。

例如：上面的P(x ) 和Q( x ) 相加的结果为： 4x6+x4–3x3+ 2x2–x

表示结果为：(4, 6)，(1, 4)，(-3, 3)，(2, 2)，(-1, 1)，(0, 0)

[算法描述]：多项式可用数组p: array [ 1 .. n , 1 .. 2 ] of integer 表示。

分别以p1表示p，p2表示q，p3表示结果。处理的过程为将p赋值到p3，然后逐项检查q，当发现有相同的方次时，进行系数相加；当发现没有相同方次时，插入到p3中去。

[程 序]：

var x , y , i , i1 , j , j1 , j2 : integer;
p1, p2 , p3 : array [ 1 .. 20 , 1 .. 2 ] of integer; begin

while (x <>0) or (y<>0) do begin

j1:= j1+1;

p1 [ j1, 1 ]:= x;

p1 [ j1, 2 ]:= y; read ( x , y ) ;

end;
j1:=j1+1; p1[j1 , 1 ]:= 0; p1[j1 , 2 ] := 0; write (‘ Input Q ( x ) = ’ ); read(x , y); j2 := 0;
while (x <>0) or (y<>0) do begin

p2[j2 , 2 ]:= y; read (x , y);

p3[i , 2 ] := p1[ i , 2 ]

p3[ j+1 , 1 ] := p3 [ j , 1 ]; p3[ j+1 , 2 ] := p3 [ j , 2 ]

p3[i1 , 2 ]:= p3[ i , 2 ];