信息學(xué)競賽初中組初賽模擬試題（一）及答案選擇題（共20題，每題1.5分，合計30分。每題有5個備選答案，前10個題為單項選擇題，即每題有且只有一種對的答案，選對得分；後10題為不定項選擇題，即每題有1至5個對的答案，只有所有選對才得分）1.操作系統(tǒng)是一類重要的系統(tǒng)軟件，下面幾種軟件不屬于系統(tǒng)軟件的是（

）。

A）MS-DOS

B）Linux

C）Java

D）Windos

98

E）Unix2.

按照網(wǎng)絡(luò)覆蓋面積和各臺計算機相距的遠近，計算機網(wǎng)絡(luò)分為(

)

A)廣域網(wǎng)和局域網(wǎng)B)信息互換網(wǎng)和廣域網(wǎng)

C)分布式系統(tǒng)和集中式系統(tǒng)D)公用網(wǎng)和專用網(wǎng)E)總線網(wǎng)和星型網(wǎng)3.某計算機的硬盤容量是40G，這裏40G=(

)字節(jié).

A)40

B)40*1000

C)40*1024*1024

D)40*1024*1024*1024

E)40*1000*1000*10004．中綴體現(xiàn)式A-(B+C/D)*E的後綴體現(xiàn)式是（

）。

A)AB-C+D/E*

B)

ABC+D/-E*

C)ABCD/E*+-

D)ABCD/+E*-

E)

AB-CD/-E*5.設(shè)一種[1..100,1..100]的二維數(shù)組A,每個元素A[i,j]存儲時占用兩個字節(jié),將A數(shù)組按行優(yōu)先方式存入從SA開始的持續(xù)存儲單元中,則元素A[66,65]存儲的結(jié)束地址是(

)。A)SA+13130

B)SA+13129

C)SA+6565

D)SA+6564

E)SA+13128

6.Windows操作系統(tǒng)是一種多任務(wù)操作系統(tǒng),各應(yīng)用程序之間可以非常以便地通過(

)來互換數(shù)據(jù).

A)復(fù)制3

B)讀/寫文獻

C)剪貼板

D)剪切

E)粘貼

7.多媒體技術(shù)中的”多媒體”的含義重要是指如(

)等表達信息的形式.

A)磁盤、光盤

B)聲音、圖象

C)電纜、光纖

D)聲卡、匯圖儀

E)音箱、顯示屏

8.在數(shù)據(jù)構(gòu)造中鏈表是(

).

A)次序存儲的線性表構(gòu)造

B)

非次序存儲的線性表構(gòu)造

C)

次序存儲的非線性表構(gòu)造D)

非次序存儲的非線性表構(gòu)造E)

特殊的樹構(gòu)造

9.

計算機輔助教學(xué)的簡寫是

(

).

A)CAI

B)CAM

C)CAD

D)CAS

E)CAT

10.給定一種正整數(shù)N=，現(xiàn)決定依次刪除其中6個數(shù)位上的數(shù)字（每次刪除一種數(shù)位上的數(shù)字），每次刪除後按本來的次序構(gòu)成一種新數(shù)M的值均是目前狀態(tài)下的最小數(shù)，則第四次應(yīng)當(dāng)刪除的數(shù)字是(

).

A)6

B)8

C)7

D)4

E)3

11.算法的基本構(gòu)造有(

).

A)次序

B)選擇

C)判斷

D)循環(huán)

E)反復(fù)

12.計算機主機由(

)構(gòu)成.

A)CPU

B)主板

C)機箱

D)主存

E)顯示屏

13.算式(1011)2*(11.1)2的成果是(

).

A)(100110.1)2

B)(1011111)2

C)(38.5)10

D)(26.8)16

E)(46.4)8

14.如下是有關(guān)計算機病毒的說法，對的的是(

)

A)病毒屬于計算機軟件

B)病毒屬于硬件

C)病毒具有破壞性、傳播性、可激發(fā)性、潛伏性、隱蔽性等特點

D)若軟盤染上病毒，能清除病毒的措施是刪除該軟盤上的所有文獻

E)若軟盤染上病毒，能清除病毒的措施是格式化該軟盤

15.下列有關(guān)拾進制數(shù)-100的對的說法是(

).

A)原碼為11100100BB)反碼為E4H

C)反碼為9BH

D)補碼為64H

E)補碼為9CH

16.如下是有關(guān)排序的說法對的的是(

).

A)選擇排序、冒泡排序、插入排序是穩(wěn)定的

B)希爾排序、迅速排序、堆排序的時間復(fù)雜度為O(nlog2n)

C)線形排序的時間復(fù)雜性為O(n)

D)線形排序、二路歸并排序的空間復(fù)雜度為O(n)

E)希爾排序、迅速排序、堆排序、歸并排序是不穩(wěn)定的

17．下列是有關(guān)數(shù)據(jù)構(gòu)造的說法對的的是（

）。

A)數(shù)據(jù)構(gòu)造是帶有構(gòu)造的數(shù)據(jù)元素的集合B)線性表的線性存儲構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?gòu)造

C)隊列是一種先進先出的線性表

D)隊列是只能在一端插入，另一端刪除的線性表

E)棧的插入和刪除只能在棧底進行

8.下列IP地址中錯誤的是(

).

A)202.300.12.4B)C)100:128:35:91

D)111-102-35-21E)

19.有關(guān)二叉樹的對的說法是（

）。

A)完全二叉樹一定是滿二叉樹B)滿二叉樹一定是完全二叉樹

C)深度為h的二叉樹最多有2h-1個結(jié)點(h>=1)，至少有h個結(jié)點

D)對于任意一棵二叉樹，假如其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1

E)在二叉樹中，第i層的結(jié)點總數(shù)不超過2i-1；

