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

）。

A）MS-DOS

B）Linux

C）Java

D）Windos

98

E）Unix2.

按照網絡覆蓋面積和各臺計算機相距的遠近，計算機網絡分為(

)

A)廣域網和局域網B)信息互換網和廣域網

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

)字節.

A)40

B)40*1000

C)40*1024*1024

D)40*1024*1024*1024

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

）。

A)AB-C+D/E*

B)

ABC+D/-E*

C)ABCD/E*+-

D)ABCD/+E*-

E)

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

)。A)SA+13130

B)SA+13129

C)SA+6565

D)SA+6564

E)SA+13128

6.Windows操作系統是一種多任務操作系統,各應用程序之間可以非常以便地通過(

)來互換數據.

A)復制3

B)讀/寫文獻

C)剪貼板

D)剪切

E)粘貼

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

)等表達信息的形式.

A)磁盤、光盤

B)聲音、圖象

C)電纜、光纖

D)聲卡、匯圖儀

E)音箱、顯示屏

8.在數據構造中鏈表是(

).

A)次序存儲的線性表構造

B)

非次序存儲的線性表構造

C)

次序存儲的非線性表構造D)

非次序存儲的非線性表構造E)

特殊的樹構造

9.

計算機輔助教學的簡寫是

(

).

A)CAI

B)CAM

C)CAD

D)CAS

E)CAT

10.給定一種正整數N=，現決定依次刪除其中6個數位上的數字（每次刪除一種數位上的數字），每次刪除後按本來的次序構成一種新數M的值均是目前狀態下的最小數，則第四次應當刪除的數字是(

).

A)6

B)8

C)7

D)4

E)3

11.算法的基本構造有(

).

A)次序

B)選擇

C)判斷

D)循環

E)反復

12.計算機主機由(

)構成.

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.如下是有關計算機病毒的說法，對的的是(

)

A)病毒屬于計算機軟件

B)病毒屬于硬件

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

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

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

15.下列有關拾進制數-100的對的說法是(

).

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

C)反碼為9BH

D)補碼為64H

E)補碼為9CH

16.如下是有關排序的說法對的的是(

).

A)選擇排序、冒泡排序、插入排序是穩定的

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

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

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

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

17．下列是有關數據構造的說法對的的是（

）。

A)數據構造是帶有構造的數據元素的集合B)線性表的線性存儲構造優于鏈式存儲構造

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

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

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

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

).

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

D)111-102-35-21E)

19.有關二叉樹的對的說法是（

）。

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

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

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

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

20.

如下有關圖的對的說法是(

)。

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

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

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

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

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

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

整除？

2.

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

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

三.閱讀程序寫出對的的程序運行成果(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．單源點最短途徑：給定帶權有向圖G=(v,e),源點v1在v中，求v1到v中其他各結點的最短途徑。

數據構造闡明：

cost[I,j]:表達帶權有向圖的鄰接矩陣

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個整數提成k組(k≤n,規定每組不能為空),顯然這k個部分均可得到一種各自的積

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

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

程序闡明:

數組:a[1],a[2],...A[N]寄存原數

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。中綴體現式是對二叉樹-A*+B/CDE的中序遍歷，其後綴體現式，即後序遍歷成果為ABCD/+E*-

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

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

14、ACDE15、ACE16、BCD17、ACD

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

19、BCDE20、ACE

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

1、2662、42

三.閱讀程序寫出對的的程序運行成果(4分*8=32分)

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

2、實際上是求1～50以內的質數，并按規定輸出：

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

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

及答案

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

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

)。

(A)512B

(B)1KB

(C)2KB

(D)4KB

(E)8KB

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

)。

(A)堆排序

(B)希爾排序

(C)冒泡排序

(D)迅速排序

(E)二分排序

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

單元。

(A)1000

(B)10

(C)100

(D)500

(E)300

4.已知數組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

(E)sa+155

