全国青少年信息学奥林匹克竞赛提高组初赛试题及答案

1、第六届全国青少年信息学计算机奥林匹克分区联赛试题 提高组 PASCAL 语言 二小时完成 ? ?全部试题答案均要求写在答卷纸上， 写在试卷纸上 一律无效 ?每题 1.5 分，多项选择无分，共 30 分、选择一个正确答案代码 A/B/C/D ，填入每题的括号内C 378 D 2A161以下无符号数中，最小的数是A 11011001 2 B 75104 ?计算机病毒的特点是。A . 传播性、潜伏性、易读性与隐蔽性B . 破坏性、传播性、潜伏性与平安性D . 传播性、潜伏性、破坏性与易读性C. 传播性、潜伏性、破坏性与隐蔽性5. WINDOWS 9X 是一种 操作系统。A . 单任务字符方式C. 多

2、任务字符方式6. Internet 的标准译名应为 B . 单任务图形方式D .多任务图形方式C. 万维网D . 以太网A. 因特网英特尔网 B .7.计算机网络是一个系统。A . 管理信息系统C. 编译系统8. 计算机系统总线上传送的信号有 A . 地址信号与控制信号C.控制信号与数据信号B. 管理数据系统D .在协议控制下的多机互连系统。B. 数据信号、控制信号与地址信号D .数据信号与地址信号2在外部设备中，绘图仪属于。A ?输入设备B ?输出设备C. 辅外存储器D ?主内存储器3. 计算机主机是由CPU 与构成的。A .控制器B。输入、输出设备C. 运算器D. 内存储器9. 计算机的运

3、算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理 数据量叫字长。 64 位的奔腾处理器一次能处理 64 个信息位，相当于 字节A. 8 个B. 1 个C. 16 个D. 2 个B . 640*1000A. 64010.640K ,这里的 640K 容量是指C. 640 * 1024D . 640*1024*1024某种计算机的内存容量是 个字节。11. 下面哪些计算机网络不是按覆盖地域划分的A . 局域网B . 都市网C. 广域网D. 星型网12?在有N个叶子节点的哈夫曼树中，其节点总数为A .不确定B ? 2N-1C. 2N+1D ? 2N13?数组A中，每个元素Al

4、, J在存贮时要占3个字节，设I从1变化到8, J从1变化到10, 分配内存时是从地址 SA开始连续按行存贮分配的。试问：A5 , 8的起始地址为。A. SA+141B. SA+180C. SA+222D. SA+225A .快存/辅存/主存C. 快存/主存/辅存15. 某数列有1000个各不相同的单元search,在最坏的情況下，需检视个单元。A. 1000b 1016. 请仔細閱读以下程序段：PASCAL语言vara:array1.3,1.4 of in teger;B .外存/主存/辅存D .主存/辅存/外存由低至高按序排列；現要对该数列進行二分法检索bi naryC. 100D . 5

5、00BASIC语言DIMA(3,4),B(4 ,3FORX=1TO ) 3FORY=1TO 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)END14?不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是A. -1B. -2上列程序段的正确輸出是C. -3)。D . -417. 线性表假设米用链表存贮结构，要求内存中可用存贮单兀地址A.必须连续B.局部地址必须连续C. 一定不连续D.连续不连续均可18. 以下表达中，正确的选项是 。A. 线性表的线

6、性存贮结构优于链表存贮结构B. 队列的操作方式是先进后出C. 栈的操作方式是先进先出P:=TRUE;D. 二维数组是指它的每个数据元素为一个线性表的线性表19?电线上停着两种鸟 A , B, 可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可 分为两 类：一类是两端的小鸟相同；另一类那么是两端的小鸟不相同。：电线两个顶点上 正好停着相 同的小鸟，试问两端为不同小鸟的线段数目一定是 。A ?奇数B. 偶数 C. 可奇可偶D ?数目固定20. 一个文本屏幕有 25 列及 80 行，屏幕的左上角以 1， 1表示，而右下角則以 80 ， 25表 示， 屏幕上每一个字符佔用兩字节 byte , 整个