20.

如下有關(guān)圖的對的說法是(

)。

A)所有頂點的度數(shù)之和等于邊數(shù)的2倍

B)所有頂點的度數(shù)之和不一定等于邊數(shù)的2倍

C)任意一種圖一定有偶數(shù)個奇點D)任意一種圖一定有奇數(shù)個偶點

E)在有向圖中頂點的入度之和等于出度之和

二.問題求解（5分*2=10分）

1.已知:1到10中有兩個數(shù)1、7不能被2，3，5整除，那么1到1000中有多少個數(shù)不能被2，3，5

整除？

2.

一種棧(無窮大)的進棧序列為1,2,3,..n,有多少種不一樣的出棧序列?

如n=3時,出棧序列有1,2,31,3,22,1,32,3,13,2,1共5種，問:當(dāng)n=5時的出棧種數(shù)是多少(只求種數(shù))？

三.閱讀程序?qū)懗鰧Φ牡某绦蜻\行成果(4分*8=32分)

1.program

t1;

var

a,b,n:longint;

begin

readln(n);

a:=0;b:=0;

repeat

a:=a+1;b:=b+a;

until

b>=n;

writeln(a);

end.

輸入:0

輸出:

2.program

t2;

const

n=200;

var

si,pr:set

of

2..n;

x,j,m:integer;

begin

readln(m);

si:=[2..m];pr:=[];

x:=2;

repeat

while

not(x

in

si)

do

x:=succ(x);

pr:=pr+[x];

j:=x;

while

j

<=

m

do

begin

si:=si-[j];j:=j+x;

end;

until

si=[

];

j:=0;

for

x:=m

downto

2

do

if

x

in

pr

then

begin

write(x:5);inc(j);

if

j

mod

10=0

then

writeln;

end;

writeln;

end.

輸入：50

輸出：

3.program

t3;

var

a:array[1..9,1..9]

of

string;

st,x:string;

i,j,n,m:integer;

begin

repeat

