第二届全国青青年信息学奥林匹克联赛初赛试题提高组Pascal语言

1、第二届全国青青年信息学（运算机）奥林匹克分区联赛初赛试（高中组）（PASCAL语言竞赛历时：2小时）全数试题答案均要求写在答卷纸上，写在试卷纸上一概无效一、基础知识部份：（39分）1.已知A盘上的目录和文件组织如下：（2+3=5分）TPD11rFL.TXTIF2,TXTTB-.DOSD31F3.DOC-F4.DOCFOmT.COM其中TP、TB、DOS、DI、D31都是子目录名。设当前命令提示符为A:TB,请写出完成如下操作的DOS命令：在DOS运行中，没有执行过PATH命令，现要用DOS子目录中的FORMAT命令,对插入在B驱动器（英寸高密）中的360KB软盘进行格式化工作，请写出相应的操作

2、命令。互换与两个文件的内容。2 .请用等号或不等号联接表示以下不同进位制数值的大小。（3分）例如:（3）10（4）10=（100）2（A）16其中圆括号外右下角的下标，表示圆括号内数的进位制。（）1081623 .阅读以下程序段，写出程序运行后数组元素Al,A2,，All中的值0(6分)Al：=1：A2：=1：K：=1；REPEATAK+2：=1：FORI：=K+1DOWNTO2DOAIJ：=AI+AL1:K：=K+1：UNTILK>=I0：4 .已知：ACK(M,N)函数的计算公式如下：(4%)rN+lM=0ACK(M,N)=一ACK(M-l,1)N=0-ACK(M-l,ACK(M,N

3、-l)M¥0且NW0请计算：ACK(1,3)、ACK(2,4)、ACK(3,3)、ACK(3,4)5 .有NXN个数据组成如下方阵：（5分）AhAnAbAjnA21A22A23A：nA31A32A33A3N'AniAnzAn3Ann并已知：Aij=A"现将Au,A21,A22,A31,A32,A33,存储在一维数组A，A2,，A（N*（N+D）中。试问：任给i，j如何求出K来，使得AK的值正好是Aij,请写出由i,j计算K值的表达式。6 .已知：Ai,A?,Asi共有81个数，其中只有一个数比其它数大，要用最少的比较运算次数，把那个值大的数找出来（假设两个数比较一次

4、能决定出大于、小于或等于这三种情形）请将以下算法补充完整：（9分）第一步：SI=A+A2+Az7S2=Aas+A29+A54第一次比较（SI,S2）：SI>S2取K=0SI<S2取K=27SI=S2取K=54第二步：S1=Ak+1+Ak.2+Ak+9S2=Ak+io+Ak.u+Ak+is第二次比较(SI,S2)：SI>S2取K=SI<S2取K=SI=S2取K=第三步：SI=Ak+1+Ak.2+Ak+3S2=Ak+4+Ak+5+Ak+6第三次比较（S1,S2)*SI>S2取K=SI<S2取K=SI=S2取K=第四步：S1=Ak+iS2=Ak+2第四次比较（Si

5、,S2)*SI>S2为最大数SI<S2为最大数，SI=S2为最大数。7 .下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，表示存储数据终止）。现要求画出对应该存储结构的二叉树示用意。（7分）123456789101112131415ABC#DE#GF二、依照题目要求，完善程序：（61分）1.题目21分（3-H+3+3+4+4）积木游戏：设有n个小木块排成一排，如以下图：游戏开始时，每一个小木块向下的一面涂有红、黄、蓝三种颜色当中的一种（约定：0表示红色，1表示黄色，2表示兰色）。要求通过翻看与互换

6、方式对小木块从头排列（翻看的规那么为每一个小木快只能看一次），最终成为下面的形状： 红蓝黄即相同颜色的木块排列在一路，设计一个翻看与互换的方案，使得用最少的互换次数实现上面的要求。算法描述翻看小木块时，能够从两头进行。例如，设中间状态如下： 园口同0红未翻过蓝黄现在，能够从两个方向看，即从A或B处开始：（1）假设看A那么有三种可能性：为红色，那么不用互换为兰色，互换一次，即A与B互换为黄色，互换两次，即C与B互换一次，然后A与C再互换一次现在，平均互换次数为1。（2）假设看B,也有三种可能性：为兰色，那么不用互换为红色，互换一次，即B与A互换。为黄色，互换一次，即B与C互换。现在，平均互换次数

