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

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

《全国青少年信息学计算机奥林匹克竞赛提高组初赛试题及答案.docx》由会员分享，可在线阅读，更多相关《全国青少年信息学计算机奥林匹克竞赛提高组初赛试题及答案.docx（16页珍藏版）》请在冰点文库上搜索。

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

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

（提高组PASCAL语言二小时完成）

●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

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

1．下列无符号数中，最小的数是（）。

A．（11011001）2B．（75）10C．（37）8D．（2A）16

2．在外部设备中，绘图仪属于（）。

A．输入设备B．输出设备C．辅（外）存储器D．主（内）存储器

3．计算机主机是由CPU与（）构成的。

A．控制器B。

输入、输出设备C．运算器D．内存储器

4．计算机病毒的特点是（）。

A．传播性、潜伏性、易读性与隐蔽性B．破坏性、传播性、潜伏性与安全性

C．传播性、潜伏性、破坏性与隐蔽性D．传播性、潜伏性、破坏性与易读性

5．WINDOWS9X是一种（）操作系统。

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．640B．640*1000C．640*1024D．640*1024*1024

11．下面哪些计算机网络不是按覆盖地域划分的（）。

A．局域网B．都市网C．广域网D．星型网

12．在有N个叶子节点的哈夫曼树中，其节点总数为（）

A．不确定B．2N-1C．2N+1D．2N

13．已知数组A中，每个元素A[I，J]在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。

试问：

A[5，8]的起始地址为（）。

A．SA+141B．SA+180C．SA+222D．SA+225

14．不同类型的存储器组成了多层次结构的存储器体系，按存取速度从快到慢的排列是（）。

A．快存/辅存/主存B．外存/主存/辅存

C．快存/主存/辅存D．主存/辅存/外存

15．某数列有1000个各不相同的单元，由低至高按序排列；現要对该数列進行二分法检索（binarysearch），在最坏的情況下，需检视（）个单元。

A．1000B．10C．100D．500

16．请仔細閱读下列程序段:

var

a:

array[1..3,1..4]ofinteger;

b:

array[1..4,1..3]ofinteger;

x,y:

integer;

begin

forx:

=1to3do

fory:

=1to4do

a[x,y]:

=x-y;

forx:

=4downto1do

fory:

=1to3do

b[x,y]:

=a[y,x];

writeln（b[3,2]）;

end.

DIMA（3,4）,B（4,3）

FORX=1TO3

FORY=1TO4

A（X,Y）=X-Y

NEXTY,X

FORX=4TO1STEP-1

FORY=1TO3

B（X,Y）=A（Y,X）

NEXTY,X

PRINTB（3,2）

END

PASCAL语言BASIC语言

上列程序段的正确輸出是（）。

A．-1　　　　B．-2　　　C．-3D．-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分）

programnoi_003;

constn=7;m=6;

vari,j,x0,y0,x1,y1,x2,y2:

integer;

d:

real;p:

boolean;g:

array[0..n,0..m]of0..1;

functiondisp（x1,y1,x2,y2:

integer）:

real;

begindisp:

=sqrt（（x1-x2）*（x1-x2）+（y1-y2）*（y1-y2））;end;

begin

fori:

=0tondoforj:

=0tomdog[i,j]:

=0;

readln（x1,y1,x2,y2）;g[x1,y1]:

=1;g[x2,y2]:

=1;p:

=true;

whilepdo

begin

p:

=false;d:

=disp（x1,y1,x2,y2）;x0:

=x1;y0:

=y1;

fori:

=4tondoforj:

=0tomdo

if（d>disp（i,j,x2,y2））and（g[i,j]=0）then

begind:

=disp（i,j,x2,y2）;x0:

=i;y0:

=j;end;

if（x0<>x1）or（y0<>y1）then

beginx1:

=x0;y1:

=y0;p:

=true;g[x1,y1]:

=1;end;

d:

=disp（x1,y1,x2,y2）;x0:

=x2;y0:

=y2;

fori:

=0to3doforj:

