NOIP2000普及组初赛试题答案

1第六届全国青少年信息学（计算机）奥林匹克分区联赛试题（普及组PASCAL语言二小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、选择一个正确答案代码（A/B/C/D），填入每题的括号内(每题1.5分，多选无分，共30分）1．下列无符号数中，最小的数是（）．A．（11011001）2B．（75）10C．（37）8D．（2A）162．在外部设备中，绘图仪属于（）．A．输入设备B．输出设备C．辅（外）存储器D．主（内）存储器3．GB2312-80规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（）为序排列的．A．以笔划多少B．以部首C．以ASCII码D．以机内码4．算法是指（）．A．为解决问题而编制的计算机程序B．为解决问题而采取的方法与步骤C．为解决问题而需要采用的计算机语言D．为解决问题而采用的计算方法5．RAM中的信息是（）．A．生产厂家预先写入的B．计算机工作时随机写入的C．防止计算机病毒侵入所使用的D．专门用于计算机开机时自检用的6．计算机主机是由CPU与（）构成的．A．控制器B．运算器C．输入、输出设备D．内存储器7．计算机病毒的特点是（）．A．传播性、潜伏性、易读性与隐蔽性B．破坏性、传播性、潜伏性与安全性C．传播性、潜伏性、破坏性与隐蔽性D．传播性、潜伏性、破坏性与易读性8．设循环队列中数组的下标范围是1–n，其头尾指针分别为f和r，则其元素个数为（）．A．r-fB．r-f+1C．（r-f）MODn+1D．（r-f+n）MODn9．在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（）．A堆排序B希尔排序C冒泡排序D快速排序10．Internet的规范译名应为（）．A．英特尔网B．因特网C．万维网D．以太网211．WINDOWS9X是一种（）操作系统．A．单任务字符方式B．单任务图形方式C．多任务字符方式D．多任务图形方式12．某种计算机的内存容量是640K,这里的640K容量是指()个字节．A．640B．640*1000C．640*1024D．640*1024*102413．在Windows9X中，菜单项后带有符号“…”，表示该菜单项()．A．可以进行开关选择B．执行时有对话框C．有若干子命令D．不能执行14．某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binarysearch)，在最坏的情況下，需检视()个单元．A．1000B.10C.100D.50015．已知数组A中，每个元素A[I，J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A[5，8]的起始地址为（）．A．SA+141B．SA+180C．SA+222D．SA+22516．大家知道，不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（）．A．快存/辅存/主存B．外存/主存/辅存C．快存/主存/辅存D．主存/辅存/外存17．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）．A．必须连续B．部分地址必须连续C．一定不连续D．连续不连续均可18．下列叙述中，正确的是（）．A．线性表的线性存贮结构优于链表存贮结构B．队列的操作方式是先进后出C．栈的操作方式是先进先出D．二维数组是指它的每个数据元素为一个线性表的线性表19．电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一类则是两端的小鸟不相同．已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）．A．奇数B．偶数C．可奇可偶D．数目固定320．请仔細閱读下列程序段:PASCAL语言BASIC语言上列程序段的正确輸出是（）．A．-1B．-2C．-3D．-4二、问题解答（每题7分，共14分）1．已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2．有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。此时用一个1×2的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n0），求出铺法总数的递推公式。三、阅读程序，并写出程序正确的运行结果（10+16分，共26分）1．PROGRAMNOI_002;VARI,J,L,N,K,S,T:INTEGER;B:ARRAY[1..10]OF0..9;BEGINREADLN(L,N);S:=L;K:=1;T:=L;WHILESNDOBEGINK:=K+1;T:=T*L;S:=S+TEND;S:=S-T;N:=N-S-1;FORI:=1TO10DOB[I]:=0;J:=11;WHILEN0DOBEGINJ:=J-1;B[J]:=NMODL;N:=NDIVLEND;FORI:=10-K+1TO10DOWRITE(CHR(ORD('A')+B[I]));END.vara:array[1..3,1..4]ofinteger;b:array[1..4,1..3]ofinteger;x,y:integer;beginforx:=1to3dofory:=1to4doa[x,y]:=x-y;forx:=4downto1dofory:=1to3dob[x,y]:=a[y,x];writeln(b[3,2]);end.DIMA(3,4),B(4,3)FORX=1TO3FORY=1TO4A(X,Y)=X-YNEXTY,XFORX=4TO1STEP-1FORY=1TO3B(X,Y)=A(Y,X)NEXTY,XPRINTB(3,2)END4输入：4167输出：2．PROGRAMNOI_004;VARI,J,J1,J2,P,Q:INTEGER;P1:BOOLEAN;B,C:ARRAY[1..100]OFINTEGER;BEGINREADLN(Q,P);J:=1;P1:=TRUE;B[J]:=Q;J1:=0;WHILE(Q0)ANDP1DOBEGINJ1:=J1+1;C[J1]:=Q*10DIVP;Q:=Q*10-C[J1]*P;IFQ0THENBEGINJ2:=1;WHILE(B[J2]Q)AND(J2=J)DOJ2:=J2+1;IFB[J2]=QTHENBEGINP1:=FALSE;WRITE('0.');FORI:=1TOJ2-1DOWRITE(C[I]:1);WRITE('{');FORI:=J2TOJ1DOWRITE(C[I]:1);WRITELN('}')ENDELSEBEGINJ:=J+1;B[J]:=QENDENDEND;IFQ=0THENBEGINWRITE('0.');FORI:=1TOJ1DOWRITE(C[I]:1);WRITELNEND;READLNEND.输入①18输出输入②27输出四、完善程序（每题15分，共30分）1.将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2ｎ＋１个二进制数都不相同。例如，当n=2时,即２２个0和２２个1排成如下一圈：比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，．．．可以得到000，001，010，101，011，111，110，100A0Ｂ01ＨＣ01ＧＤ11Ｆ0Ｅ5共8个二进制数且都不相同。程序说明以n=4为例，即有16个0，16个1，数组a用以记录32个0，1的排法，数组b统计二进制数是否已出现过。程序清单PROGRAMNOI00;VARA:ARRAY[1..36]OF0..1;B:ARRAY[0..31]OFINTEGER;I,J,K,S,P:INTEGER;BEGINFORI:=1TO36DOA[I]:=0;FORI:=28TO32DOA[I]:=1;P:=1;A[6]:=1;WHILE(P=1)DOBEGINJ:=27;WHILEA[J]=1DOJ:=J-1;①FORI:=J+1TO27DO②FORI:=0TO31DOB[I]:=0;FORI:=1TO32DOBEGIN③FORK:=ITOI+4DOS:=S*2+A[K];④END;S:=0;FORI:=0TO31DOS:=S+B[I];IF⑤THENP:=0END;FORI:=1TO32DOFORJ：=ITOI+4DOWRITE(A[J]);WRITELNEND.2．多项式的乘法。例如有如下多项式：P(X)=2X2-X+1,Q(X)=X+1则：P(X)·Q(X)=(2X2-X+1)(X+1)=2X3+X2+1程序说明：多项式的表示：系数、指数如上例中：P(X)：系数指数Q(X)系数指数2211-11101000006PXQ的结果存入C中。其输出格式是：依次用一对括号内的（系数，指数）分别来表示。如上例的输出结果表示为：（2，3）（1，2）（1，0）程序清单PROGRAMNOI_007;VARI,J,K,L,JP,JQ,JC,X,Y,X1,Y1:INTEGER;P,Q:ARRAY[1..10,1..2]OFINTEGER;C:ARRAY[1..20,1..2]OFINTEGER;BEGINJP:=0;READLN(X,Y);WHILEX0DOBEGINJP:=JP+1;P[JP,1]:=X;P[JP,2]:=Y;READLN(X,Y)END;JQ:=0;READLN(X,Y);WHILEX0DOBEGINJQ:=JQ+1;Q[JQ,1]:=X;Q[JQ,2]:=Y;READLN(X,Y)END;JC:=1;C[JC,1]:=0;C[JC,2]:=-1000;FORI:=1TOJPDOBEGIN①Y:=P[I,2];FORJ:=1TOJQDOBEGIN②Y1:=Y+Q[J,2];K:=1;WHILEY1C[K,2]DOK:=K+1;IFY1=C[K,2]THEN③ELSEBEGINFORL:=JCDOWNTOKDOBEGINC[L+1,1]:=C[L,1];C[L+1,2]:=C[L,2]END;C[K,1]:=X1;C[K,2]:=Y1;④ENDENDEND;FORI:=1TOJCDOIF⑤THENWRITE(‘（’，C[I,1],‘，’，C[I,2],'）');READLNEND.7赛区市学校姓名==========================密封线=======================第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题普及组答卷纸阅卷记录总阅卷人总得分第一大题得分第二大题得分题号12345678910第三大题得分得分(1)(2)题号11121314151617181920第四大题得分得分(1)(2)=============================以下由考生填写=============================答卷部分一、选择一个正确答案代码（A/B/C/D），填入每题的括号内(每题1.5分，多选无分，共30分）题号12３45678910选择题号11121314151617181920选择二、问题解答（共14分）1.答：有种不同形态的二叉树可以得到这一遍历结果;（2分）可画出的这些二叉树为:（5分）2.对给出的任意一个n（n0），用F（N）表示其铺法的总数的递推公式为:（7分）8赛区市学校姓名==========================密封线=======================三、阅读程序，并写出程序的正确运行结果（10+16分，共26分）（1）程序的运行结果是:（2）程序的运行结果是:四、根据题意，将程序补充完整(每个点3分，共30分)PASCAL语言BASIC语言＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝题一①70②110③140④180⑤220题二①190②240③280④300⑤350第六届全国青少年信息学（计算机）奥