5.在pascal語言過程調用時，數值形參得到的是實際參數的(

。

(A)數值

(B)地址

(C)值

(D)變量

(E)以上都不是

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

。

(A)2

(B)

8

(C)

24

(D)

32

(E)

72

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

中。

(A)RAM

(B)ROM

(C)硬盤

(D)寄存器

(E)控制器

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

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

(E)111000

9.設棧S的初始狀態為空,現對序列{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郵件本質上是一種(

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

(E)電訊

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

個結點

(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)}對該圖進行深度優先遍歷,得到的頂點序列對的的是(

(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源程序轉換成可運行的EXE文獻的程序

（B）.把pascal源程序轉換成等價的目的碼的程序

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

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

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

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

）

（A）．

種

（B）．

種

（C）．

種

（D）．種

E.

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

）。

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

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

（C）.采用存儲-轉發方式在網絡上逐漸傳遞信息,不象電話那樣直接、及時,但費用低廉

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

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

）

（A）．主機

（B）.光驅

（C）.聲卡

（D）.音箱

（E）.超級解霸

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

)

(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）信息技術

（D）信息采集

（E）信息存儲

19.在windows中,最小化一種應用程序窗口後，該程序將（

）。

(A)被終止執行

(B)被暫停執行(C)被轉入後臺

(D)繼續執行（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]:在所有三位數中，各位數字從高位到低位順次減小的數共有

個。

[問題2]："銀條"

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

[問題3]:"換不開的現金"

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

答：_________________。

三、寫出程序的運行成果：（每題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.

當程序運行

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

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

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

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

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

第1題

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

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

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型數組a中寄存著從第1屆到第16屆足球世界杯冠軍國家的名字，下面的函數可求出歷界世界杯比賽共有幾種國家曾獲得過世界杯冠軍，請填空完畢。

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（裴波那契）數列的規律是：前2個數均為1，從第3個數開始每個數等于它前面兩個數之和，即：1，1，2，3，5，8，13，21，34，55，89，144，233，377，...。已知任意一種不小于0的整數可以表達為若干個互不相似的fibonacci之數和。

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

下面的程序是由鍵盤輸入一種正整數n，輸出構成n的互不相似的fibonacci數。

例如：若輸入121

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

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

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

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

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、當程序運行

(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信息學競賽初中組初賽模擬試題(三)及答案

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

1、二進制數01100100轉換成拾六進制數是（

）。

A．32

B．64

C．128

D．100

E．256

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

）。

A．Java

B．MS-DOS

C．Linux

D．Windows

E．Unix

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

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

A．編輯文稿

B．讀寫磁盤

C．編程序

D．掃描圖畫

E．打印

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

）。

A．因特網連接

B．因特網使用

C．因特網設計

D．因特網服務提供者

E．信息傳播

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

）。

A．WWW

B．TCP/IP

C．Telnet

D．E-mail

E．FTP

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

）語言書寫的文獻。

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、一棵完全二叉樹的結點總數為18，其葉結點數為（

）。

A．7個

B．8個

C．9個

D．10個

E．11個

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

）。

A．起始框

B．判斷框

C．輸入輸出框

D．處理工作框

E．結速框

10、在處理計算機主機與打印機之間速度不匹配時一般設置一種打印數據緩沖區，重要將要輸出打印的數據依次寫入該緩沖區，而打印機從該緩沖區中取出數據打印。該緩沖區應當是一種（

）構造。

A．堆棧

B．數組

C．線性表

D．隊列

E．鏈表

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

）等多種體現信息的形式。

A．磁盤

B．音箱

C．顯示屏

D．聲音

E．圖像

12、下面有關計算機知識闡明，對的的是（

）。

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

B．FOXMAIL是用于收發電子郵件的工具

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

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

E．為了提高軟件的測試效率，應當選擇發現錯誤的也許性大的測試數據

13、對按關鍵字排序好的線性表進行二分查找，該線性表適合的存儲構造為（

）。

A．鏈接存儲

B．索引存儲

C．散列存儲

D．次序存儲

E．循環存取

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

）。

A．54312

B．24135

C．21543

D．12534

E．12345

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

）。

A．對的性

B．運行時間

C．占用空間

D．迭代次數

E．簡樸性

16、下面描述用多維數組表達的數據構造的語句中，對的的是（

）。

A．多維數組寄存的都是同一種類型的數據

B．多維數組各維的下標范圍必須同樣

C．多維數組在內存中的地址是持續的

D．多維數組中的下標不能是體現式

E．多維數組是隨機存取的數據構造

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

）。

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．以上都不也許出現

18、線性表具有如下的構造特點：（

）

A．均勻性

B．單一性

C．簡樸性

D．無序性

E．有序性

19、下列有關數據構造的論述中對的的是（

）。

A．數據構造是帶有構造的數據元素的集合

B．線性表的線性存儲構造優于鏈式存儲構造

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

D．二維數組是其數據元素為線性表的線性表

E．圖是一種非線性數據構造

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

）。

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

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

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

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

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

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

1、

光明中學開設數學、英語和信息學三個愛好學習小組，其中數學小組30人，英語小組15人，信息學小組18人，參與三個小組總人數為50人，其中有3人同步參與3個小組，那么同步只參與兩個小組的同學有多少人？

2、

給出一組頂點（頂點值用A，B，C，D，E，F表達），其對應權值分別為2，3，1，7，8，4。請以A，B，C，D，E，F為葉子頂點構造一棵哈夫曼樹，并求出它的最小帶權途徑長度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分）

【問題描述】

設有n種物品，每種物品有一種重量及一種價值。但每種物品的數量是無限的，同步有一種背包，最大載重量為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之間，反復出現次數最多的01串。

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

由0，1組合的數列，由‘.’結尾。

輸出：規定的串。

提醒：本程序中將01序列轉換為2進制數存取。

【程序清單】

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信息學競賽初中組初賽模擬試題(四)

及答案

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

1.二進制數11011011的拾進制值是（

）

A.202

B.219

C.193

D.209

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

）

A.80億次B.100億次

C.130億次

D.150億次

3.程序段如下：

FORI:=1TO5DO

FORJ:=2TOIDO

Writeln(‘*’)

輸出’*’的個數是（

）

A.5

B.10

C.15

D.25

E.30

4.設待排序的記錄為（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.設無向樹T有7片樹葉，其他頂點度均為3，則T中3度頂點有多少個（

）

A.5

B.7

C.9

D.4

E.8

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

）

A．7B.8

C.9

D.10E.11

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

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

01

2

3

4

5

6

7

8

9

10

11

12

80

44

35

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

。

A.4

B.5

C.6

D.7

E.8

請根據下面是一段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.假設在程序開始執行時，數組A[1…n]是一組隨機整數。下列答案中，哪一種最佳的描述了最差狀況下的程序排序的時間復雜度？（

）

A.O(nlog2n)

B.O(n)

C.O(log2n)

D.O(n2)

E.O(2n)

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

）

A.O(nlog2n)

B.O(n)

C.O(log2n)

D.O(n2)

E.O(2n)

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

）

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.在計算機運行時，把程序和數據同樣寄存在內存中，這是1946年由_______所領導的研究小組正式提出并論證的。（

）

A.圖靈

B.馮·諾依曼

C.布爾

D.赫夫曼

E.哈希

12.下面有關計算機的說法對的的是（

）

A.微機內存容量的基本計量單位是字節

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

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

D.1T=1024MB

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

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

）

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

B.必須通過良好培訓的高水平的程序員使用

C.離機器的