=0tomdo

if（d

begind:

=disp（x1,y1,i,j）;x0:

=i;y0:

=jend;

if（x0<>x2）or（y0<>y2）then

beginx2:

=x0;y2:

=y0;p:

=true;g[x2,y2]:

=1;end;

end;WRITELN（X1，Y1，X2，Y2）

end.输入：

7600

输出：

2.

programnoi_002;

vari,j,l,n,k,s,t:

integer;b:

array[1..10]of0..9;

begin

readln（l,n）;s:

=l;k:

=1;t:

=l;

ifn>lthenbegin

whiles

begink:

=k+1;t:

=t*l;s:

=s+tend;

s:

=s-t;n:

=n-s-1;

fori:

=1to10dob[i]:

=0;

j:

=11;

whilen>0do

beginj:

=j-1;b[j]:

=nmodl;n:

=ndivlend;

fori:

=10-k+1to10dowrite（chr（ord（'A'）+b[i]））;

readln;

end

elsewriteln（chr（ord（'A'）+n-1））

end.输入：

4167输出：

四、完善程序（共38分）

1．问题描述

　　将2n个0和2n个1，排成一圈。

从任一个位置开始，每次按逆时针的方向以长度为n+1的单位进行数二进制数。

要求给出一种排法，用上面的方法产生出来的2ｎ＋１个二进制数都不相同。

　A

　0

　Ｂ　０　　　　　　１　Ｈ

Ｃ　０　　　　　　　　１Ｇ

　Ｄ　１　　　　　　１　Ｆ

　0

　　　　　　Ｅ

例如，当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统计二进制数是否已出现过。

程序清单

Programnoi00;

var

a:

array[1..36]of0..1;

b:

array[0..31]ofinteger;

i,j,k,s,p:

integer;

Begin

fori:

=1to36doa[i]:

=0;

fori:

=28to32doa[i]:

=1;

p:

=1;a[6]:

=1;

while（p=1）do

begin

j:

=27;

whilea[j]=1doj:

=j-1;

①

fori:

=j+1to27do②

fori:

=0to31dob[i]:

=0;

fori:

=1to32do

begin

③

fork:

=itoi+4dos:

=s*2+a[k];

④

end;

s:

=0;

fori:

=0to31dos:

=s+b[i];

if⑤thenp:

=0

end;

fori:

=1to32doFORJ：

=ITOI+4DOwrite（a[J]）;

writeln

End.

2．问题描述

求出一棵树的深度和宽度。

例如有如下的一棵树：

①

/∣\

②③④

//

⑤⑥

\

⑦

其树的深度为从根结点开始到叶结点结束的最大深度,树的宽度为同一层上结点数的最大值。

在上图中树的深度为4，宽度为3。

用邻接表来表示树，上图中的树的邻接表见表1.

程序说明：

数组tree表示树,用邻接表来表示（假设树的度为4）

数组q表示队列，其中SP1——取出指针，SP2——存入指针，q[i,0]表示层数

数组d，统计同一层上的结点数（假设≤20层）

表1

１

２

３

４

０

０

２

０

０

０

０

０

３

５

０

０

０

０

４

６

０

０

０

０

５

０

０

０

０

０

６

７

０

０

０

０

７

０

０

０

０

０

程序清单

programnoi00_6;

vari,j,sp1,sp2,l,max:

integer;tree:

array[1..20,1..6]ofinteger;

q:

array[1..100,0..6]ofinteger;d:

array[0..20]ofinteger;

begin

fori:

=1to14doforj:

=1to6dotree[i,j]:

=0;

forj:

