青少年计算机竞赛初赛试题

衢州市第23届青少年信息学（计算机）竞赛初赛试题

一、单项选择题（共20题，每题2分，共计40分。每题仅有一个正确答案。）

1.OSI/RM（开放系统互联）参考模型的最低层是（）。

A.传输层B.网络层C.物理层D.应用层

2.128KB的存储器用十六进制表示，它的最大的地址码是（)

A.10000B.EFFFC.1FFFFD.FFFFF

3.冯・诺依曼计算机的思想是（兀

A.指令控制B.数据存储

C.程序控制D.存储程序和程序控制

4.设字符串S="Olympic"，S的非空子串数的数目是（)O

A.29B.28C.16D.17

5.与十进制28.5625相等的六进制数是（)O

A.44.3213B.44.3123C.34.3213D.34.3123

6.在计算机中，防火墙的作用是（

A.防止火灾蔓延B.防止网络攻击

C.防止计算机死机D.防止使用者误删数据

7.完全二叉树共有2*NT个结点,则它的叶结点数是（)

A.N-1B.NC.2*ND.2-1

8.关于图灵机下面的说法哪个是正确的：（)o

A.图灵机是世界上最早的计算机。

B.由于大量使用磁带操作，图灵机运行速度很慢。

C.图灵机只是一个理论上的计算模型。

D.图灵机是英国人图灵发明的，在二战中为破译德军的密码发挥了重要作用。

9.下列各数中最大的是（）。

A.11010110.0101（二进制）B.D6.53（十六进制）

C.214.32（十进制）D.326.25（八进制）

10.关于ASCII,下面哪个说法是正确的：（）

A.ASCH码就是键盘上所有键的唯一编码。

B.一个ASCII码使用一个字节的内存空间就能够存放。

C.最新扩展的ASCII编码方案包含了汉字和其他欧洲语言的编码。

D.ASCH码是英国人主持制定并推广使用的。

11.在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111

111111101101,其对应的十进制整数应该是：

A.19B.-19C.18D.-18

12.近20年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问

题的强有力的工具。在下列关于递归算法的说法中，正确的是（）o

A.在1977年前后形成标准的计算机高级语言“F0RTRAN77”禁止在程序使用

递归，原因之一是该方法可能会占用更多的内存空间

B.和非递归算法相比，解决同一个问题，递归算法一•般运行得更快一些

C.对于较复杂的问题，用递归方式编程一般比非递归方式更难一些

D.对于已经定义好的标准数学函数sin（x）,应用程序中的语句“y=sin（sin

（x））;"就是一种递归调用

13.递归过程或函数调用时，处理参数和返回地址，通常使用一种称为（）

的数据结构。

A.队列B.栈

C.多维数组D.链表

14.数值数据在计算机内表示时，其正负号用（）表示。

A.+B.-C.0或1D.01

15.一个高度为h的完全二叉树最小元素数目是（）。

A.2h+lB.2h-lC.2h-!D.2h-l

16.二叉树T的宽度优先遍历序列为ABCDEFGHI,已知A是C的父结点,

D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深

度设为0），可知F的父结点是（）。

A.BB.CC.DD.E

17.地面上有标号为A、B、C的3根细柱，在A柱上放有10个直径相同中间有

空的圆盘，从上到下一次编号为1,2,3,……，将A柱上的部分圆盘经过B柱

移入C柱，也可以在B柱上暂存。如果B柱上的操作记录为：进，出，进，出，

进，进，进，出，出，进，出，出。那么，在C柱上，从上往下的盘子的编号为：

（）

A.635421B.364521

C.634521D.365421

18.设A=B=C=true,D=false,以下逻辑运算表达式值为假的有（）。

AR-＞（（.4AS）VC）AD）

C.AA（BVCVD）ADD.

19.对给定的整数序列（54,73,21,35,67,78,63,24,89）进行从小到大的排序时,

采用选择排序的第一趟扫描的结果是（）。

A.（21,24,35,54,67,78,63,73,89）

B.（21,35,24,54,67,78,63,73,89）

C.（21,24,35,54,67,63,73,78,89）

D.（21,73,54,35,67,78,63,24,89）

20.将数组｛8,23,4,16,77,-5,53,100｝中的元素按从大到小的顺序排列,

每次可以交换任意两个元素，最少需要交换（）次。

A.4B.5

C.6D.7

二、问题求解（共2题，每题5分，共计10分）

1.（计数问题）将字符a,a,a,a,a,b,c,d,e进行排列，有

_（2分）种排法，若b,c,d,e中任何两个字母不相邻有（3分）种

排法。

2.（路径问题）邮递员需要寄送6份快件，分别位

于A,B,C,D,E,F六个地点，它们之间的通路以及

所需的时间如右图，如果要尽快把这6份邮件送完，选择最，114

分钟。

三、阅读程序写结果（共4题，每题5分，共计20分）

1.programal;

vara,b,c,d,e:integer;

begin

a:=l;

b:=a+2;

c:=b+3;

d:=c+4;

a:=d+5;

fore:=lto4do

begin

ifamod2=0

thena:=adiv2+d

elsea:=adiv2+d+l;

b:=a+2;

c:=b+3;

d:=c+4;

a:=d+5;

end;

writeln(a);

end.

输出：___________________

2.programa2;

var

m,n,p:integer;

functionged(a,b:integer):integer;

var

r:integer;

begin

r:=amodb;

ifr=0thenged:=b

elseged:=ged(b,r)

end;

begin

write('Enterthenumbersmandn:');

