第六届全国青少年信息学（计算机）奥林匹克分区联赛试题

第六届全国青少年信息学（计算机）奥林匹克分区联赛试题
（普及组PASCAL语言　二小时完成）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）
1.下列无符号数中，最小的数是（　　）
A.（11011001）2 B.（75）10 C.（37）8 D.（2A）16
2.在外部设备中，绘图仪属于（　　）
A.输入设备 B.输出设备 C.辅（外）存储器 D.主（内）存储器
3.GB2312-80规定了一级汉字3755个，二级汉字3008个，其中二级汉字字库中的汉字是以（　　）为序排列的。
A.以笔划多少 B.以部首 C.以ASCⅡ码 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-f B.r-f+1 C.(r-f)　MOD　n+1 D.(r-f+n)　MOD　n
9.在待排序的数据表已经为有序时，下列排序算法中花费时间反而多的是（　　）
A.堆排序 B.因特网 C.冒泡排序 D.快速排序
10.Internet的规范译名应为（　　）
A.英特尔网B.因特网C.万维网D.以太网
11.WINDOWS9x是一种（　　）操作系统
A.单任务字符方式 B.单任务图形方式
C.多任务字符方式 D.多任务图形方式
12.某种计算机的内存容量是640K，这里的640K容量是指（　　）个字节
A.640 B.640*1000 C.640*1024 D.640*1024*1024
13.在Windows9x中，菜单项后带有符号“…”，表示该菜单项（　　）
A.可以进行开关选择 B.执行时有对话框 C.有若干子命令 D.不能执行
14.某数列有1000个各不相同的单元，由低至高按序排列；现要对该数列进行二分法检索（binary search），在最坏的情况下，需检视（　　）个单元
A.1000 B.10 C.100 D.500
15.已知数组A中，每个元素A[I,J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A[5,8]的起始地址为（　　）
A.SA+141 B.SA+180 C.SA+222 D.SA+225
16.不同类型的存储器组成了多层次结构的存储器体系,按存取速度从快到慢的排列是（　　　）
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:array[1..3,1..4]of
integer;
　　　 b:array[1..4,1..3]of
integer;
　　　 x,y:integer;
　　 　begin
　　　 　　for x:=1 to 3 do
　　　　　　for y:=1 to 4 do
　　　　　　 　a[x,y]:=x-y;
　　　 　　 for x:=4 downto 1 do
　　　　　　　for y:=1 to 3 do
　　　　　　 　b[x,y]:=a[y,x];
　　　 　　 writeln(b[3,2]);
　　 　end. DIM A(3,4),B(4,3)
FOR X=1 TO 3
FOR Y=1 TO 4
A(X,Y)=X-Y
NEXT Y,X
FOR X=4 TO 1 STEP-1
FOR Y=1 TO 3
B(X,Y)=A(Y,X)
NEXT Y,X
PRINT 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分）
　1.PROGRAM NOI__002;
　　　　VAR I,J,L,N,K,S,T: INTEGER;
　　　　　　B　　　　　　: ARRAY[1..10] OF 0..9;
　　　BEGIN
　　　　 READLN(L,N);S:=L;　　K:=1;　　T:=L;
　　　　 WHILE S　　　　 BEGIN K:=K+1;　　T:=T*L;　　 S:=S+T　　END;
　　　　 S:=S-T; N:=N-S-1;
　　　　 FOR I:=1 TO 10 DO　　B[I]:=0;
　　　　 J:=11;
　　　　 WHILE N>0 DO
　　　　　BEGIN　　J:=J-1;　　B[J]:=N MOD L;　　N:=N DIV L　　END;
　　　　 FOR I:=10-K+1 TO 10 DO WRITE(CHR(ORD('A')+B[I]));
　　　END
　　输入：4　　167
输出：
2.PROGRAM NOI__004;
　　　　VAR　I,J,J1,J2,P,Q: INTEGER;
　　　　　　 P1　　　　　 : BOOLEAN;
　　　　　　 B,C　　　　　: ARRAY[1..100] OF INTEGER;
　　　　BEGIN
　　　　　 READLN(Q,P);　　J:=1;　　P1:=TRUE;　　B[J]:=Q;　　J1:=0;
　　　　　 WHILE　（Q>0） AND P1 DO
　　　　　　BEGIN
　　　　　　　J1:=J1+1;　C[J1]:=Q*10　DIV P;　Q:=Q*10-C[J1]*P;
　　　　　　　IF Q>Q THEN BEGIN
　　　　　　　　　　　　　 J2:=1;
　　　　　　　　　　　　　 WHILE (B[J2]<>Q) AND (J2<=J) DO　　J2:=J2+1;
　　　　　　　　　　　　　　IF B[J2]=Q THEN
　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　P1:=FALSE;　　WRITE('0.');
　　　　　　　　　　　　　　　　FOR I:=1 TO J2-1 DO　　WRITE(C[I]:1);
　　　　　　　　　　　　　　　　WRITE('{'};
　　　　　　　　　　　　　　　　FOR I:=J2 TO J1 DO　　WRITE(C[I]:1);
　　　　　　　　　　　　　　　　WRITELN(')')
　　　　　　　　　　　　　　　END
　　　　　　　　　　ELSE　　BEGIN　　J:=J+1;　　B[J]:=Q　　END
　　　　　　　END
　　　　　　END;
　　　　　 IF Q=0 THEN BEGIN
　　　　　　　　　　　　　WRITE('0.');
　　　　　　　　　　　　　FOR I:=1 TO J1 DO　　WRITE(C[I]:1);
　　　　　　　　　　　　　WRITELN
　　　　　　　　　　　　END;
　　　　　　READLN
　　　END.　　
　　　输入　　①1　　8　　输出
　　　输入　　②2　　7　　输出
四、完善程序（每题15分，共30分）
1.将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。
要求给出一种排法，用上面的方法产生出来的2n+1个二进制数都不相同。
　例如，当n=2时，即22个0和22个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　　　　:ARRAY[1..36] OF 0..1
　　　B　　　　:ARRAY[0..31] OF INTEGER;
　　　I,J,K,S,P:INTEGER;
　　　BEGIN
　　　　FOR I:=1 TO 36 DO　　A[I]:=0;
　　　　 FOR I:=28 TO 32 DO　　A[I]:=1;
　　　　P:=1;　　A[6]:=1;
　　　　WHILE (P=1) DO
　　　　　BEGIN
　　　　　　J:=27
　　　　　　WHILE A[J]=1 DO　　J:=J-1;
　　　　　　(　①　)
　　　　　　FOR I:=J+1 TO 27 DO (　②　)
　　　　　　FOR I:=0 TO 31 DO B[I]:=0;
　　　　　　FOR I:=1 TO 32 DO
　　　　　　 BEGIN
　　　　　　　(　③　)
　　　　　　　　FOR K:=I TO I+4 DO　　S:=S*2+A[k];
　　　　　　　　(　④　)
　　　　　　 END;
　　　　　　S:=0;
　　　　　　FOR I:=0 TO 31 DO　　S:=S+B[I];
　　　　　　IF (　⑤　) THEN P:=0
　　　　　END;
　 　　　FOR I:=1 TO 32 DO　　FOR J:=I TO I+4 DO　　WRITE(A[J]);
　　　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　　　　　:ARRAY[1..10,1..2] OF INTEGER;
　　　　　C　　　　　　:ARRAY[1..20,1..2] OF INTEGER;
　　　BEGIN
　　　　JP:=0;
　　　　READLN(X,Y) ;
　　　　WHILE X<>0 DO
　　　　 BEGIN　　JP:=JP+1;　P[JP,1]:=X;　P[JP,2]:=Y;　READLN(X,Y)　END;
　　　　JQ:=0;
　　　　READLN(X,Y);
　　　　WHILE X<>0 DO
　　　　 BEGIN　JQ:=JQ+1;　Q[JQ,1]:=X;　Q[JQ,2:]=Y;　READLN(X,Y)　END;
　　　　JC:=1　　C[JC,1]:=0;　　C[JC,2]:=-1000;
　　　　FOR I:=1 TO JP DO
　　　　　BEGIN
　　　　　　(　①　)
　　　　　　　Y:=P[I,2];
　　　　　　FOR J:=1 TO JQ DO
　　　　　　　BEGIN
　　　　　　　　(　②　)
　　　　　　　　Y1:=Y+Q[J,2];
　　　　　　　　K:=1;
　　　　　　　　WHILE Y1　　　　　　　　IF Y1=C[K,2] THEN (　③　)
　　　　　　　　　　　　　　 ELSE
　　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　　FOR L:=JC DOWNTO K DO
　　　　　　　　　　　　　　　　　　BEGIN
　　　　　　　　　　　　　　　　　　　C[L+1,1]:=C[L,1];
　　　　　　　　　　　　　　　　　　　C[L+1,2]:=C[L,2]
　　　　　　　　　　　　　　　　　　END;
　　　　　　　　　　　　　　　　　　C[K,1]:=X1; C[K,2]:=Y1;
　　　　　　　　　　　　　　　　　　(　④　)
　　　　　　　　　　　　　　　　END
　　　　　　　END
　　　　　END;
　　　　FOR I:=1 TO JC DO
　　　　　IF (　⑤　) THEN WRITE('(',C[I,1],',',C[I,2],')');
　　　　READLN
　　END.