2024年信息学竞赛初中组初赛模拟试题

信息學竞赛初中组初赛模拟试題（一）及答案选择題（共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.离机器的