writeln('please

input

a

string(length<10):');

readln(st);

n:=length(st);

until

(n

<

10)

and

odd(n);

m:=(n+1)

div

2;

for

i:=1

to

n

do

for

j:=1

to

n

do

a[i,j]:='

';

for

i:=1

to

m

do

for

j:=i

to

n+1-i

do

begin

x:=copy(st,j,1);

a[i,j]:=x;

a[n+1-i,n+1-j]:=x

end;

for

j:=n

downto

1

do

begin

for

i:=1

to

n

do

write(a[i,j]:2);

writeln;

end;

end.

輸入：ABCDEFG

輸出：

4.program

t4;

var

m,n:byte;

procedure

fen(i,j:byte;s:string);

var

k:byte;

s1:string;

begin

if

j=1

then

writeln(m,'=',s,i)

else

for

k:=1

to

i-j+1

do

begin

str(k,s1);

fen(i-k,j-1,s+s1+'+');

end;

end;

begin

readln(m,n);

fen(m,n,'

');

end.

輸入:5

3

輸出:

四.完善程序題(4分*4+2分*6=28分)

1．單源點最短途徑：給定帶權(quán)有向圖G=(v,e),源點v1在v中，求v1到v中其他各結(jié)點的最短途徑。

數(shù)據(jù)構(gòu)造闡明：

cost[I,j]:表達帶權(quán)有向圖的鄰接矩陣

d[j]：表達從v1到vj的最短途徑長度

path[j]：表達從v1到vj的最短途徑

程序如下:

program

t5;

const

n=5;

maxnum=1e10;

type

gr=array[1..n,1..n]

of

real;

dt=array[1..n]

of

real;

jh=set

of

1..n;

pt=array[1..n]

of

jh;

var

s:jh;

cost:gr;

d:dt;

path:pt;

i,j,k:integer;

mm:real;

begin

for

i:=1

to

n

do

for

j:=1

to

n

do

read(cost[i,j]);

s:=[1];

for

i:=2

to

n

do

begin

d[i]:=cost[1,i];

if

d[i]

<

maxnum

then

path[i]:=[1]+[i]

else

___（1）___

end;

for

i:=1

to

n-1

do

begin

mm:=maxnum;

for

j:=2

to

n

do

if

___（2）___

then

begin

mm:=d[j];k:=j;

end;

s:=s+[k];

for

j:=2

to

n

do

if

not(j

in

s)

and

(cost[k,j]

<

maxnum)

then

if

___（3）___

then

begin

d[j]:=d[k]+cost[k,j];

path[j]:=___（4）___

end;

end;

writeln;

for

i:=2

to

n

do

begin

writeln('v1->','v',i,':',d[i]);

write('v1');

for

j:=2

to

n

do

if

j

in

path[i]

then

write('->','v',j);

writeln;

end;

end.

2.

問題描述:將n個整數(shù)提成k組(k≤n,規(guī)定每組不能為空),顯然這k個部分均可得到一種各自的積

p1,p2,……pk,定義整數(shù)S為:S=(p1-p2)2+(p1-p3)2+……+(p1-pk)2+(p2-p3)2+……+(pk-1-pk)2

問題求解:求出一種分法,使S為最大(若有多種方案僅記一種〉

程序闡明:

數(shù)組:a[1],a[2],...A[N]寄存原數(shù)

p[1],p[2],...,p[K]寄存每個部分的積

b[1],b[2],...,b[N]窮舉用臨時空間

d[1],d[2],...,d[N]寄存最佳方案

程序:

program

t6;

Var

i,j,n,k

:

integer;

Sum,cmax:longint;

a

:array

[1..100]

of

integer;

b,d:array

[0..100]

of

integer;

p

:array[1..30]

of

integer;

begin

readln(n,k);

for

I:=1

to

n

do

read(a[I]);

for

I:=0

to

n

do

b[I]:=1;

cmax:=0;

while

(b[0]=1)

do

begin

for

I:=1

to

k

do

___（5）___;

for

I:=1

to

n

do

___（6）___;

sum:=0;

for

I:=1

to

k-1

do

for

j:=___（7）___

do

sum:=sum+(p[I]-p[j])*(p[I]-p[j]);

if

___（8）___

then

begin

cmax:=sum;

for

I:=1

to

n

do

d[I]:=b[I];

end;

j:=n;

while

___（9）___

do

j:=j-1;

b[j]:=b[j]+1;

for

I:=j+1

to

n

do

___（10）___

;

end;

writeln(cmax);

for

I:=1

to

n

do

write(d[I]:40);

writeln;

end.初賽模擬試題（一）答案一、選擇題（共20題，每題1.5分，合計30分）

1、C2、A3、D

4、D。中綴體現(xiàn)式是對二叉樹-A*+B/CDE的中序遍歷，其後綴體現(xiàn)式，即後序遍歷成果為ABCD/+E*-

5、B。數(shù)組元素A[66,65]存儲的起始地址是SA+13128，而結(jié)束地址則是SA+13130-1

6、C7、B8、B9、A10、D11、ABD12、ABD13、ACDE

14、ACDE15、ACE16、BCD17、ACD

18、ACD。IP地址是由4個10進制數(shù)構(gòu)成，每個數(shù)都在0～255之間，且彼此用.分隔。

19、BCDE20、ACE

二.問題求解（5分*2=10分）

1、2662、42

三.閱讀程序?qū)懗鰧Φ牡某绦蜻\行成果(4分*8=32分)

1、200。b=(1+a)*a/2，即b>=0……

2、實際上是求1～50以內(nèi)的質(zhì)數(shù)，并按規(guī)定輸出：

47

43

41

37

31

29

23

19

17

11

7

5

3

2

3、輸出：

G

A

F

F

B

B

E

E

E

C

C

C

D

D

D

D

D

D

D

C

C

C

E

E

E

B

B

F

F

A

G

4、輸出：

5＝

1＋1＋3

5＝

1＋2＋2

5＝

1＋3＋1

5＝

2＋1＋2

5＝

2＋2＋1

5＝

3＋1＋1

四、完善程序題(4分*4+2分*6=28分)

1．(1)path[i]:=[i]

(2)not

(j

in

s)

and

(d[j]

<

mm)

(3)(d[k]+cost[k,j])

<

d[j]

(4)path[j]+[k]

2．

(5)p[i]:=1

(6)p[b[i]]:=p[b[i]]*a[i]

(7)i+1

to

k

(8)cmax

<

sum(9)b[j]=k

(10)b[i]:=1

信息學(xué)競賽初中組初賽模擬試題(二)

及答案

一、選擇題：（共20小題，1-15小題為單項選擇題，每題1分；16-20小題為多選題，每題2分。共25分）

1.對存儲器按字節(jié)進行編址，若某存儲器芯片共有10根地址線的引腳，則該存儲器芯片的存儲容量為(

)。

(A)512B

(B)1KB

(C)2KB

(D)4KB

(E)8KB

2.在待排序的數(shù)據(jù)表已經(jīng)為有序時，下列排序算法中花費時間反而多的是(

)。

(A)堆排序

(B)希爾排序

(C)冒泡排序

(D)迅速排序

(E)二分排序

3.某數(shù)列有1000個各不相似的單元，由低至高按序排列，現(xiàn)要對該數(shù)列進行二分法檢索，在最壞的狀況下，需要檢索(

單元。

(A)1000

(B)10

(C)100

(D)500

(E)300

4.已知數(shù)組a中，每個元素a[i,j]在存儲時要占3個字節(jié)，設(shè)i從1變化到8，j從1變化到10，分派內(nèi)存實是從地址sa開始持續(xù)按行存儲分派的。試問：a[5，8]的起始地址為(

)。

(A)sa+141

(B)sa+180

(C)sa+222

(D)sa+225

(E)sa+155

5.在pascal語言過程調(diào)用時，數(shù)值形參得到的是實際參數(shù)的(

。

(A)數(shù)值

(B)地址

(C)值

(D)變量

(E)以上都不是

6.一種24*24點陣的中文字形信息所占的字節(jié)數(shù)為(

。

(A)2

(B)

8

(C)

24

(D)

32

(E)

72

7.在微機系統(tǒng)中，最基本的輸入輸出模塊BIOS寄存在(

中。

(A)RAM

(B)ROM

(C)硬盤

(D)寄存器

(E)控制器

8.拾進制算術(shù)體現(xiàn)式:3*512+5*64+2*8+1的運算中,用二進制表達為(

。(A)(B)(C)(D)

(E)111000

9.設(shè)棧S的初始狀態(tài)為空,現(xiàn)對序列{1,2,3,4,5}在棧S上,依次進行如下操作(從元素1開始,出棧後不再進棧):進棧,出棧,進棧,進棧,出棧,出棧。試問出棧的元素序列是(

。

(A){1,2,3}B){1,3,2}C){3,2,1}D){2,3,1}

(E)以上都不對

10.E-mail郵件本質(zhì)上是一種(

(A)文獻(B)電報(C)電話(D)傳真

(E)電訊

11.一棵二叉樹的高度為h，所有結(jié)點的度為0，或為2，則此樹至少有(

個結(jié)點

(A)2h-1(B)2h-1(C)2h+1(D)h+1

(E)h*h+1

12.無向圖G=(V，E)，其中V={a,b,c,d,e,f}

E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}對該圖進行深度優(yōu)先遍歷,得到的頂點序列對的的是(

(A)a,b,e,c,d,f(B)a,c,f,e,b,d(C)a,e,b,c,f,d(D)a,b,e,d,f,c(E)以上都不對

13.pascal編譯程序是(

（A）.把pascal源程序轉(zhuǎn)換成可運行的EXE文獻的程序

（B）.把pascal源程序轉(zhuǎn)換成等價的目的碼的程序

（C）.生成和修改一種pascal語言源程序的等程序

（D）.把pascal的目的碼程序轉(zhuǎn)換成可運行的EXE文獻的程序

（E）.生成一種等價的匯編程序

14.將三封信投到4個郵筒，最多的投法有（

）

（A）．

種

（B）．

種

（C）．

種

（D）．種

E.

15.電子信函(電子郵件)的特點之一是（

）。

（A）.比郵政信函，電報，電話，傳真都更快

（B）.在通信雙方的計算機之間建立其直接的通信線路後即可迅速傳遞數(shù)字信息

（C）.采用存儲-轉(zhuǎn)發(fā)方式在網(wǎng)絡(luò)上逐漸傳遞信息,不象電話那樣直接、及時,但費用低廉

（D）.在通信雙方的計算機都開機工作的狀況下即可迅速傳遞數(shù)字信息

16.如下屬于多媒體硬件的是（

）

（A）．主機

（B）.光驅(qū)

（C）.聲卡

（D）.音箱

（E）.超級解霸

17.對的的二維數(shù)組類型闡明是(

)

(A)typear2=array[1..5,5..1]ofinteger;

(B)typear2=array[1..5]ofarray[5.1]ofinteger;

(C)typear2=array[1..5,1..5]ofinteger;

(D)typear2=array[1..5]ofarray[1..5]ofinteger

(E)typear2=array[1..5,1..5]of0..1

18.下列屬于信息處理的是（

）

（A）信息加工

（B）信息分類

（C）信息技術(shù)

（D）信息采集

（E）信息存儲

19.在windows中,最小化一種應(yīng)用程序窗口後，該程序?qū)ⅲ?/p>

）。

(A)被終止執(zhí)行

(B)被暫停執(zhí)行(C)被轉(zhuǎn)入後臺

(D)繼續(xù)執(zhí)行（E）以上答案都不對

20.下面的常量闡明中，對的的是（

）（A）CONST

（B）、CONST

（C）、CONST

（D）、CONST

（E）CONST

t=true

b,C=45

M=100，15

N=1OR2

a=’A’

二、問題求解：（第1小題5分，第2-3小題各4分,共13分）

[問題1]:在所有三位數(shù)中，各位數(shù)字從高位到低位順次減小的數(shù)共有

個。

[問題2]："銀條"

一位銀礦勘探員無力預(yù)付3月份的房租。他有一根長31英寸的純銀條，因此他和女房東到達如下協(xié)議。他說，他將把銀條切成小段。3月份的第一天，他給女房東1英寸長的一段，然後每天給她增長1英寸，以此作為抵押。勘探員預(yù)期到3月份的最終一天，他能全數(shù)付清租金，而屆時女房東將把銀條小段所有還給他。3月份有31天，一種措施是把銀條切成31段，每段長1英寸?？墒沁@處花諸多功夫?？碧絾T但愿既履行協(xié)議，又能使銀條的分段數(shù)目盡量減少。例如，他可以第一天給女房東1英寸的一段，第二天再給1英寸的一段，第三開他取回這兩段1英寸的而給她3英寸的一段。假設(shè)銀條的各段是按照這種方式來回倒換的話，勘探員至少需要把他的銀條切成______段？

[問題3]:"換不開的現(xiàn)金"

錢柜裏有1.15美分，一位顧客提出：把1美元的現(xiàn)金換成硬幣，但出納小姐說換不開，後來這位顧客提出：把50美分的現(xiàn)金換成硬幣，但出納小姐又說換不開，而實際上，出納小姐也無法把25美分、10美分、5美分的現(xiàn)金換成硬幣。請問錢柜裏究竟有哪些硬幣？他們分別有多少枚？

答：_________________。

三、寫出程序的運行成果：（每題6分，共30分）1.

programtext1;

constn=6;m=3;

vari,j,k:integer;

begin

fori:=-ntondo

begin

k:=n-abs(i);

write('':39-k);

forj:=-ktokdo

ifabs(j)>k-m

thenwrite(n-(i+n)div2)

elsewrite('');

writeln;

end;

end.

輸出的成果為：

2.PROGAMtext2；

VARa:ARRAY[1..10]OFChar；

k:Integer；ch:Char；

BEGIN

FORk:=1TO10DOa[k]:=Chr(Ord('A')+k)；

FORk:=1TO10DO

BEGIN

ch:=a[k]；

a[k]:=a[11-k]；

a[11-k]:=ch；

END；

FORk:=1TO10DO

Write(a[k])；

Writeln

END.

輸出的成果為：

3.programtext3(input,output);

Varm,n,p:integer;

x:real;

proceduremm(varm:integer;x:real);

varn:integer;

begin

m:=m+1;

n:=m+1;

x:=n*3;

p:=n;

end;

begin

m:=8;n:=5;p:=3;x:=1.0;

mm(n,x);

writeln(m:5,n:5,p:5,x:6:1);

end.

輸出的成果為：

4.programtext4;

constn=5;

typeary=array[0..n-1,0..n-1]ofinteger;

vara:ary;i,j,k:integer;

begin

fori:=0ton-1do

forj:=0ton-1doa[i,j]:=0;

k:=1;

fori:=1tondo

forj:=n-1downtoido

begin

a[j,j-i]:=k;

k:=k+1;

end;

fori:=0ton-1do

begin

forj:=0ton-1do

write(a[I,j]:4);

writeln;

end;

end.

輸出的成果為：

5.programtext5(input,output);

varch:char;

i,n,sum:integer;

beginsum:=0;

read(ch);

casechof

'A':fori:=4to6do

begin

read(n):

sum:=sum＋n

end;

'B'：beginread(n);

fori:=1tondo

beginread(n);sum:=sum＋nend;

end;

'C':repeat

read(n);sum:=sum＋n

untilsum>10;

'D':beginread(n);

whilen<=3do

beginsum:=sum＋n;read(n)end

end

end;writeln(sum:4)

end.

當(dāng)程序運行

(1)輸入A4123456789時，其輸出為_____________。

(2)輸入B4123456789時，其輸出為_____________。

(3)輸入C4123456789時，其輸出為_____________。

(4)輸入D4123456789時，其輸出為_____________。

四、完善程序（第1題每空2分第2、3題每空3分，共32分）

第1題

孿生素數(shù)是指兩個相差為2的素數(shù)，例如：3和5，5和7，11和13等。

下面程序可輸出15對孿生素數(shù)，其中函數(shù)q判斷整數(shù)a與否為素數(shù)。

programp(output);

var

k,n:integer

q(a:integer):booklean;

var

k:integer;

flag:boolean;

begin

flag:___(1)____

k:=2

___(2)____(k<=adiv2)andflagdo

ifamodk=0then

______(3)_______

else

k:=k+1

q:=flag

end;

begin

n:=0;

k:=2;

repeat

ifq(k)and___(4)___then

begin

n:=n+1;

writeln(k,k+2)

end;

k:=K+1

untiln=5

end.

第二題

已知有類型arr=array[1..16]ofstring;

arr型數(shù)組a中寄存著從第1屆到第16屆足球世界杯冠軍國家的名字，下面的函數(shù)可求出歷界世界杯比賽共有幾種國家曾獲得過世界杯冠軍，請?zhí)羁胀戤叀?/p>

text2(a:arr):integer;

vark,j,s:integer;

mult:boolean;

begin

___(5)___;

forj:=2to16do

begin

k:=1;

mult:=false;

whilenotmultand___(6)___do

if___(7)__thenmult:=ture

elsek:=k+1;

ifnotmultthens:=___(8)___

end;

text2:=s

end;

第三題

Fibonacci（裴波那契）數(shù)列的規(guī)律是：前2個數(shù)均為1，從第3個數(shù)開始每個數(shù)等于它前面兩個數(shù)之和，即：1，1，2，3，5，8，13，21，34，55，89，144，233，377，...。已知任意一種不小于0的整數(shù)可以表達為若干個互不相似的fibonacci之?dāng)?shù)和。

例如：121=89+21+8+3

下面的程序是由鍵盤輸入一種正整數(shù)n，輸出構(gòu)成n的互不相似的fibonacci數(shù)。

例如：若輸入121

則輸入121=+89+21+8+3

本程序的算法如下：（n=121為例）

1）尋找不不小于或等于n的最大的fibonacci數(shù)a（例如89），并以a作為構(gòu)成n的一種數(shù)輸出。

2）若n≠a則以n-a作為新的任意正整數(shù)（例如32），反復(fù)環(huán)節(jié)1.若n=a，則結(jié)束。程序中的函數(shù)find返回不不小于或等于n的最大的fibonacci數(shù)。

programtext3(input,output);

var

n:integer;

find(n:integer):integer;

vara,b,c:integer;

begin

a:=1;b:=1;

repeat

c:=___(9)___;

a:=b;b:=c;

untilb>=n;

ifb=nthenfind:=___(10)___

elsefind:=___(11)___

end;

procedurep(n:integer);

vara:integer;

begin

a:=find(n);

write('+',a:4);

ifa<nthen

p___(12)___

end;

begin

readln(n);

write(n:5,'=');

p(n);

writeln

end.初賽模擬試題（二）參照答案

一、選擇題：（本題共20小題，1-15小題為單項選擇題，每題1分；16-20小題為多選題，每題2分。共25分）

題號12345678910

答案BDBABEBCBA

題號1112131415

答案BDBCC

題號1617181920

答案ABCDCEABDECDAE

二、問題求解：（第1小題3分，第2-3小題各5分,共13分）

[問題1]：

120

[問題2]：

5

[問題3]：

50美分1枚，25美分1枚，10美分4枚，5美分1枚，1美分4枚

三、寫出程序的運行成果：（每題6分，共30分）1、輸出成果為：

2、輸出成果為：

BCDEFGHIJK

6

666

55555

555

555

444

444

444

444

333

333

333

333

222

222

222

222

11111

111

0

3、輸出成果為：

4、輸出成果為：

8

6

7

1.0

0

0

0

0

0

4

0

0

0

0

7

3

0

0

0

9

6

2

0

0

10

8

5

1

0

5、當(dāng)程序運行

(1)輸入A4123456789時，其輸出為______7_____。

(2)輸入B4123456789時，其輸出為______10____。

(3)輸入C4123456789時，其輸出為_______14___。

(4)輸入D4123456789時，其輸出為________0___。

四、完善程序（第1題每空2分第2、3題每空3分，共32分）

第1題

（1）

true

（2）

while

（3）

flag:=false

（4）

F(K+2)=true或F(K+2)

第2題

（5）

s:=1

（6）

(k<j)若無（）扣1分

（7）

a[j]=a[k]

（8）

s+1或s+1;或succ(s)

第3題

（9）

a+b或b+a

（10）

b或c或n

（11）

a或a;

（12）

n-a信息學(xué)競賽初中組初賽模擬試題(三)及答案

一、選擇題：（選出每題對的的答案代碼，填在括號裏，1—10題為單項選擇題，每題只有一種對的答案，11—20題為不定項選擇題，每題有一種或一種以上的對的答案，共20題，每題1.5，共30分）

1、二進制數(shù)01100100轉(zhuǎn)換成拾六進制數(shù)是（

）。

A．32

B．64

C．128

D．100

E．256

2、操作系統(tǒng)是一類重要的系統(tǒng)軟件，下面幾種軟件中，不屬于系統(tǒng)軟件的是（

）。

A．Java

B．MS-DOS

C．Linux

D．Windows

E．Unix

3、計算機病毒的傳染是以計算機運行和（

）為基礎(chǔ)的，沒有這兩個條件，病毒是不會傳染的。

A．編輯文稿

B．讀寫磁盤

C．編程序

D．掃描圖畫

E．打印

4、因特網(wǎng)不屬于任何個人，也不屬于任何組織。其中在網(wǎng)絡(luò)知識這一塊中有一種英文簡寫ISP，它的中文意思是（

）。

A．因特網(wǎng)連接

B．因特網(wǎng)使用

C．因特網(wǎng)設(shè)計

D．因特網(wǎng)服務(wù)提供者

E．信息傳播

5、Internet給我們提供了資源共享、瀏覽、檢索信息和遠程登錄等多種服務(wù)，下面幾種選項中用于遠程登錄的是（

）。

A．WWW

B．TCP/IP

C．Telnet

D．E-mail

E．FTP

6、IE是目前流行的瀏覽器軟件，它的工作基礎(chǔ)是解釋執(zhí)行用（

）語言書寫的文獻。

A．VC

B．HTML

C．BASIC

D．HTTP

E．VB

7、給出3種排序：插入排序、冒泡排序、選擇排序。這3種排序的時間代價分別是（

）。

A．O(n)、O(n2)、O(logn)

B．O(logn)、O(n)、O(n2)

C．O(n2)、O(n)、O(logn)

D．O(n2)、O(n)、O(n)

E．O(n2)、O(n2)、O(n2)

8、一棵完全二叉樹的結(jié)點總數(shù)為18，其葉結(jié)點數(shù)為（

）。

A．7個

B．8個

C．9個

D．10個

E．11個

9、在流程圖的符號中，菱形框一般作為（

）。

A．起始框

B．判斷框

C．輸入輸出框

D．處理工作框

E．結(jié)速框

10、在處理計算機主機與打印機之間速度不匹配時一般設(shè)置一種打印數(shù)據(jù)緩沖區(qū)，重要將要輸出打印的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應(yīng)當(dāng)是一種（

）構(gòu)造。

A．堆棧

B．?dāng)?shù)組

C．線性表

D．隊列

E．鏈表

11、多媒體技術(shù)中的“多媒體”的含義重要是指如（

）等多種體現(xiàn)信息的形式。

A．磁盤

B．音箱

C．顯示屏

D．聲音

E．圖像

12、下面有關(guān)計算機知識闡明，對的的是（

）。

A．在WINDOWS98操作系統(tǒng)下，刪除磁盤中的文獻時都先寄存在回收站中

B．FOXMAIL是用于收發(fā)電子郵件的工具

C．文獻夾組織是一種有層次的樹狀構(gòu)造，其中最頂層的是桌面

D．存儲器具有記憶能力，其中的信息任何時候都不會丟失

E．為了提高軟件的測試效率，應(yīng)當(dāng)選擇發(fā)現(xiàn)錯誤的也許性大的測試數(shù)據(jù)

13、對按關(guān)鍵字排序好的線性表進行二分查找，該線性表適合的存儲構(gòu)造為（

）。

A．鏈接存儲

B．索引存儲

C．散列存儲

D．次序存儲

E．循環(huán)存取

14、一種棧的輸入次序為1、2、3、4、5，下列序列中也許是棧的輸出序列的是（

）。

A．54312

B．24135

C．21543

D．12534

E．12345

15、評價一種算法的好壞有多種指標(biāo)，下列是算法評價指標(biāo)的是（

）。

A．對的性

B．運行時間

C．占用空間

D．迭代次數(shù)

E．簡樸性

16、下面描述用多維數(shù)組表達的數(shù)據(jù)構(gòu)造的語句中，對的的是（

）。

A．多維數(shù)組寄存的都是同一種類型的數(shù)據(jù)

B．多維數(shù)組各維的下標(biāo)范圍必須同樣

C．多維數(shù)組在內(nèi)存中的地址是持續(xù)的

D．多維數(shù)組中的下標(biāo)不能是體現(xiàn)式

E．多維數(shù)組是隨機存取的數(shù)據(jù)構(gòu)造

17、若已知一種棧的入棧次序1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn（它是輸入序列的一種排列），則在輸出序列中也許出現(xiàn)的狀況是（

）。

A．Pj<Pk<Pi，其中i<j<k

B．Pk<Pj<Pi，其中i<j<k

C．Pj<Pi<Pk，其中i<j<k

D．Pi<Pk<Pj，其中i<j<k

E．以上都不也許出現(xiàn)

18、線性表具有如下的構(gòu)造特點：（

）

A．均勻性

B．單一性

C．簡樸性

D．無序性

E．有序性

19、下列有關(guān)數(shù)據(jù)構(gòu)造的論述中對的的是（

）。

A．?dāng)?shù)據(jù)構(gòu)造是帶有構(gòu)造的數(shù)據(jù)元素的集合

