衢州市第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