7、为2/3。由此可见，从B处翻看直到游戏终止，次数最少符合题目要求。程序PROGRAMEXP1（INPUTOUTPUT）CONSTN=20;VARI.TEMRBYINTEGER:A:ARRAYL.NOF0.2;BEGINFORI:=lTONDOREAD（A|I）;R:=l;Y:=N;WHILEDOIFTHENBEGINTEM:=AR;AR:=AB;AfB:=TEM:R:=R+1ENDELSEIFTHENBEGINTEM:=ABJ;AB:=AY;AY:=TEM;；：ENDELSEB:=B-1FORI:=lTONDOWRITE(AI:3)END.2.题目（20分，每空4分）4色问题。设有以下形状的图

8、形：（N=8）,其编号为1,2,，No图形之间的相邻关系用下面的邻接矩阵表示:1234567801000011101001100101010000101I0000010100011110101100010110000010其中：1相邻，0不相邻。程序要求将上而图形的每一个部份涂上红（1），黄（2）,蓝（3）,绿（4）四种颜色之一，要求相邻的部份有不同颜色。输入方式：邻接矩阵。输出方式：区域、颜色。算法描述用数组R：ARRAY1.NJ.NOF0.1表示相邻关系，S:ARRAY1.NOFINTEGER表示颜色。采纳回溯的方式，第一给第一个图形涂上红色（1）,然后在下而的图形中依次涂上其他颜色，当有

9、矛盾时回溯解决。程序PROGRAMEXP2（INPUT.OUTPUT）;CONSTN=8;VARIJKINTEGER;R:ARRAY1.NJ.NOF0.1;S:ARRAYf1.NOFINTEGER:BEGINFORI:=1TONDOBEGINFORJ:=lTONDOREAD(RIJ);READLNEND;：I:=2;J:=1;WHILEI<=NDOBEGINWHILE(J<=4)AND(I<=N)DOBEGINK:=l;WHILEDOK:=K+1;IFK<ITHENELSEBEGIN ；J：=lENDEND;IFJ>4THENBEGINEND;END;FORI:=

10、lTONDOWRITELN(I/->'.SI)END.3.题目(20分，每空4分)多项式加法运算：一个仅含有x的多项式能够用以下的方式表示：(系数，指数)，(系数，指数)，(0,0)o其中(0,0)作为终止标志。例如：P(x)=4x6-3x3+2x2-l可表示为：(4.6),(-3,3),(2,2),(-1.0),(0,0)Q(x)=x<x+1可表示为：(1,4),(-1,1),(1,0),(0,0)当用上面的方式给出2个多项式以后，编制程序对这两个多项式进行加法运算，结果也用上面的方式给出。例如:上面的P(x)和Q(x)相加的结果为:4x6+x4-3x3+2x2-x表示结

11、果为：(4,6),(1,4),(-3,3),(2,2),(-1,1),(0,0)算法描述多项式可用数组P表示；别离以pl表示P，p2表示Q,p3表示结果。处置的进程为将P复制到p3,然后逐项检查Q,当发觉有相同的方次时，进行系数相加：当发觉没有相同方次时，插入到p3中去。程序PROGRAMEXP3(INPUTQUTPUT)VARX.Y.LI1JJ1.J2:INTEGER;P1.P2T3:ARRAY1.20J.2OFINTEGERBEGINJI:=0;WRITECINPUTP(X)=r);READ(X.Y);WHILEXoODOBEGINJ1:=J1+1;P1J1J:=X;P1JL2:=Y;RE

12、AD(X.Y)END;J1:J1+1;P1JM:=O;P1J1,2:=O;WRITE(INPUTQ(X)=);READ(X,Y);J2:=0;WHILEXoODOBEGINJ2:=J2+1;P2J2,1:=X;P2J2,2:=Y;READ(X.Y)END;J2:=J2+1;P2J2J:=O;P2J2,2:=O;FORI:=1TOJIDOBEGINP3IJ:=P1(IJ;P3L2:=P1|L2END;I:=l;WHILEDOBEGINIFTHENBEGINFORJ:=J1DOWNTO1DOBEGINP3J+1J:=P3J,1;P3J+1:=P3J,2END;P3L1:=P2|L1;P3I,2:=P2I,2;J1:=J1+1ENDELSEBEGINWHILEP2I,2<P3IL2DO；IFP2I,2=P3I1,2THENP3nl.1:=ELSEBEGINFORJ:=J1DOWN