7、屏幕則以线性方式存儲在电脑的存儲器內，由屏幕左上角开始，位移为 0，然后逐列逐列存儲。求位于屏幕 X， 丫的第一个字节的位移是。A ? Y * 80 + X * 2 - 1B. Y - 1 * 80 + X - 1 * 2C. Y * 80 + X - 1 * 2DY - 1 * 80 + X * 2 - 1二、问题求解 6+ 6= 12 分 1，按中序遍历二叉树的结果为： 二叉树可以得到这一遍历结果，并画出这些二叉树。abc 问：有多少种不同形态的2.设有一个共有n级的楼梯，某人每步可走 1级，也可走2级，也可走3级，用递推公式给出某 人从 底层开始走完全部楼梯的走法。例如：当n=3 时，共

8、有 4 种走法，即 1+1+1,1+2,2+13三、阅读程序，并写出正确的运行结果 ( 每题 10 分，共 20 分 )PROGRAM NOI_003;CONST N=7; M=6;VAR I,J,X0,Y0,X1,Y1,X2,Y2:INTEGER;D:REAL; P:BOOLEAN;G:ARRAY0.N,0.M OF 0.1;FUNCTION DISP(X1,Y1,X2,Y2:INTEGER):REAL;BEGIN DISP:=SQRT(X1-X2)*(X1-X2)+(Y1-Y2)*(Y1-Y2); END;FOR I:=0 TO N DO BEGIN FOR J:=0 TO M DO GI

