noipNOIP1996提高组初赛试题

第二届全国青少年信息学（计算机）奥林匹克分区联赛初赛试 （高中组） （PASCAL 语言 竞赛用时：2小时） ●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●● 一、基础知识部分：（39分） 1． 已知A盘上的目录和文件组织如下:（2+3=5分） 其中TP、TB、DOS、D11、D31都是子目录名。 设当前命令提示符为 A:＼TB> ,请写出完成如下操作的DOS 命令： ① 在DOS运行中，没有执行过PATH命令，现要用DOS子目录中的FORMAT命令，对插入在B驱动器（5.25英寸高密）中的360KB软盘进行格式化工作,请写出相应的操作命令。 ② 交换F2.TXT与F3.DOC两个文件的。 2．请用等号或不等号联接示下列不同进位制数值的大小。（3分） 例如：（3）10 <(4)10 =(100)2 < ( A )16 其中圆括号外右下角的下标，表示圆括号内数的进位制。 （98.375）10 (142.3)8 (58.5)16 (1011000.0101)2 3．阅读下列程序段，写出程序运行后数组元素A1，A2，…，A11中的值 。（6分） A[1]：=1； A[2]：=1 ； K：=1 ； REPEAT A[K+2]：=1 ； FOR I：=K+1 DOWNTO 2 DO A[I]：=A[I] +A[I-1 ] ； K：=K+1 ； UNTIL K>=10 ； 4．已知：ACK（M，N）函数的计算公式如下： （4%） N+1 M=0 ACK（M，N）= ACK（M-1，1） N=0 ACK（M-1，ACK（M，N-1） M≠0 且N≠0 请计算：ACK（1，3）、ACK（2，4）、ACK（3，3）、ACK（3，4） 5．有N×N个数据组成如下方阵：（5分） A11 A12 A13 …… A1N A21 A22 A23 …… A2N A31 A32 A33 …… A3N ………… AN1 AN2 AN3 …… ANN 并已知： Aij = Aji 现将A11 ，A21，A22 ，A31 ，A32 ，A33 ，…存储在一维数组A[1]，A[2]，…，A[（N*（N+1））/2] 中。 试问：任给i，j怎样求出K来，使得A[K]的值正好是Aij，请写出由i，j计算K值的表达式。 6．已知：A1，A2，……，A81 共有81个数，其中只有一个数比其它数大，要用最少的比较运算次数，把这个值大的数找出来（假设两个数比较一次能决定出大于、小于或等于这三种情况）请将以下算法补充完整：（9分） 第一步： 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 为最大数。 7．下面是一个利用完全二叉树特性，用顺序表来存储的一棵二叉树，结点数据为字符型（结点层次号从小到大，同一层从左到右顺序存储，#表示空结点，@表示存储数据结束）。 现要求画出对应该存储结构的二叉树示意图。（7分） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C # # D E # # # # # G F @ 二、根据题目要求，完善程序：（61分） 1．[题 目] 21分（3+4+3+3+4+4） 积木游戏：设有n 个小木块排成一排，如下图： …… 游戏开始时，每个小木块向下的一面涂有红、黄、蓝三种颜色之中的一种（约定：0表示红色，1表示黄色，2表示兰色）。要求通过翻看与交换方式对小木块重新排列（翻看的规则为每个小木快只能看一次），最终成为下面的形状： …… …… …… 红 蓝 黄 即相同颜色的木块排列在一起，设计一个翻看与交换的，使得用最少的交换次数实现上面的要求。 [算法描述] 翻看小木块时，可以从两端进行。例如，设中间状态如下： …… A …… B …… C …… 红 未翻过 蓝 黄 此时，可以从两个方向看，即从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; ⑤ ; ⑥ ; end else b:=b-1 for I:=1 to n do write(a[I]:3) end. 2．[题 目] （20分，每空4分） 4色问题。 设有下列形状的图形：（N=8），其编号为1，2，……，N。 图形之间的相邻关系用下面的邻接矩阵表示： 1 2 3 4 5 6 7 8 1 0 1 0 0 0 0 1 1 2 1 0 1 0 0 1 1 0 3 0 1 0 1 0 1 0 0 4 0 0 1 0 1 1 0 0 5 0 0 0 1 0 1 0 0 6 0 1 1 1 1 0 1 0 7 1 1 0 0 0 1 0 1 8 1 0 0 0 0 0 1 0 其中：1——相邻，0——不相邻。 [程序要求] 将上面图形的每一个部分涂上红（1），黄（2），蓝（3），绿（4）四种颜色之一，要求相邻的部分有不同颜色。 输入方式：邻接矩阵。 输出方式：区域、颜色。 ………… [算法描述] 用数组R:ARRAY[1..N,1..N] OF 0..1表示相邻关系，S:ARRAY[1..N] OF INTEGER 表示颜色。 采用回溯的，首先给第一个图形涂上红色（1），然后在下面的图形中依次涂上其他颜色，当有矛盾时回溯解决。 ［程 序］ program exp2(inpuT,output); Const n=8; Var I,j,k:integer; R:Array[1..n,1..n] of 0..1; S:Array[1..n] of integer; 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 k4 then begin I:=I-1; ⑤ End; end; For I:=1 to n do writeln(I,'(',s[I]) End. 3．[题　 目] （20分，每空4分） 多项式加法运算：一个仅含有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表示；分别以p1表示P，p2表示Q，p3表示结果。 处理的过程为将P复制到p3，然后逐项检查Q，当发现有相同的方次时，进行系数相加；当发现没有相同方次时，插入到p3中去。 [程 序] PROGRAM EXP3(INPUT,OUTPUT) Var x,y,i,i1,j,j1,j2:integer; P1,P2,P3 :array[1..20,1..2] of integer Begin j1:=0; write('Input P(x)='); read(x,y); while x<>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 do begin j2:=j2+1; P2[j2,1]:=x; P2[j2,2]:=y; read(x,y) end; j2:=j2+1; P2[j2,1]:=0; P2[j2,2]:=0; for i:=1 to j1 do begin P3[I,1]:=P1[I,1]; P3[I,2]:=P1[I,2] End; I:=1; While ① do begin If ② then begin For j:=j1 down to 1 do begin P3[j+1,1]:=P3[j,1]; P3[j+1,2]:=P3[j,2] End; P3[I,1]:=P2[I,1]; P3[I,2]:=P2[I,2]; j1:=j1+1 End Else begin I1:=1; While P2[I,2]