B．線性表的線性存儲構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?gòu)造

C．隊列是限定僅在一端進行插入，在另一端進行刪除的線性表

D．二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表

E．圖是一種非線性數(shù)據(jù)構(gòu)造

20、任意一棵樹均可惟一地轉(zhuǎn)換成與它對應(yīng)的二叉樹。由樹轉(zhuǎn)換成的二叉樹中，頂點N的左右子女分別是N在原樹裏對應(yīng)頂點的（

）。

A．最左子頂點/最鄰近的右兄弟

B．最右子頂點/最右的兄弟

C．最鄰近的右兄弟/最左的兄弟

D．最鄰近的左兄弟/最鄰近的右兄弟

F．最鄰近的右兄弟/最右的兄弟

二、問題解答：（共2題，每題5分，共10分）

1、

光明中學(xué)開設(shè)數(shù)學(xué)、英語和信息學(xué)三個愛好學(xué)習(xí)小組，其中數(shù)學(xué)小組30人，英語小組15人，信息學(xué)小組18人，參與三個小組總?cè)藬?shù)為50人，其中有3人同步參與3個小組，那么同步只參與兩個小組的同學(xué)有多少人？

2、

給出一組頂點（頂點值用A，B，C，D，E，F(xiàn)表達），其對應(yīng)權(quán)值分別為2，3，1，7，8，4。請以A，B，C，D，E，F(xiàn)為葉子頂點構(gòu)造一棵哈夫曼樹，并求出它的最小帶權(quán)途徑長度WPL的值。

