NOIP2000普及组初赛试题答案(共10页).doc

精选优质文档-倾情为你奉上第六届全国青少年信息学（计算机）奥林匹克分区联赛试题（ 普及组 PASCAL语言 二小时完成 ） 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 一、选择一个正确答案代码（A/B/C/D），填入每题的括号内 (每题1.5分，多选无分，共30分）1下列无符号数中，最小的数是（ ）A（）2 B（75）10 C（37）8 D（2A）162在外部设备中，绘图仪属于（ ） A输入设备 B输出设备 C辅（外）存储器 D主（内）存储器3GB2312-80 规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（ ）为序排列的A以笔划多少 B以部首 C以ASCII码 D以机内码4算法是指（ ）A为解决问题而编制的计算机程序 B为解决问题而采取的方法与步骤C为解决问题而需要采用的计算机语言 D为解决问题而采用的计算方法5RAM 中的信息是（ ）A生产厂家预先写入的 B计算机工作时随机写入的C防止计算机病毒侵入所使用的 D专门用于计算机开机时自检用的6计算机主机是由CPU 与（ ）构成的 A控制器 B运算器 C输入、输出设备 D内存储器7计算机病毒的特点是（ ） A传播性、潜伏性、易读性与隐蔽性 B破坏性、传播性、潜伏性与安全性 C传播性、潜伏性、破坏性与隐蔽性 D传播性、潜伏性、破坏性与易读性8设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为（ ） Ar- f Br- f +1 C（r- f ） MOD n+1 D（r- f + n） MOD n9在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（ ） A 堆排序 B 希尔排序 C 冒泡排序 D 快速排序10Internet 的规范译名应为（ ） A英特尔网 B因特网 C 万维网 D以太网11WINDOWS 9X 是一种（ ）操作系统 A单任务字符方式 B单任务图形方式 C多任务字符方式 D多任务图形方式12某种计算机的内存容量是640K, 这里的640K 容量是指( ) 个字节A640 B 640*1000 C 640 * 1024 D640*1024*1024 13在Windows 9X中，菜单项后带有符号“”，表示该菜单项( ) A可以进行开关选择 B执行时有对话框C有若干子命令 D不能执行14某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索(binary search)，在最坏的情況下，需检视( )个单元 A1000 B. 10 C. 100 D. 500 15已知数组A中，每个元素AI，J在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A5，8的起始地址为（ ） ASA+141 BSA+180 CSA+222 DSA+22516大家知道，不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（ ）A快存 / 辅存 / 主存 B外存 / 主存 / 辅存C快存 / 主存 / 辅存 D主存 / 辅存 / 外存17线性表若采用链表存贮结构，要求内存中可用存贮单元地址（ ）A必须连续 B部分地址必须连续C一定不连续 D连续不连续均可18下列叙述中，正确的是（ ）A 线性表的线性存贮结构优于链表存贮结构 B 队列的操作方式是先进后出C 栈的操作方式是先进先出 D二维数组是指它的每个数据元素为一个线性表的线性表19电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一类则是两端的小鸟不相同已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（ ） A奇数 B偶数 C可奇可偶 D数目固定20请仔細閱读下列程序段: PASCAL语言 BASIC语言var a:array1.3,1.4 of integer; b:array1.4,1.3 of integer; x,y:integer; begin for x:=1 to 3 do for y:=1 to 4 doax,y:=x-y;for x:=4 downto 1 do for y:=1 to 3 dobx,y:=ay,x;writeln(b3,2); end.DIM A(3,4), B(4,3)FOR X=1 TO 3FOR Y=1 TO 4A(X,Y)=X-YNEXT Y , XFOR X=4 TO 1 STEP -1FOR Y=1 TO 3B(X,Y)=A(Y,X)NEXT Y, XPRINT B(3,2)END 上列程序段的正确輸出是（ ） A-1 B-2 C-3 D-4 二、问题解答（每题7分，共14分） 1已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 2有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。 此时用一个1×2的骨牌铺满方格，共有3种铺法： 试对给出的任意一个n（n>0），求出铺法总数的递推公式。三、阅读程序，并写出程序正确的运行结果（10+16分，共26分）1PROGRAM NOI_002; VAR I, J, L, N, K, S, T : INTEGER; B : ARRAY1.10 OF 0.9; BEGIN READLN(L,N); S:=L; K:=1; T:=L; WHILE S<N DO BEGIN K:=K+1; T:=T*L; S:=S+T END; S:=S-T; N:=N-S-1; FOR I:=1 TO 10 DO BI:=0; J:=11; WHILE N>0 DO BEGIN J:=J-1; BJ:=N MOD L; N:=N DIV L END; FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD('A')+BI); END. 输入：4 167 输出：2PROGRAM NOI_004; VAR I, J, J1, J2, P, Q : INTEGER; P1 : BOOLEAN; B,C : ARRAY1.100 OF INTEGER; BEGIN READLN(Q,P); J:=1; P1:=TRUE; BJ:=Q; J1:=0; WHILE (Q>0) AND P1 DO BEGIN J1:=J1+1; CJ1:=Q*10 DIV P; Q:=Q*10-CJ1*P; IF Q>0 THEN BEGIN J2:=1; WHILE (BJ2<>Q) AND (J2<=J) DO J2:=J2+1; IF BJ2=Q THEN BEGIN P1:=FALSE; WRITE('0.'); FOR I:=1 TO J2-1 DO WRITE(CI:1); WRITE(''); FOR I:=J2 TO J1 DO WRITE(CI:1); WRITELN('') END ELSE BEGIN J:=J+1; BJ:=Q END END END; IF Q=0 THEN BEGIN WRITE('0.'); FOR I:=1 TO J1 DO WRITE(CI:1); WRITELN END; READLN END.输入1 8输出 输入 2 7输出四、完善程序（每题15分，共30分）1. 将2n个0和2n 个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。 要求给出一种排法，用上面的方法产生出来的2个二进制数都不相同。 A 00 10 11 1 0 例如，当n=2时, 即个0 和个1 排成如下一圈：比如，从A位置开始，逆时针方向取三个数000，然后再从B位置上开始取三个数001，接着从C开始取三个数010，可以得到000，001，010，101，011，111，110，100共8个二进制数且都不相同。程序说明 以n=4为例，即有16个0，16个1， 数组a用以记录32个0，1的排法， 数组b统计二进制数是否已出现过。程序清单 PROGRAM NOI00;VAR A : ARRAY1.36 OF 0.1; B :ARRAY0.31 OF INTEGER; I, J, K, S, P : INTEGER; BEGIN FOR I:=1 TO 36 DO AI:=0; FOR I:=28 TO 32 DO AI:=1; P:=1; A6:=1; WHILE (P=1) DO BEGIN J:=27; WHILE AJ=1 DO J:=J-1; FOR I:=J+1 TO 27 DO FOR I:=0 TO 31 DO BI:=0; FOR I:=1 TO 32 DO BEGIN FOR K:=I TO I+4 DO S:=S*2+AK; END; S:=0; FOR I:=0 TO 31 DO S:=S+BI; IF THEN P:=0 END; FOR I:=1 TO 32 DO FOR J：=I TO I+4 DO WRITE(AJ); WRITELN END.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) 系数 指数 2 2 1 1 -1 1 1 0 1 0 0 0 0 0 PXQ的结果存入C中。其输出格式是：依次用一对括号内的（系数，指数）分别来表示。如上例的输出结果表示为：（2，3）（1，2）（1，0）程序清单PROGRAM NOI_007; VAR I, J, K, L , JP, JQ, JC, X, Y, X1, Y1 : INTEGER; P, Q : ARRAY1.10,1.2 OF INTEGER; C : ARRAY1.20,1.2 OF INTEGER; BEGIN JP:=0; READLN(X,Y); WHILE X<>0 DO BEGIN JP:=JP+1; PJP,1:=X; PJP,2:=Y; READLN(X,Y) END; JQ:=0;READLN(X,Y); WHILE X<>0 DO BEGIN JQ:=JQ+1; QJQ,1:=X; QJQ,2:=Y; READLN(X,Y) END; JC:=1; CJC,1:=0; CJC,2:=-1000; FOR I:=1 TO JP DO BEGIN Y:=PI,2; FOR J:=1 TO JQ DO BEGIN Y1:=Y+QJ,2; K:=1; WHILE Y1<CK,2 DO K:=K+1; IF Y1=CK,2 THEN ELSE BEGIN FOR L:=JC DOWNTO K DO BEGIN CL+1,1:=CL,1; CL+1,2:=CL,2 END; CK,1:=X1; CK,2:=Y1; END END END; FOR I:=1 TO JC DO IF THEN WRITE(（，CI,1,，CI,2,'）'); READLN END. 赛区 市 学校 姓名 = 密 封 线 =第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题普及组答卷纸 阅 卷 记 录 总阅卷人 总 得 分 第 一 大 题得 分第二大题得分题号 1 2 345678910第三大题得分得分(1)(2)题号11121314151617181920第四大题得分得分(1)(2)= 以下由考生填写 = 答卷部分一、 选择一个正确答案代码（A/B/C/D），填入每题的括号内 (每题1.5分，多选无分，共30分）题号 1 2 4 5 6 7 8 9 10选择 题号 11 12 13 14 15 16 17 18 19 20选择二、问题解答（共14分） 1. 答：有 种不同形态的二叉树可以得到这一遍历结果; （2分） 可画出的这些二叉树为: （5分） 2. 对给出的任意一个n（n>0），用F（N）表示其铺法的总数的递推公式为: （7分） 赛区 市 学校 姓名 = 密 封 线 =三、阅读程序，并写出程序的正确运行结果（10+16分，共26分） （1） 程序的运行结果是: （2） 程序的运行结果是:四、根据题意，将程序补充完整(每个点3分，共30分) PASCAL语言 BASIC语言 题一 70 110 140 180 220 题二 190 240 280 300 350第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题普及组参考答案一、选择一个正确答案代码（A/B/C/D），填入每题的括号内 (每题1.5分，多选无分，共30分）题号 1 2 4 5 6 7 8 9 10选择 C B B B B D C D D B题号 11 12 13 14 15 16 17 18 19 20选择 D C B B A C D D B A二、问题解答（第1题的第1问2分，第2问5分，第2题7分，两题共14分） 1答：有 5 种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为: a b a c c / / / b a c c a b / / c b b a 2对给出的任意一个n（n>0），用F（n）表示其铺法的总数的递推公式为: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（n3）三、阅读程序，并写出程序的正确运行结果（10+16分，共26分）(1) 程序的运行结果是: BBAC(2) 程序的运行结果是: 0.125 0.四、根据题意，将程序补充完整(每个点3分，共30分) PASCAL 语言 BASIC语言 题一 AJ:=1; 70 A(J) = 0 AI:=0; 110 A(I) = 0 S:=0; 140 S = 0 BS:=1; 180 B(S) = 1 S=32 220 S < 32题二 X:=PI,1; 190 X * Q(J, 1) X1:=X*QJ,1; 240 Y1 = C(K, 2) CK,1:=CK,1+X1 280 GOTO 320 JC:=JC+1 300 C(K, 1) + X1 CI,1<>0 350 C(I, 1) = 0专心-专注-专业