第六届全国青少年信息学（计算机）奥林匹克分区联赛初赛试题
（提高组BASIC语言 二小时完成）
●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●
一． 选择一个正确答案代码（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.请仔读下列程序段：
PASCAL语言
Var
A:array[1..3,1..4]of integer;
B:array[1..4,1..3]of integer;
X,y:integer;
Begin
For x:=1to3do
For y:=1to4do
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
BASIC语言
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
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分）
10 N=7：M=6
20 DIM G（N，M）
30 FOR I=0 TO N
40 FOR J=0 TO M
50 G（I，J）=0
60 NEXT J：NEXT I
70 INPUT X1，Y1，X2，Y2
80 G（X1，Y1）=1：G（X2，Y2）=1
112 XP=X1：YP=Y1：XQ=X2：YQ=Y2
120 GOSUB 1000
130 DMIN=DISP
140 P=1
142 IF P=0 THEN500
144 P=0
150 FOR I=4 TO N
160 FOR J=0 TO M
170 IF G（I，J）>0 THEN 204
180 XP=I:YP=J:XQ=X2:YQ=Y2
190 GOSUB 1000
200 IF DISP>=DMIN THEN 204
202 DMIN=DISP:X0=I:Y0=J:P=1
204 NEXT J:NEXT I
206 IF P=0 THEN 260
220 X1=X0:Y1=Y0:G(X0,Y0)=1:
260 Q=0
300 FOR I=0 TO 3
310 FOR J=0 TO M
320 IF G(I,J)>0 THEN 380
330 XP=X1:YP=Y1:XQ=I:YQ=J
340 GOSUB 1000
350 IF DISP<=DMIN THEN 380
360 DMIN=DISP:X0=I:Y0=J:P=1:Q=1
380 NEXT J:NEXT I
390 IF Q=0 THEN 440
420 X2=X0:Y2=Y0:G(X2,Y2)=1
440 GOTO 142
500 PRINT X1,Y1,X2,Y2:END
1000 DISP=(XP-XQ)*(XP-XQ)+(YP-YQ)*(YP-YQ)
1010 RETURN
输入 7，6，0，0 输出
2．
10 DIM B(10)
20 INPUT L,N
25 IF N<=L THEN 200
30 S=L:K=1:T=L
40 IF S>=NTHEN 70
50 K=K+1:T=T*L:S=S+T
60 GOTO 40
70S=S-T:N=N-S-1
80 FOR I=1 TO 10:B(I)=0:NEXT I
90 J=11
100 IF N<=0 THEN 130
110 J=J-1:B(J)=N MOD L:N=INT(N/L)
120 GOTO 100
130 FOR I=10-K+1 TO 10
140 PRINT CHR$(65+B(I));
145 NEXT I
150 PRINT
160 GOTO 220
200 PRINT CHR$(65+N-1)
220 END
输入：4，167 输出：
四.完善程序（共38分）
1.问题描述：
将2n个和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统计二进制数是否已出现过。
程序清单
10 DIM A(36),B(31)
20 FOR I=1 TO 36:A(I)=0:NEXT I
30 FOR I=28 TO 32:A(I)=1:NEXT I
40 P=1:A(6)=1
50 IF P=0 THEN 230
60 J=27
70 IF ① THEN 100
80 J=J-1
90 GOTO 70
100 A(J)=1
110 FOR I=J+1 TO 27: ② :NEXT I
120 FOR I=0 TO31:B(I)=0: NEXT I
130 FOR I=1 TO 32
140 ③
150 FOR J=I TO I+4
160 S=S*2+A(J)
170 NEXT J
180 ④
190 NEXT I
200 S=0
210 FOR I=0 TO 31:S=S+B(I):NEXT I
220 IF ⑤ THEN 50
230 P=0
240 FOR I=1 TO 32
245 FOR J=I TO I+4
246 PRINT A(J);
248 NEXT J,I:END
2.问题描述
求出一棵树的深度和宽度。例如有如下的一棵树：
其树的深度为从根结点开始到叶结点结束的最大深度，树的宽度为同一层上结点数的最大值。在上图中树的深度为4，宽度为3。
用邻接表来表示树，上图中的树的邻接表示如下：
|
1 |
2 |
3 |
4 |
0 |
0 |
|
2 |
0 |
0 |
0 |
0 |
0 |
|
3 |
5 |
0 |
0 |
0 |
0 |
|
4 |
6 |
0 |
0 |
0 |
0 |
|
5 |
0 |
0 |
0 |
0 |
0 |
|
6 |
7 |
0 |
0 |
0 |
0 |
|
7 |
0 |
0 |
0 |
0 |
0 |
程序说明：
数组tree表示树树（假设树的度为4）
数组q表示队列，其中SP1-取出指针，SP2-存入指针，q[i,0]表示层数
数组d，统计同一层上的结点数（假设≤20层）
程序清单
10 DIM TREE(20,6),Q(100,6),D(20)
20 FOR I=1 TO14
30 TREE(I,1)=I
40 FOR J=1 TO 5
42 READ TREE(I,J+1)
44 NEXT J
50 NEXT I
55 TREE(15,1)=0
60 SP1=1:SP2=1
70 FOR I=1 TO 6:Q(1,I)=TREE(1,I):NEXT I
80 Q(1,0)=1
90 IF ① THEN 210
100 L= ② :J=2
120 IF ③ THEN 190
130 SP2=SP2+1:Q(SP2,0)=L:Q(SP2,1)=Q(SP1,J)
140 FOR I=2 TO 6
150 Q(SP2,I)=TREE(Q(SP1,J),I)
160 NEXT I
170 J=J+1
180 GO TO 120
190 SP1=SP1+1
200 GOTO 90
210 PRINT ④
220 FOR I=0 TO 20:D(I)=0:NEXT I
230 FOR I=1 TO SP2
240 D(Q(I,0))= ⑤
250 NEXT I
260 MAX=D(I)
270 FOR I=2 TO 20
280 IF D(I)<=MAX THEN 300
290 MAX=D(I)
300 NEXT I
310 PRINT MAX
320 END
1000 DATA 2,3,4,0,0,5,6,0,0,0,7,8,0,0,0,9,10,11,0,0,0,0,0,0,0,0,0,0,0,0
1010 DATA 12,13,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
1020 DATA 14,0,0,0,0,0,0,0,0,0,0,0,0,0,0 |
网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！） 