readln(m,n);

p:=ged(m,n);

writein('ged(\m,1/,n,J)=',p);

readln

end.

、—A-,

运仃:

Enterthenumbersmandn:5688

输出:____________________

3.programa3;

var

n,m,s,f,t:integer;

a:array[1..50]of0..1;

begin

writeInputn,m=，);

readln(m,n);

fort:=1tomdo

a[t]:=0;

f:=0;t:=0;s:=0;

writein(JSequencecomingoutfromqueueis:');

repeat

t:=t+l;

ift=m+lthent:=l;

ifa[t]=0thens:=s+l;

ifs=nthen

begin

s:=0;

write(t:3,'');

a[t]:=1;

f:=f+l;

end

untilf=m;

writein;

end.

运仃：

Inputn,m=94

输出：Sequencecomingoutfromqueueis:

4.proceduresolve(first:string;spos_f,epos_f:integer;mid:string;sp

os_m,epos_m:integer);

var

i,root_m:integer;

begin

ifspos_f>epos_fthenexit;

fori:=spos_mtoepos_mdo

iffirst[spos_f]=mid[i]thenbegin

root_m:=i;

break;

end;

solve(first,spos_f+l,spos_f+(root_m-spos_m),mid,spos_m,root_m-l);

solve(first,spos_f+(root_m-spos_m)+1,epos_f,mid,root_m+l,epos_m);

write(first[spos_f]);

end;

var

first,mid:string;

len:integer;

begin

readIn(len);

readln(first);

readln(mid);

solve(first,1,len,mid,1,len);

writein;

end.

输入：7

ABDCEGF

BDAGECF

输出：_______________________________________

四、完善程序（10个空格，每个空格3分，共30分）

1.火车转轨问题

右图中有2条轨道连到一个铁路

转轨处，形成一个铁路转轨网络的栈。

其中右边轨道为输入端，左边轨道为

输出端。如果执行了Push,Push,Po

p,Push,Push,Pop,Pop,Pop,就

会将输入端的车皮编号顺序1,2,3,4,变成2,4,3,1,请编程求左边车皮

编号为1,2,3,4时，在右边轨道可能得到的所有车皮编号顺序。

PROGRAMBl;

CONSTn=4;

VAR

a,b,c:array[1..n]ofinteger;

top,i:integer;

FUNCTIONjudge(m:integer):Boolean;

VAR

sO,si:integer;

i:integer;

BEGIN

judge:=true;

s0:=0;

si:=0;

FORi:=1to2*nDO

BEGIN

IFmmod2=0THENsO:=sO+lELSEsl:=sl+l;

m:=mdiv2;

IF①THENBEGIN

judge:=false;

exit;

END;{THEN}

END;{FOR}

IF②THENBEGIN

judge:=false;

exit;

END;{THEN}

END;{judge}

PROCEDUREpush;

VAR

i:integer;

BEGIN

b[top]:=a[l]；

top:=top+l;

FORi:=1ton-1DOa[i]:=a[i+l];

a[n]:=0;

write(，push');

END;{push}

PROCEDUREpop;

VARi:integer;

BEGIN

top:二top-1;

FORi:=1ton-1DOc[i]:=c[i+l];

c[n]:=b[top];

write('POP');

END;{pop}

PROCEDUREprint(m:integer);

VAR

t:array[1..2*n]ofBoolean;

i:integer;

BEGIN

write(m,'');

FORi:=ltonDOa[i]:=i;

FORi:=1to2*nDO

BEGIN

t[i]：=(mmod2=0);

③

END;

FORi:=2*ndownto1do

IF⑷THENpopELSEpush;

FORi:=1tonDOwrite(c[i]);

writein;

END;

BEGIN

top:=l；

fori:=1to255DO

IF⑤thenprint（i）;

writein;

END.

2.（棋盘覆盖问题）在一个2kX2k个方格组成的棋盘中恰有一个方格与其他

方格不同（图中标记为T的方格），称之

为特殊方格。现用L型（占3个小格）纸

33

片覆盖棋盘上除特殊方格的所有部分，各纸

c-113

片不得重叠，于是，用到的纸片数恰好是（44115

k-1）/3。在下表给出的一个覆盖方案中，4455

k=2,相同的3个数字构成一个纸片。

下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、

左下角、右下角，递归进行。请将程序补充完整程序如下：

PROGRAMj402;

TYPE

arrl=array[1..65]ofinteger;

arr2=array[1..65]ofarrl;

VAR

board:arr2;

tile:integer;

size,dr,de:integer;

PROCEDUREchessboard(tr,tc:integer;dr,de:integer;VARsize:integer);

VARt,s:integer;

BEGIN

IF(size=l)THENexit;

t:=tile;inc(tile);

s:=sizediv2;

IF⑥THEN

chessboard(tr,tc,dr,de,s)

ELSE

BEGIN

board[tr+s-1][tc+s-1]:=t;

___________色_____________；

END;{ELSE}

IF(dr<tr+s)AND(dc>=tc+s)THEN

chessboard(tr,tc+s,dr,de,s)

ELSE

BEGIN

board[tr+s-1][tc+s]:=t;

____________________________；

END;

IF(dr>=tr+s)AND(dc<tc+s)THEN

chessboard(tr+s,tc,dr,de,s)

ELSE

BEGIN

board[tr+s][tc+s-1]:=t;

______________________________；

END;

IF(dr>=tr+s)AND(dc>=tc+s)THEN

chessboard(tr+s,tc+s,dr,de,s)

ELSE

BEGIN