9、,J:=0;READLN(X1,Y1,X2,Y2); GX1,Y1:=1; GX2,Y2:=1; WHILE P DOBEGINP:=FALSE;FOR I:=4 TO N DOD:=DISP(X1,Y1,X2,Y2);FOR J:=0 TO M DOX0:=X1; Y0:=Y1;IF (D>DISP(I,J,X2,Y2) AND (GI,J=0) THEN BEGIN D:=DISP(I,J,X2,Y2); X0:=I; Y0:=J; END;IF (X0<>X1) OR (Y0<>Y1) THENBEGIN X1:=X0; Y1:=Y0; P:=TRUE;GX

10、1,Y1:=1; END;D:=DISP(X1,Y1,X2,Y2); X0:=X2; Y0:=Y2;FOR I:=0 TO 3 DOFOR J:=0 TO M DOIF (D<DISP(X1,Y1,I,J) AND (GI,J=0) THENBEGIN D:=DISP(X1,Y1,I,J);XO:=I;YO:=J END;IF (X0<>X2) OR (Y0<>Y2) THENBEGIN X2:=X0; Y2:=Y0; P:=TRUE; GX2,Y2:=1;END;END; WRITELN (X1 , Y1 , X2, Y2)END.输入：7600输出:2.PRO

11、GRAM NOI_002;VAR l,J,L,N,K,S,T:INTEGER;B:ARRA Y1.1O OF 0.9;BEGINREADLN(L,N); S:=L;K:=1;T:=L;IF N>L THEN BEGINWHILE S<N DOBEGIN 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 DOBEGIN J:=J-1;BJ:=N MOD L;N:=N DIV L END;FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD('

12、;A')+BI); READLN;ENDELSE WRITELN(CHR(ORD('A')+N-1)END.输入:4167输出：四、完善程序(共38分)1.问题描述将2n个0和2n个1,排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2n + 1个二进制数都不相同。例如，当n=2时，即2?个 0和2彳个1排成如下一圈：ABC 0D0H1 GFE001，接比方，从A位置开始，逆时针方向取三个数000,然后再从B位置上开始取三个数着从C开始取三个数 010,，可以得到 000, 001 , 010,

13、101 , 011 , 111, 110, 100共8个二进 制数 且都不相同程序说明以n=4为例，即有16个0, 16个1,数组a用以记录32个0, 1的排法， 数组b统计二进制数是 否已出现过。程序清单PROGRAM NOI00;VARAB:ARRA Y1.36 OF 0.1;:ARRA Y 0.31 OFINTEGER;I, J, K, S, P : INTEGER;BEGINFOR I:=1 TO 36 DO Al:=0;FOR l:=28 TO 32 DO AI:=1;P:=1; A6:=1;WHILE (P=1) DOBEGINJ:=27;WHILE AJ=1 DO J:=J-1;

14、FOR I:=J+1 TO 27 DO FOR I:=0 TO 31 DO Bl:=0;FOR I:=1 TO 32 DOBEGINFOR K:=I TO 1+4 DO S:=S*2+AK;END;S:=0;FOR I:=0 TO 31 DO S:=S+BI;IF THEN P:=0END;FOR I:=1 TO 32 DO FOR 上=I TO I+4 DO WRITE(AJ);WRITELNEND.2 ?问题描述求出一棵树的深度和宽度。例如有如下的一棵树：/ I / /其树的深度为从根结点开始到叶结点结束的最大深度，树的宽度为同一层上结点数的最大值。在上图中树的深度为4,宽度为3。用邻接表

15、来表示树，上图中的树的邻接表见表1.程序说明:数组tree表示树,用邻接表来表示 (假设树的度为4)数组q表示队列，其中SP1取出指针，SP2存入指针，qi,O表示层数 数组d，统计同一层上的结点数(假设w 20层)表1123400200000350000460000500000670000700000程序清单PROGRAM NOIOO_6;VARI,J,SP1,SP2 丄，MAX:INTEGER;TREE:ARRA Y1.20,1.6 OF INTEGER;Q:ARRA Y1.100,0.6 OF INTEGER; D:ARRA YO.2O OF INTEGER;BEGINFOR I:=1

16、TO 14 DOFOR J:=1 TO 6 DOTREEI,J:=0;FOR J:=1 TO 14 DO TREEJ,1:=J;TREE1,2:=2;TREE1,3:=3;TREE1,4:=4;TREE2,2:=5;TREE2,3:=6;TREE3,2:=7;TREE3,3:=8;TREE4,2:=9;TREE4,3:=10;TREE4,4:=11;TREE7,2:=12;TREE7,3:=13;TREE13,2:=14;SP1:=1;SP2:=1;FOR I:=1 TO 6 DO Q1,I:=TREE1,I;Q1,0:=1;WHILE DOBEGINL:=;J:=2;WHILE DOBEGI

17、NSP2:=SP2+1;QSP2,0:=L;QSP2,1:=QSP1,J;FOR I:=2 TO 6 DOQSP2,I:=TREEQSP1,J,I;J:=J+1END;SP1:=SP1+1END;WRITELN ；FOR I:=0 TO 20 DO DI:=0;FOR I:=1 TO SP2 DODQI,0:=；MAX:=D1;FOR I:=2 TO 20 DOIF DI>MAX THEN MAX:=DI;WRITELN(MAX);READLN;END.=密 封 线=第六届全国青少年信息学计算机奥林匹克分区联赛初赛试题提咼组答卷纸阅卷记录:总阅卷人总得分第一大题得分第二大题得分题号123

18、45678910第三大题得分:得分(1) (2)题号111213 114151617181920 第四大题得分得分(1) (2)以下由考生填写=答卷局部、选择一个正确答案代码A/B/C/D,填入每题的括号内每题 1.5分，多项选择无分，共30 分题号12345678910选择题号1112 |1314151617181920选择、问题解答 12分(1分)(5分)1 ?答：有种不同形态的二叉树可以得到这一遍历结果可画出的这些二叉树为：2?用递推公式给出某人从底层开始走完全部楼梯的走法为用F N记录不同方案数6分赛区市学校姓名密封线三、 阅读程序，并写出程序的正确运行结果：每题10分，共20分1程序的运行结果是：2程序的运行结果是：四、根据题意，将程序补充完整共38分PASCAL语言BASIC语言题一(3+3+4