NOIP1995提高组初赛试题

1NOI’95“同创杯”全国青少年信息学（计算机）奥林匹克竞赛分区联赛初赛试题（高中组）竞赛用时：2小时一、基础题：1执行①CDIR命令后，屏幕上显示如下画面：FORMATCOM12145SYSCOM4878PUCBAT126XCOPYEXE112164FILE（S）123456bytesfree接着又顺序执行了如下几条DOS命令：②CDIRDF.TXT//表示将列表显示的目录作为文件写盘//③CTYPEDF.TXT④CDIR试问：执行命令③和④在屏幕上显示的结果是否与①相同?2列举一个问题，使问题的解能对应相应的算法。例如对算法：X：=10；答题要求一、全部试题答案均应写在答卷纸上，写在试卷纸上一概无效。二、算法描述中，可以使用下列过程、函数或算符：（1）算术运算：＋，－，×，／，DIV，MOD整数除（DIV）：是取二整数相除的商的整数部分。如：11DIV2=5取模（MOD）：是取二整数相除的余数。如：11MOD2=1（2）关系运算：，，=，，=，=（3）逻辑运算：AND，OR，NOT（4）函数：ABS(X)：求X的绝对值。如：ABS（3.14）=3.14ABS(-3.14)=3.14SQR(X)：求X的平方值。如：SQR（3）=9SQR（-15）=225SQRT(X)：求X的平方根值。如：SQRT(9)=3SQRT(225)=15TRUNC(X)：去掉X的小数部分：如TRUNC(6.3)=6TRUNC(-7.9)=-7ROUND(X)：函数值是小数四舍五入后的整数值。如：ROUND(3.14)=3ROUND(3.16)=4ROUND(-3.14)=-4ORD(X)：函数值是字符在ASCII码中的序号。如：ORD(‘A’)=65ORD(‘B’)=66ORD(‘Z’)=90ORD(‘0’)=48CHR(X)：X表示ASCII码中的序号，函数值是该序号代表的字符值。如：CHR(48)=’0’CHR(65)=’A’CHR(90)=’Z’（5）过程：DEC(A,[X])：变量递减，A为有序变量，X缺省时为1。INC(A,[X])：变量递增，A为有序变量，X缺省时为1。2Y：=5；READ（M，N）；S：=X*M-Y*N；可列举出如下的问题：学生答题，答对一题可得10分，答错一题则要扣去5分，输入答对的题数（M）与答错的题数（N），求最后得分（S）是多少？现有以下算法：K：=0；FORI：=0TO10DOK：=K+（50-I*5）DIV2+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）的可行路线图中，数字标号表示关卡：现将上面的路线图，按记录结构存储如下：123456789101112131415161718请设计一种能从存储数据中求出从入口到出口经过最少关卡路径的算法。1218731241985131661415917…0111222345681011111112…NoPRE3二、根据题目要求，补充完善以下伪代码程序：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进行错位相加，可能有下列情况3426154412+)23464018342615441223464018或：3426154412+）234640183426154435464018或：3426154412+）2346401834261567584018或：……最后有：3426154412+)23464018-234640183426154412可以看到：由于错位不同，相加的结果也不同。程序要求：找出一个错位相加的方案，使得输出的数组面积为最大。[算法提要]：设a，b的长度为10，用a,b:array[1..10]ofinteger表示，其结果用数组C,D:array[1..30]ofinteger表示。错位相加的过程可以从开始不重叠，然后逐步重叠，再到最后的不重叠。梯形面积的计算公式为：(上底+下底)×高÷2其中由于约定高为1，故可写为(上底+下底)÷2。12246481216111Sd=(12+24)/2+(24+6)/2114程序：n=10;Functionsea:real;{计算数组C面积}BeginJ1:=1;While_______①______doj1:=j1+1;ENDWHILE;Ifj1=3*nthensea:=0ElsebeginJ2:=3*n;While_______②______doj2:=j2-1;Ifj1=j2thensea:=0ElsebeginJ3:=c[j1]+c[j2];Forj4:=j1+1toj2-1doINC(j3,c[j4]*2);ENDFOR;Sea:=j3/2endENDIF;End;//主程序//Fori:=1tondoread(a[I]);endfor;Forj:=1tondoread(b[j]);endfor;__________③____________;fori:=1to2*n+1doforj:=1to3*ndo________④__________endfor;forj:=1tondoc[j+n]:=a[j]endfor;forj:=1tondo_________⑤__________;endfor;p:=sea;ifpsthenbegind:=c;s:=pend;endif;endfor;forI:=1to3*ndowrite(d[I],'');endfor;write(s);End.//主程序结束//52表的操作：设有一个表，记为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，表中最大元素及元素求和均采用递归计算。程序：PROCEDUREINQUEUE(Q，C);//过程需要二个参数，Q记录类型，C字符类型//Q.REAR:=_________①__________;Q.BASE[Q.REAR]:=C；END;//过程结束//FUNCTIONOUTQUEUE(Q)//函数需要一个参数，Q记录类型//Q.FRONT:=_________②__________;OUTQUEUE:=Q.BASE[Q.FRONT]END；//函数结束//FUNCTIONMAXNUMBER(C)//函数需要一个参数，C字符类型//Max:=CHR(0);FORi:=1toT[C].LENGTHDOCH:=T[C].ELEMENT[i];IF_______③________THENM:=MAXNUMBER(CH)ELSEM:=CHENDIF;IFMAXMTHENMAX:=MENDIF;ENDFOR;___________④____________END;//函数结束//6FUNCTIONTOTAL(C)//函数需要一个参数，C：字符类型//K:=0;FORi:=1TOT[C].LENGTHDOCH:=T[C].ELELMENT[i];IF_________⑤__________THENM:=TOTAL(CH);ELSEM:=ORD(CH)-ORD('0');ENDIFK:=K+MENDFOR;TOTAL:=K;END;//函数结束////主程序//MAX:=36;FORTABNO:='A'TO'Z'DOT[TABNO].LENGTH:=0;ENDFOR；Q.FRONT:=0;Q.REAR:=0;INQUEUE(Q,'L');WHILE(Q.FRONTQ.REAR)DOTABNO:=OUTQUEUE(Q);WRITE(TABNO,'=');READLN(S);i:=1;WHILES[i]'('DOi:=i+1;ENDWHILE;WHILES[i]')'DOIF(S[i]='A')AND(S[i]='Z')THENS[i]:=CHR(ORD(S[i])+ORD('A')-ORD('a'));IF(S[i]='A')AND(S[i]='Z')THENINC(T[TABNO].LENGTH);T[TABNO].ELEMENT[T[TABNO].LENGTH]:=S[i];INQUEUE(Q,S[i]);ENDIF;ELSEIF(S[i]='0')ANDN(S[i]='9')THENINC(T[TABNO].LENGTH);T[TABNO].ELEMENT[T[TABNO].LENGTH]:=S[i]ENDIF;INC(i)7ENDIF;ENDWHILE;ENDWHILE;WRITE('ThemaxnumberintableLis:',maxnumber('L'));WRITE('Totalis:',total('L'))END.//主程序结束//3设有一个实数，以字符串形式存放于数组x中，用x：array[1..N]ofchar表示。其中x[1]若为'-'，表示负数；若为'+'、'.'或''，则表示正数。若为数字，也认为是正数。例如x=('','2','0','','3','.','5','%')则表示203.5x=('-','1','.','','2','0','%')则表示-1.2约定：在字符串x中，除x[1]外，其后可以包含有若干个'.'与''，但仅以第一次出现的为准，空格不起任何作用，并以字符'%'作为结束标志。程序要求：将输入的字符串还原成实数输出（小数点后无用的0应除去），还原的结果以下列形式存放（不需要输出）。F：数符。正数放0，负数放1。A：array[1..N]ofinteger;存放数字，不放小数点。K：表示A中有效数字的个数。J：表示小数点后的位数。例如：数203.24，还原后结果的存放是：F=0A=(2,0,3,2,4)K=5J=2又如：数-33.0740，还原后结果的存放是：F=1A=(3,3,0,7,4)K=5J=3[算法提要]：x:array[1..10]ofchar;可放长度定为10；首先读入字符串，然后处理数的符号，在还原的过程中，需要判定整数部分与小数部分，同时去除多余的空格和小数点，并约定输入是正确的，不用作出错检查。程序：FORI:=1TO10DOA[I]:=0;ENDFOR;FORI:=1TO10DOREAD(X[I]);ENDFOR;J:=0;F:=0;K:=0;B:=0;IFX[1]='-'THENBEGIN____________①________________________②____________ENDELSEIFX[1]:=