三、寫出程序的運行成果（共4題，每題8分，共32分）

第1題：

programtest1；

varn：integer；

count(n：integer)：integer；

begin

ifn=1thencount：=0

else

ifnmod2=0thencount：=count(ndiv2)+1

elsecount：=count(n*3+1)+1；

end；

begin

readln(n)；

writeln(count(n))；

end.

輸入：99

輸出：

第2題：

programtest2(input,output);

var

i,j,k,s:integer;

begin

s:=0

fori:=3downto1do

begin

forj:=1to3do

begin

k:=0;

repeat

k:=k+1;s:=s+k;

untilk=j;

end;

s:=s-(k+1);

end;

write(‘s=’,s);

end.

輸出：

第3題：

programtest3;

vara,b,n:longint;

begin

readln(n);

a:=0;b:=0;

repeat

a:=a+1;b:=b+a;

untilb>=n;

writeln(a);

end.

輸入：415377

輸出：

programtest4;

varm,n,i,p,k：integer;

r:array[1…200]ofinteger;

b:Boolean;

begin

m:=6;n:=2;

forI:=1tom-1dor[i]:=i+1;

r[m]:=1;i:=0;p:=1;b:=true;

whilebdo

begin

i:=i+1;k:=p;p:=r[p];

ifk=pthen

