2000年NOIP提高组初赛真题

一、选择一个正确答案代码（A/B/C/D），填入每题的括号内（每题1.5分，多选无分，共30分）

1. 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. 数据信号与地址信号

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:=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. 上列程序段的正确揄出是（　　）

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分）

21. 已知，按中序遍历二叉树的结果为：abc 问：有多少种不同形态的二叉树可以得到这一遍历结果，并画出这些二叉树。 _________

22. 设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1，1+2，2+1，3。 _________

三、阅读程序，并写出正确的运行结果（每题10分，共20分）

23.

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
输出：____①_____

24.

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.
输出：____①_____

四、完善程序（共38分）

25. 问题描述：(3+3+4+4+4=18分) 将2^n个0和2^n个1，排成一个圈。从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。要求给出一种排法，用上面的方法产生出来的2^(n+1)个二进制数都不相同。 例如，当n=2时，即2^2个0和2^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+1to 27 do  ____②_____  ;
for i:=0 to 31 do b[1]:=o;
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.

26. 求出一棵树的深度和宽度。例如有如下的一棵树：( 4+4+4+4+4=20分) 其树的深度为从根结点开始到叶结点结束的最大深度，树的宽度为同一层上结点数的最大值。在上图中树的深度为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 程序清单


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]:=o;
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.

查看参考答案