=1to14dotree[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;

fori:

=1to6doq[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];

fori:

=2to6do

q[sp2,i]:

=tree[q[sp1,j],i];

j:

=j+1

end;

sp1:

=sp1+1

end;

writeln④;

fori:

=0to20dod[i]:

=0;

fori:

=1tosp2do

d[q[i,0]]:

=⑤;

max:

=d[1];

fori:

=2to20do

ifd[i]>maxthenmax:

=d[i];

writeln（max）;

readln;

end.

赛区市学校姓名

==========================密封线=======================

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

提高组答卷纸

阅卷记录

总阅卷人总得分

第一大题

得分

第二大题得分

题号

1

2

3

4

5

6

7

8

9

10

第三大题得分

得分

（1）

（2）

题号

11

12

13

14

15

16

17

18

19

20

第四大题得分

得分

（1）

（2）

==============================以下由考生填写===============================

答卷部分

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

题号

1

2

３

4

5

6

7

8

9

10

选择

题号

11

12

13

14

15

16

17

18

19

20

选择

二、问题解答（12分）

1．答：

有种不同形态的二叉树可以得到这一遍历结果;　　　　　　　　（1分）

可画出的这些二叉树为:

　　　　　　　　　　　　　　　　　　　　　　　（5分）

2．用递推公式给出某人从底层开始走完全部楼梯的走法为（用F（N）记录不同方案数）

:

（6分）

赛区市学校姓名

=============================密封线============================

三、阅读程序，并写出程序的正确运行结果：

（每题10分，共20分）

（1）程序的运行结果是:

（2）程序的运行结果是:

四、根据题意,将程序补充完整（共38分）

PASCAL语言BASIC语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

题一（3+3+4+4+4=18分）

①　　　　　　　　　　　　　　　　70

②　　　　　　　　　　　　　　　　　　　　110　　　　　　　　　　　　　　　　　　　　

③　　　　　　　　　　　　　　　　　　　　140　　　　　　　　　　　　　　　　　

④　　　　　　　　　　　　　　　　　　　　180　　　　　　　　　　　　　　　　　

⑤　　　　　　　　　　　　　　　　　　　　220　　　　　　　　　　　　　　　　　

题二（4+4+4+4+4=20分）

①　　　　　　　　　　　　　　　　90

②　　　　　　　　　　　　　　　　　　　　100　　　　　　　　　　　　　　　　

③　　　　　　　　　　　　　　　　　　　　120　　　　　　　　　　　　　　　　　

④　　　　　　　　　　　　　　　　　　　　210　　　　　　　　　　　　　　　　　

⑤　　　　　　　　　　　　　　　　　　240　　　　　　　　　　　　　　　　　

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

提高组参考答案

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

题号

1

2

３

4

5

6

7

8

9

10

选择

C

B

D

C

D

B

Ｄ

　Ｂ

　Ａ

C

题号

11

12

13

14

15

16

17

18

19

20

选择

D

B

A

C

B

A

D

D

B

Ｂ

二、问题解答（12分）

1．答：

有5种不同形态的二叉树可以得到这一遍历结果;可画出的这些二叉树为:

①a②b③a④c⑤c

\/\\//

baccab

\/\/

cbba

2．用递推公式给出的某人从底层开始走完全部楼梯的走法为

（用F（N）记录不同方案数）：

　F

（1）＝1　　F

（2）＝2　F（3）＝4　

　　　　F（N）＝F（N－3）＋F（N－2）＋F（N－1）　　（N≥4）

三、阅读程序，并写出程序的正确运行结果：

（每题10分，共20分）

（１）程序的运行结果是:

4302

（２）程序的运行结果是:

BBAC

四、根据题意，将程序补充完整（共38分）

PASCAL语言BASIC语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

题一（3+3+4+4+4=18分）

①A[j]:

=1;70A（j）=0

②A[i]:

=0;　　　　110　A（I）=0

③S:

=0;　　　　140S=0

④B[s]:

=1;　　　　180　B（s）=1

⑤S=32　　　220　S<32

题二（4+4+4+4+4=20分）

①Sp1<=sp290sp1>sp2

②Q[sp1,0]+1　　100Q（SP1，0）+1；

③Q[sp1,j]<>0　120　q（sp1,j）=0

④（q[sp2,0]）;　　　　210　q（sp2,0）

⑤D[q[i,0]]+1;　　　240　d（q（i,0））+1