beginwriteln(p);b:=falseend

elseifi=n+1then

begin

write(p,‘

’);i:=0;p:=r[p];r[k]:=p;

end

end

end.

輸出：

四、完善程序（共2題，每題14分，共28分）

第1題（7分）

【問題描述】

設(shè)有n種物品，每種物品有一種重量及一種價值。但每種物品的數(shù)量是無限的，同步有一種背包，最大載重量為XK，今從n種物品中選用若干件（同一種物品可以多次選用），使其重量的和不不小于等于XK，而價值的和為最大。

【程序清單】

Programpackage;

constmaxxk=400;maxn=20;

typetlist=array[1…maxn]ofbyte;

tmake=array[0…maxn,0…maxxk]ofinteger;

varn,xk:integer;

w,u:tlist;

f:tmake;

procedureinit;

vari:byte;

begin

fillchar(w,sizeof(w),0);

fillchar(u,sizeof(u),0);

readln(n,xk);

fori:=1tondo

①

;

end;

proceduremake;

vari,j:byte;

begin

fori:=1tondo

begin

forj:=1tow[i]-1do

f[i,j]:=f[i-1,j];

forj:=w[i]toxkdo

iff[i-1,j]>f[i,j-w[i]]+u[i]then

②

;

else

③

;

end;

