第六届全国青少年信息学（计算机）奥林匹克分区联赛试题（提高组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．计算机主机是由CPU与（）构成的。A．控制器B。输入、输出设备C．运算器D．内存储器4．计算机病毒的特点是（）。A．传播性、潜伏性、易读性与隐蔽性B．破坏性、传播性、潜伏性与安全性C．传播性、潜伏性、破坏性与隐蔽性D．传播性、潜伏性、破坏性与易读性5．WINDOWS 9X是一种（）操作系统。A．单任务字符方式B．单任务图形方式C．多任务字符方式D．多任务图形方式6．Internet的规范译名应为（）。A．英特尔网B．因特网C．万维网D．以太网7．计算机网络是一个（）系统。A．管理信息系统B．管理数据系统C．编译系统D．在协议控制下的多机互连系统8．计算机系统总线上传送的信号有（）。A．地址信号与控制信号B．数据信号、控制信号与地址信号C．控制信号与数据信号D．数据信号与地址信号9．计算机的运算速度取决于给定的时间内，它的处理器所能处理的数据量。处理器一次能处理的数据量叫字长。已知64位的奔腾处理器一次能处理64个信息位，相当于（）字节。A．8个B．1个C．16个D．2个10．某种计算机的内存容量是640K，这里的640K容量是指（）个字节。A．640 B．640*1000 C．640*1024 D．640*1024*1024 11．下面哪些计算机网络不是按覆盖地域划分的（）。A．局域网B．都市网C．广域网D．星型网12．在有N个叶子节点的哈夫曼树中，其节点总数为（）A．不确定B．2N-1 C．2N+1 D．2N 13．已知数组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 14．不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（）。A．快存/辅存/主存B．外存/主存/辅存C．快存/主存/辅存D．主存/辅存/外存15．某数列有1000个各不相同的单元，由低至高按序排列；現要对该数列進行二分法检索（binary search），在最坏的情況下，需检视（）个单元。A．1000 B．10 C．100 D．500 16．请仔細閱读下列程序段: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 PASCAL语言BASIC语言上列程序段的正确輸出是（）。A．-1 B．-2 C．-3 D．-4 17．线性表若采用链表存贮结构，要求内存中可用存贮单元地址（）。A．必须连续B．部分地址必须连续C．一定不连续D．连续不连续均可18．下列叙述中，正确的是（）。A．线性表的线性存贮结构优于链表存贮结构B．队列的操作方式是先进后出C．栈的操作方式是先进先出D．二维数组是指它的每个数据元素为一个线性表的线性表19．电线上停着两种鸟（A，B），可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类：一类是两端的小鸟相同；另一类则是两端的小鸟不相同。已知：电线两个顶点上正好停着相同的小鸟，试问两端为不同小鸟的线段数目一定是（）。A．奇数B．偶数C．可奇可偶D．数目固定20.一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角則以（80，25）表示，屏幕上每一个字符佔用兩字节（byte），整个屏幕則以线性方式存儲在电脑的存儲器內，由屏幕左上角开始，位移为0，然后逐列逐列存儲。求位于屏幕（X，Y）的第一个字节的位移是（）。A．(Y*80+X)*2-1 B．((Y-1)*80+X-1)*2 C．(Y*80+X-1)*2 D．((Y-1)*80+X)*2-1二、问题求解（6＋6＝12分）1．已知，按中序遍历二叉树的结果为：abc问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。2．设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。三、阅读程序，并写出正确的运行结果（每题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:ARRAY[0..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;BEGIN FOR I:=0 TO N DO FOR J:=0 TO M DO G[I,J]:=0;READLN(X1,Y1,X2,Y2);G[X1,Y1]:=1;G[X2,Y2]:=1;P:=TRUE;WHILE P DO BEGIN P:=FALSE;D:=DISP(X1,Y1,X2,Y2);X0:=X1;Y0:=Y1;FOR I:=4 TO N DO FOR J:=0 TO M DO IF(D>DISP(I,J,X2,Y2))AND(G[I,J]=0)THEN BEGIN D:=DISP(I,J,X2,Y2);X0:=I;Y0:=J;END;IF(X0<>X1)OR(Y0<>Y1)THEN BEGIN X1:=X0;Y1:=Y0;P:=TRUE;G[X1,Y1]:=1;END;D:=DISP(X1,Y1,X2,Y2);X0:=X2;Y0:=Y2;FOR I:=0 TO 3 DO FOR J:=0 TO M DO IF(D<DISP(X1,Y1,I,J))AND(G[I,J]=0)THEN BEGIN D:=DISP(X1,Y1,I,J);X0:=I;Y0:=J END;IF(X0<>X2)OR(Y0<>Y2)THEN BEGIN X2:=X0;Y2:=Y0;P:=TRUE;G[X2,Y2]:=1;END;END;WRITELN（X1，Y1，X2，Y2）END.
输入：7 6 0 0输出：2.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;IF N>L THEN BEGIN 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 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]));READLN;END ELSE WRITELN(CHR(ORD(’A’)+N-1))END.
输入：4 167输出：四、完善程序（共38分）１．问题描述将2n个0和2n个1，排成一圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2ｎ＋１个二进制数都不相同。例如，当n=2时,即2２个0和2２个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．问题描述求出一棵树的深度和宽度。例如有如下的一棵树：①/∣\②③④//⑤⑥\⑦其树的深度为从根结点开始到叶结点结束的最大深度,树的宽度为同一层上结点数的最大值。在上图中树的深度为4，宽度为3。用邻接表来表示树，上图中的树的邻接表见表1.程序说明：数组tree表示树,用邻接表来表示(假设树的度为4)数组q表示队列，其中SP1——取出指针，SP2——存入指针，q[i,0]表示层数数组d，统计同一层上的结点数(假设≤20层)表1１２３４００２０００００３５００００４６００００５０００００６７００００７０００００程序清单PROGRAM NOI00_6;VAR I,J,SP1,SP2,L,MAX:INTEGER;TREE:ARRAY[1..20,1..6]OF INTEGER;Q:ARRAY[1..100,0..6]OF INTEGER;D:ARRAY[0..20]OF INTEGER;BEGIN FOR I:=1 TO 14 DO FOR J:=1 TO 6 DO TREE[I,J]:=0;FOR J:=1 TO 14 DO TREE[J,1]:=J;TREE[1,2]:=2;TREE[1,3]:=3;TREE[1,4]:=4;TREE[2,2]:=5;TREE[2,3]:=6;TREE[3,2]:=7;TREE[3,3]:=8;TREE[4,2]:=9;TREE[4,3]:=10;TREE[4,4]:=11;TREE[7,2]:=12;TREE[7,3]:=13;TREE[13,2]:=14;SP1:=1;SP2:=1;FOR I:=1 TO 6 DO Q[1,I]:=TREE[1,I];Q[1,0]:=1;WHILE①DO BEGIN L:=②;J:=2;WHILE③DO BEGIN SP2:=SP2+1;Q[SP2,0]:=L;Q[SP2,1]:=Q[SP1,J];FOR I:=2 TO 6 DO Q[SP2,I]:=TREE[Q[SP1,J],I];J:=J+1 END;SP1:=SP1+1 END;WRITELN④;FOR I:=0 TO 20 DO D[I]:=0;FOR I:=1 TO SP2 DO D[Q[I,0]]:=⑤;MAX:=D[1];FOR I:=2 TO 20 DO IF D[I]>MAX THEN MAX:=D[I];WRITELN(MAX);READLN;end.第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题(提高组参考答案)一、选择一个正确答案代码(A/B/C/D),填入每题的括号内(每题1.5分，多选无分，共30分)题号12345678910选择CBDCDBDBAC题号11121314151617181920选择DBACBADDBB二、问题解答(第1题的第1问2分，第2问5分，第2题7分，两题共14分)1.答：有5种不同形态的二叉树可以得到这一遍历结果；可画出的这些二叉树为：2.用递推公式给出的某人从底层开始走完全部楼梯的走法为(用F(N))记录不同案数：F(1)=1F(2)=2F(3)=4F(N)=F(N-3)+F(N-2)+F(N-1)(N≥4)三、阅读程序，并写出程序的正确运行结果：(10分，共20分)(1)程序的运行结果是：4302(2)程序的运行结果是：BBAC四、根据题意，将程序补充完整(每个点3分，共30分)PASCAL语言题一①A[J]：=1；②A[I]：=0；③S：=0；④B[S]：=1；⑤S=32题二①SP1<=SP2②Q[SP1,0]+1③Q[SP1,J]<>0④(Q[SP2,0])；⑤D[Q[I,0]]+1；
