NOIP1999提高组初赛试题答案

1第五届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题（提高组）（PASCAL语言竞赛用时：2小时）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）。1、微机内的存储器的地址是以()编址的。A.二进制位B.字长C.字节D.微处理器的型号2、下列诸因素中,对微机工作影响最小的是()A.尘土B.噪声C.温度D.湿度3、在24*24点阵的字库中，汉字“一”与“编”的字模占用字节数分别是（）A.32、32B.32、72C.72、72D.72、324、将DOS系统盘插入A驱动器启动机器，随后使用一批应用软件，在此过程中，DOS系统盘（）A.必须始终插入在A驱动器中B.不必再用C.可能有时要插入A驱动器中D.可能有时要插入B驱动器中5、以下DOS命令中，有可能在磁盘上建立子目录的是（）A.TYPEB.DIRC.XCOPYD.CD6、在CONFIG.SYS文件中，装入特定可安装设备驱动程序的命令是（）ABUFFERBFILESCDRIVERDDEVICE7、计算机能直接执行的指令包括两部分,它们是（）A.源操作数与目标操作数B.操作码与操作数C.ASCⅡ码与汉字代码D.数字与字符8、在微机中，通用寄存器的位数是（）A.8位B.16位C.计算机字长D.32位9、在计算机,字符编码通常采用()A.原码B.反码C.ASCII码D.补码10、计算机的软件系统通常分为（）A.系统软件与应用软件B.高级软件与一般软件C.军用软件与民用软件D.管理软件与控制软件11、执行DOS命令：C:\ATTRIBA:*.*的功能是（）A.查看A盘上所有文件属性B.查看A盘上当前目录中所有文件属性C.查看A盘上所有系统文件属性D.删去A盘上所有隐含文件的属性212、执行下列DOS命令，效果等价的是（）组A.COPY*.FOR与COPY*.FORCONB.COPYA:*.*B:与XCOPYA:*.*B:C.COPYFILE1.TXT+FILE2.TXT与COPYFILE2.TXT+FILE1.TXTD.XCOPYA:*.*B:/S与DISKCOPYA:B:13、已知小写字母“M”的十六进制的ASCⅡ码值是6D，则小写字母“C”的十六进制数的ASCⅡ码值是（）A.98B.62C.99D.6314、计算机中的数有浮点与定点数两种，其中用浮点数表示的数，通常由（）这两部分组成。A.指数与基数B.尾数与小数C.阶码与尾数D.整数与小数15、下列文件名中，属于DOS中的保留设备名的为（）A.AUXB.COMC.CON1D.PRN116、启动计算机引导DOS是将操作系统()A.从磁盘调入中央处理器B.从内存储器调入高速缓冲存储器C.从软盘调入硬盘D.从系统盘调入内存储器17、十进制算术表达式：3*512+7*64+4*8+5的运算结果，用二进制表示为（）A.10111100101B.11111100101C.11110100101D.1111110110118、组成“教授”（JIAOSHOU）,“副教授”（FUJIAOSHOU）与“讲师”(JIANGSHI)这三个词的汉字，在GB2312-80字符集中都是一级汉字，对这三个词排序的结果是（）A.教授、副教授、讲师B.副教授、教授、讲师C.讲师、副教授、教授D.副教授、讲师、教授19、不同的计算机，其指令系统也不相同，这主要取决于（）A.所用的操作系统B.系统的总体结构C.所用的CPUD.所用的程序设计语言20、对具有隐含属性（H）的当前目录下的文件AB.TXT，能成功执行的DOS命令是（）A.TYPEAB.TXTB.COPYAB.TXTXY.TXTC.DIRAB.TXTD.RENAB.TXTXY.TXT二、回答问题（10分）将Ln定义为求在一个平面中用n条直线所能确定的最大区域数目。例如：当n=1时，L1=2,进一步考虑，用n条折成角的直线（角度任意），放在平面上，能确定的最大区域数目Zn是多少？例如：当n=1时，Z1=2（如下图所示）当给出n后，请写出以下的表达式：1Ln=______________2Zn=_______________3三、阅读程序，并写出正确的程序运行结果（每题1.5分，共30分）1.programexp1;vari,j,k:integer;a:array[0..100]ofinteger;BeginforI:0to100doa[i]:=ifork:=5downto2dobeginfori:=1to100doif(imodk)=0thena[I]:=0;fori:=1to99doforj:=1to100-idoifa[j]a[j+1]thenbegina[j]:=a[j]+a[j+1];a[j+1:=a[j]-a[j+1];a[j]:=a[j]-a[j+1];end;end;j:=1;while(a[j]=0)and(j100)doj:=j+1;fori:=jto100doa[0]=a[0]+a[i];writeln(a[0]);End.本题的运行结果是:2、设数组A[1]，A[2]，…，A[N]，已存入了数据，调用不同的排序程序，则数据比较的次数将会不同，试计算分别调用下列不同的排序过程的比较运算的次数。其中SWAP（I，J）表示A[I]与A[J]进行交换。（1）PROCEDURESORT1（N：INTEGER）；VARI，J：INTEGER；BEGINFORI：=1TON-1DOFORJ：=1TONDOIFA[J]A[I]THENSWAP(I,J)END;调用该过程的语句为SORT1（N），比较运算的次数为：__________(2)PROCEDURESORT2（I，N：INTEGER）；VARJ：INTEGER；BEGINIFI=NTHENWRITE（A[N]）ELSEFORJ：=I+1TONDOBEGINIFA[J]A[I]THENSWAP（I，J）WRITE（A[I]）；SORT2（I+1，N）ENDEND.4调用该过程的语句为SORT2（1，N），比较运算的次数为：__________（3）PROCEDURESORT3（I，J：INTEGER）；VARM：INTEGER；BEGINIFI〈〉JTHENBEGINM：=（I+J）DIV2；SORT3（I，M）；SORT3（M+1，J）；MERGE；{假设合并的元素分别为P、Ｇ个，需要比较P+Ｇ次}END；END；调用该过程的语句为SORT3（1，N），比较运算的次数为：__________四、根据题意，将以下程序填写完善（共30分）1、[问题描述]求一棵树的深度与宽度。[算法说明]树可用数组tree:array[1..n,1..5]ofinteger;其中：tree[I,1]表示结点号；tree[I,2]——tree[I,5]所属结点如上图可表示为：1234025670380004910005000060000711120080000900001000001100001213000130000在求解的过程中，用到数组G:ARRAY[1..N,1..7]OFINTEGER；其中：G[I,1]表示父结点，G[I,2]表示层次，G[I,3]表示本结点号，G[I,4]——G[I,7]表示子女结点；同时，设2个指针SP1（取数指针），SP2（存数指针）（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（13）5[程序清单]：programexＧp3;constn=13;vari,j,k,sp1,sp2,n1,n2,jmax,p:integer;tree:array[1..n,1..5]ofinteger;g:array[1..n,1..7]ofinteger;beginfori:=1tondobegintree[i,1]:=i;forj:=2to5doread(tree[i,j]);readln;end;sp1:=1;sp2:=1;g[1,1]:=0;g[1,2]:=1;g[1,3]:=1;fori:=4to7dog[1,i]:=tree[1,i-2];while__________①_________dobeginp:=g[sp1,2];n2:=g[sp1,3];_________②________;j:=4;while_________③_________dobeginn1:=g[sp1,j];j:=j+1;__________④_________;g[sp2,1]:=n2;g[sp2,2]:=p;g[sp2,3]:=n1;fori:=1to4dog[sp2,i+3]:=tree[n1,i+1];end;__________⑤_________;end;writeln('maxd=',g[sp2,2]);j:=1;k:=g[1,2];jmax:=0;fori:=2tosp2doif__________⑥__________thenj:=j+1elsebeginifjjmaxthenjmax:=j;__________⑦________;k:=g[Ｉ,2];end;ifjjmaxthenjmax:=j;writeln('max1=',jmax);end.2、[问题描述]用生成法求出1，2，…，r的全排列(r=8)（15分）[算法过程]用数组：a:array[1..r]ofinteger;表示排列；初始化时，a[I]:=1(I=1,2,….f)设中间的某一个排列为a[1],a[2],…a[r]则求出下一个排列的算法为：(1)从后面向前找，直到找到一个顺序为止（设下标为j-1,则a[j-1]a[j](2)从a[j]-a[r]中，找出一个a[k]比a[j-1]大的最小元素6(3)将a[j-1]与a[Ｋ]交换(4)将a[j]，a[j+1]……a[r]由小到大排序。[程序清单]programexＧp4;constr=7;varn,i,s,k,j,i1,t:intger;a:array[1..r]ofinteger;procedureprint1;varik:integer;beginforik:=1tordowrite(a[ik]:8);writeln;endbeginfori:=1tordo__________①__________;print1;s:=1;fori:=2tordos:=s*i;s:=s-1;fori:=__________②__________dobeginj:=r;while__________③_________doj:=j-1;k:=j;fori1:=j+1tordoif__________④_________thenk:=i1;t:=a[j-1];a[j-1]:=a[k];a[k]:=t;fori1:=jtor-1dofork:=i1+1tordoif__________⑤___________thenbegint:=a[i1];a[i1]:=a[k];a[k]:=t;end;print1;end;end.第五届全国青少年信息学（计算机）奥林匹克分区联赛初赛（提高组）参考答案一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）7题号12345678910选择CBCCCDBCCA题号11121314151617181920选择BBDCADBDCA二、回答问题：（5＋5＝10分）当给n后，写出的表达式为：Ln=n(n+1)/2+1(n≥0)Zn=L2n-2n=2n2-n+1三、阅读程序，并写出正确的程序运行结果（每题15分，共30分）1．程序运行的结果：9702．（PASCAL语言作5+5+5=15分）（1）调用该过程的语句为SORT1（N）；比较运算的次数为：n(n-1)（2）调用该过程的语句为SORT2（N）；比较运算的次数为：n(n-1)/2（3）调用该过程的语句为SORT3（N）；比较运算的次数为：nlog2n+c（BAS