end;

procedureprint;

varget:tlist;

i,j:byte;

begin

fillchar(get,sizeof(get),0);

i:=

④

;j:=

⑤

;

whilei>0do

iff[i,j]=f[i-1,j]thendec(i)

elsebegin

dec(j,w[i]);

⑥

;

end;

writeln(‘n=’,n,‘,’,‘xk=’,xk);

writeln(‘maxworth=’,

⑦

;

fori:=1tondo

writeln(‘no.’,i‘,weight:’,w[i]:2,‘worth:’,u[i]:2,‘get’,get[i]:2);

end;

begin

init;

make;

print;

end.

第2題（7分）

【問題描述】

給定一種01串，請你找出長度介于a,b之間，反復(fù)出現(xiàn)次數(shù)最多的01串。

輸入：a,b(0<a<=b<=12)

由0，1組合的數(shù)列，由‘.’結(jié)尾。

輸出：規(guī)定的串。

提醒：本程序中將01序列轉(zhuǎn)換為2進制數(shù)存取。

【程序清單】

programshuchuan;

vari,j,s,k,a,b,max:integer;

m:array[1…8192]ofinteger;

two,v:array[1…20]ofinteger;

c:char;

begin

fori:=1to13do

①

;

readln(a,b);

read(c);

s:=1;k:=1;

whilec<>‘.’dobegin

s:=sshl1+ord(c)-48;

if

②

then

s:=((s-two[b+1])modtwo[b])+two[b];

inc(m[s]);

ifk<bthen

fori:=atok-1do

③

;

inc(k);

read(c);

end;

fori:=two[b]totwo[b+1]do

ifm[i]>0then

forj:=atob-1do

m[(imodtwo[j])+two[j]]:=

④

;

max:=0;

fori:=two[a]totwo[b+1]do

ifm[i]>maxthen

⑤

;

fori:=two[a]totwo[b+1]do

ifm[i]=maxthenbegin

j:=0;k:=I;

repeat

inc(j);v[j]:=kmod2;

⑥

;

until

⑦

;

whilej>0dobeginwrite(v[j]);dec(j)end;

writeln;

end;

end.初賽模擬題(三)參照答案

一、選擇題：（選出每題對的的答案代碼，填在括號裏，1—10題為單項選擇題，每題只有一種對的答案，11—20題為不定項選擇題，每題有一種或一種以上的對的答案，共20題，每題1.5，共30分）

題號12345678910

答案BABDCBECBD

題號11121314151617181920

答案DEBCEDCEABCEACEBCDAEACDEA

二、問題解答：（共2題，每題5分，共10分）

第1題：

7

第2題：

61

三、寫出程序的運行成果：（共4題，每題8分，共32分）

第1題：

25第2題：

s=18

第3題：

911第4題：

4

2

1

3

6

5

四、完善程序（共2題，每題14分，共28分）

第1題：

①read(w[i],u[i])

②f[i,j]:=f[i-1,j]

③f[i,j]:=f[i,j-w[i]]+u[i]

④i:=n

⑤j:=xk

⑥inc(get[i])

⑦f[n,xk]

第2題：

①two[i]:=1shli；

②s>=two[b+1](或k>b)

③inc（m[(smodtwo[i])+two[i]]）

④m[(imodtwo[j])+two[j]]+m[i]

⑤max:=m[i]

⑥k:=kdiv2

⑦k=1信息學(xué)競賽初中組初賽模擬試題(四)

及答案

一、選擇題：（每題1.5分，合計30分。每題有5個選項，前10題為單項選擇題，後10題為不定項選擇題，所有選對才得分）。

1.二進制數(shù)11011011的拾進制值是（

）

A.202

B.219

C.193

D.209

2.我國研制的銀河Ⅲ型的超級計算機通過基準(zhǔn)程序的測試，其峰值速度是（

）

A.80億次B.100億次

C.130億次

D.150億次

3.程序段如下：

FORI:=1TO5DO

FORJ:=2TOIDO

Writeln(‘*’)

輸出’*’的個數(shù)是（

）

A.5

B.10

C.15

D.25

E.30

4.設(shè)待排序的記錄為（49，38，65，97，76，13，27,49,55,4），通過下過程將序列排序

第一趟：13,27,49,55,4,49,38,65,97,76

第二趟：13,4,49,38,27,49,55,65,97,76

第三趟：4,13,27,38,49,49,55,65,76,97

問它所用的措施是：(

A.冒泡排序

B.直接選擇排序

C.直接插入排序

D.希爾排序

5.設(shè)無向樹T有7片樹葉，其他頂點度均為3，則T中3度頂點有多少個（

）

A.5

B.7

C.9

D.4

E.8

6.設(shè)連通圖G的頂點數(shù)和邊數(shù)與一立方體相似，即有8個頂點和12條邊。任意一棵G的生成樹的總邊數(shù)為（

）

A．7B.8

C.9

D.10E.11

7.設(shè)有兩個散列函數(shù)h1(k)=kmod13和h2(k)=kmod11

+1，散列表為T[0…12]，用二次散列法處理沖突。函數(shù)h1用來計算散列地址，當(dāng)發(fā)生沖突時，h2作為計算下一種探測地址的地址增量。假定某一時刻散列表的狀態(tài)為：

01

2

3

4

5

6

7

8

9

10

11

12

80

44

35

下一種被插入的關(guān)鍵碼為57，其插入的位置為(

。

A.4

B.5

C.6

D.7

E.8

請根據(jù)下面是一段PASCAL程序,判斷第8、9題。

forh:=1ton-1dobegin

x:=A[h+1];

k:=h;

while(k>=1)and(A[k]>x)dobegin

A[k+1]:=A[k];

k:=k–1

end

A[k+1]:=x

end

8.假設(shè)在程序開始執(zhí)行時，數(shù)組A[1…n]是一組隨機整數(shù)。下列答案中，哪一種最佳的描述了最差狀況下的程序排序的時間復(fù)雜度？（

）

A.O(nlog2n)

B.O(n)

C.O(log2n)

D.O(n2)

E.O(2n)

9.假設(shè)在程序開始執(zhí)行時，數(shù)組A[1…n]是按關(guān)鍵字非遞減有序排列時，下列答案中，哪一種最佳的描述了最佳狀況下的程序排序的時間復(fù)雜度？（

）

A.O(nlog2n)

B.O(n)

C.O(log2n)

D.O(n2)

E.O(2n)

10.對下列四個序列用迅速排序措施進行排序，以序列的第一種元素為劃分的基準(zhǔn)，在第一趟劃分過程中，元素的移動數(shù)最多的是哪一種序列（

）

A.70,65,34,82,53,25,90

B.82,53,25,70,65,34,90

C.34,25,53,65,90,82,70

D.53,25,65,70,34,90,82

E.65,34,82,70,25,53,90

11.在計算機運行時，把程序和數(shù)據(jù)同樣寄存在內(nèi)存中，這是1946年由_______所領(lǐng)導(dǎo)的研究小組正式提出并論證的。（

）

A.圖靈

B.馮·諾依曼

C.布爾

D.赫夫曼

E.哈希

12.下面有關(guān)計算機的說法對的的是（

）

A.微機內(nèi)存容量的基本計量單位是字節(jié)

B.二進制數(shù)中右起第10位上的1相稱于210

C.CPU每執(zhí)行一種指令，就完畢一步基本運算或判斷

D.1T=1024MB

E.32位的計算機中的“32”指的是字長

13.為何說PASCAL是“高級語言”，是由于它（

）

A.必須在性能較高的機器上運行

B.必須通過良好培訓(xùn)的高水平的程序員使用

C.離機器的