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

信息学竞赛初中组初赛模拟试题（一）及答案

选择题（共20题，每题1.5分，共计30分。每题有5个备选答案，前10个题为单选题，即每题有且只有一个正确答案，选对得分；后10题为不定项选择题，即每题有1至5个正确答案，只有全部选对才得分）

1.操作系统是一类重要的系统软件，下面几个软件不属于系统软件的是（ ）。

A）MS-DOS B）Linux C）Java D）Windos 98 E）Unix

2. 按照网络覆盖面积和各台计算机相距的远近，计算机网络分为( ) 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*1000 4．中缀表达式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=8934632178，现决定依次删除其中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)原码为11100100B B)反码为E4H C)反码为9BH D)补码为64H E)补码为9CH 16.以下是关于排序的说法正确的是( ).

1

A)选择排序、冒泡排序、插入排序是稳定的

B)希尔排序、快速排序、堆排序的时间复杂度为O(nlog2n) C)线形排序的时间复杂性为O(n)

D)线形排序、二路归并排序的空间复杂度为O(n)

E)希尔排序、快速排序、堆排序、归并排序是不稳定的 17．下列是关于数据结构的说法正确的是（ ）。

A)数据结构是带有结构的数据元素的集合 B)线性表的线性存储结构优于链式存储结构 C)队列是一个先进先出的线性表 D)队列是只能在一端插入，另一端删除的线性表 E)栈的插入和删除只能在栈底进行 8.下列IP地址中错误的是( ).

A)202.300.12.4 B)192.168.0.3 C)100:128:35:91 D)111-102-35-21 E)19.255.0.1 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,3 1,3,2 2,1,3 2,3,1 3,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.

输入:20100 输出:

2.program t2;

2

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

3

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中，求 的最短路径。 数据结构说明：

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

v1到v中其余各结点4

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个部分均可得到一个各自的积

5

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.

6

初赛模拟试题（一）答案 一、选择题（共20题，每题1.5分，共计30分） 1、C 2、A 3、D

4、D。中缀表达式是对二叉树-A*+B/CDE的中序遍历，其后缀表达式， 即后序遍历结果为ABCD/+E*-

5、B。数组元素A[66,65]存储的起始地址是SA+13128，而结束地址则 是SA+13130-1 6、C 7、B 8、B 9、A 10、D 11、ABD 12、ABD 13、ACDE 14、ACDE 15、ACE 16、BCD 17、ACD

18、ACD。IP地址是由4个10进制数组成，每个数都在0～255之间，且彼此用.分隔。 19、BCDE 20、ACE

二.问题求解（5分*2=10分） 1、266 2、42

三.阅读程序写出正确的程序运行结果(4分*8=32分) 1、200。b=(1+a)*a/2，即b>=20100??

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

7

信息学竞赛初中组初赛模拟试题(二) 及答案

一、选择题：（共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)1011010001 (B) 10110100011 (C) 11101010001 (D) 11110100011 (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）.比邮政信函，电报，电话，传真都更快

8

（B）.在通信双方的计算机之间建立其直接的通信线路后即可快速传递数字信息

（C）.采用存储-转发方式在网络上逐步传递信息,不象电话那样直接、及时,但费用低廉 （D）.在通信双方的计算机都开机工作的情况下即可快速传递数字信息 16. 以下属于多媒体硬件的是（ ）

（A）．主机 （B）.光驱 （C）.声卡 （D）. 音箱 （E）. 超级解霸 17. 正确的二维数组类型说明是( )

(A) type ar2=array[1..5,5..1] of integer;

(B) type ar2=array[1..5] of array[5.1] of integer; (C) type ar2=array[1..5,1..5] of integer;

(D)type ar2=array[1..5] of array[1..5] of integer (E)type ar2=array[1..5,1..5] of 0..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 = 1 OR 2 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. program text1; const n=6;m=3; var i,j,k:integer; begin

for i:=-n to n do begin

k:=n-abs(i);

write(' ': 39-k); for j:=-k to k do if abs(j)>k-m

9

then write(n-(i+n)div 2) else write(' '); writeln; end; end.

输出的结果为： 2. PROGAM text2；

VAR a:ARRAY[1..10] OF Char； k:Integer； ch:Char； BEGIN

FOR k:=1 TO 10 DO a[k]:=Chr(Ord('A')+k)； FOR k:=1 TO 10 DO BEGIN

ch:=a[k]；

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

FOR k:=1 TO 10 DO Write(a[k])； Writeln END.

输出的结果为：

3. program text3(input,output); Var m,n,p:integer; x:real;

procedure mm(var m:integer;x:real); var n: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. program text4; const n=5;

type ary=array[0..n-1,0..n-1]of integer; var a:ary;i,j,k:integer; begin

for i:=0 to n-1 do

10

for j:=0 to n-1 do a[i,j]:=0; k:=1;

for i:=1 to n do

for j:=n-1 downto i do begin

a[j,j-i]:=k; k:=k+1; end;

for i:=0 to n-1 do begin

for j:=0 to n-1 do write(a[I,j]:4); writeln; end; end.

输出的结果为：

5.program text5(input,output); var ch:char; i,n,sum:integer; begin sum:=0; read(ch); case ch of

'A':for i:=4 to 6 do begin

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

'B'：begin read(n);

for i:=1 to n do

begin read(n);sum:=sum＋n end; end; 'C':repeat

read(n);sum:=sum＋n until sum>10; 'D':begin read(n); while n<=3 do

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

end; writeln(sum:4) end.

当程序运行

(1) 输入 A 4 1 2 3 4 5 6 7 8 9时，其输出为_____________。 (2) 输入 B 4 1 2 3 4 5 6 7 8 9时，其输出为_____________。 11

(3) 输入 C 4 1 2 3 4 5 6 7 8 9时，其输出为_____________。 (4) 输入 D 4 1 2 3 4 5 6 7 8 9时，其输出为_____________。 四、完善程序（第1题每空2分第2、3题每空3分，共32分） 第1题

孪生素数是指两个相差为2的素数，例如：3和5，5和7，11和13等。 下面程序可输出15对孪生素数，其中函数q判断整数a是否为素数。 program p(output); var k,n:integer

q (a:integer):booklean; var k:integer; flag:boolean; begin

flag:___(1)____ k:=2

___(2)____ (k<=a div 2) and flag do if a mod k=0 then ______(3)_______ else k:=k+1 q:=flag end; begin n:=0; k:=2; repeat

if q(k) and ___(4)___ then begin n:=n+1;

writeln(k,k+2) end; k:=K+1 until n=5 end.

第二题

已知有类型arr=array[1..16] of string;

arr型数组a中存放着从第1届到第16届足球世界杯冠军国家的名字，下面的函数可求出历界世界杯比赛共有几个国家曾获得过世界杯冠军，请填空完成。 text2(a:arr):integer; var k,j,s:integer; mult:boolean; begin

___(5)___;

for j:=2 to 16 do begin

12

k:=1;

mult:=false;

while not mult and ___(6)___ do if ___(7)__ then mult:=ture else k:=k+1;

if not mult then s:=___(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数。 program text3(input,output); var n:integer;

find(n:integer):integer; var a,b,c:integer; begin

a:=1; b:=1; repeat

c:=___(9)___; a:=b;b:=c; until b>=n;

if b=n then find:=___(10)___ else find:=___(11)___ end;

procedure p(n:integer); var a:integer; begin

a:=find(n); write('+',a:4); if a

13

begin

readln(n);

write(n:5,'='); p(n); writeln end.

初赛模拟试题（二）参考答案

一、选择题：（本题共20小题，1-15小题为单选题，每题1分；16-20小题为多选题，每题2分。共25分）

题号 1 2 3 4 5 6 7 8 9 10 答案 B D B A B E B C B A

题号 11 12 13 14 15 答案 B D B C C

题号 16 17 18 19 20 答案 ABCD CE ABDE CD AE

二、问题求解：（第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 6 6 6 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1

14

1 1 1 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) 输入 A 4 (2) 输入 B 4 (3) 输入 C 4 (4) 输入 D 4

1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9时，其输出为______7_____。 9时，其输出为______10____。 9时，其输出为_______14___。 9时，其输出为________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

（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题，

15

每题1.5，共30分）

1、二进制数01100100转换成十六进制数是（ ）。 A．32 B．64 C．128 D．100 E．256 2、操作系统是一类重要的系统软件，下面几个软件中，不属于系统软件的是（ ）。 A．Java B．MS-DOS C．Linux D．Windows2000 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

16

15、评价一个算法的好坏有多种指标，下列是算法评价指标的是（ ）。

A． 正确性 B．运行时间 C．占用空间 D．迭代次数 E．简单性 16、下面描述用多维数组表示的数据结构的语句中，正确的是（ ）。 A． 多维数组存放的都是同一种类型的数据 B． 多维数组各维的下标范围必须一样 C． 多维数组在内存中的地址是连续的 D． 多维数组中的下标不能是表达式 E． 多维数组是随机存取的数据结构

17、若已知一个栈的入栈顺序1，2，3，?，n，其输出序列为P1，P2，P3，?，Pn（它是输入序列的一个排列），则在输出序列中可能出现的情况是（ ）。

A．Pj

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题：

17

program test1； var n：integer；

count(n：integer)：integer； begin

if n=1 then count：=0 else

if n mod 2=0 then count：=count(n div 2)+1 else count：=count(n*3+1)+1； end； begin

readln(n)；

writeln(count(n))； end. 输入：99 输出： 第2题：

program test2(input,output); var

i,j,k,s:integer; begin s:=0

for i:=3 downto 1 do begin

for j:=1 to 3 do begin k:=0; repeat

k:=k+1;s:=s+k; until k=j; end;

s:=s-(k+1); end;

write(‘s=’,s); end. 输出： 第3题：

program test3; var a,b,n:longint; begin

readln(n); a:=0;b:=0; repeat

a:=a+1;b:=b+a; until b>=n;

18

writeln(a); end.

输入：415377 输出：

program test4;

var m,n,i,p,k：integer; r:array[1?200] of integer; b:Boolean; begin

m:=6;n:=2;

for I:=1 to m-1 do r[i]:=i+1; r[m]:=1;i:=0;p:=1;b:=true; while b do begin

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

begin writeln(p);b:=false end else if i=n+1 then begin

write(p,‘ ’);i:=0;p:=r[p];r[k]:=p; end end end. 输出：

四、完善程序（共2题，每题14分，共28分） 第1题（7分） 【问题描述】

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为XK，今从n种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于XK，而价值的和为最大。 【程序清单】 Program package;

const maxxk=400;maxn=20;

type tlist=array[1?maxn] of byte;

tmake=array[0?maxn,0?maxxk] of integer; var n,xk:integer; w,u:tlist; f:tmake; procedure init; var i:byte; begin

fillchar(w,sizeof(w),0); fillchar(u,sizeof(u),0); readln(n,xk);

19

for i:=1 to n do

① ; end;

procedure make; var i,j:byte; begin

for i:=1 to n do begin

for j:=1 to w[i]-1 do f[i,j]:=f[i-1,j]; for j:=w[i] to xk do

if f[i-1,j]>f[i,j-w[i]]+u[i] then ② ; else ③ ; end; end;

procedure print; var get:tlist; i,j:byte; begin

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

i:= ④ ;j:= ⑤ ; while i>0 do

if f[i,j]=f[i-1,j] then dec(i) else begin

dec(j,w[i]);

⑥ ; end;

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

writeln(‘max worth=’, ⑦ ; for i:=1 to n do

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

由0，1组合的数列，由‘.’结尾。

20

输出：要求的串。

提示：本程序中将01序列转换为2进制数存取。 【程序清单】

program shuchuan;

var i,j,s,k,a,b,max:integer; m:array[1?8192] of integer; two,v:array[1?20] of integer; c:char; begin

for i:=1 to 13 do ① ; readln(a,b); read(c); s:=1;k:=1;

while c<>‘.’do begin s:=s shl 1+ord(c)-48; if ② then

s:=((s-two[b+1]) mod two[b])+two[b]; inc(m[s]); if k

for i:=a to k-1 do ③ ; inc(k); read(c); end;

for i:=two[b] to two[b+1] do if m[i]>0 then

for j:=a to b-1 do

m[(i mod two[j])+two[j]]:= ④ ; max:=0;

for i:=two[a] to two[b+1] do

if m[i]>max then ⑤ ; for i:=two[a] to two[b+1] do if m[i]=max then begin j:=0;k:=I; repeat

inc(j);v[j]:=k mod 2; ⑥ ; until ⑦ ;

while j>0 do begin write(v[j]);dec(j) end; writeln; end; end.

初赛模拟题(三)参考答案

21

一、选择题：（选出每题正确的答案代码，填在括号里，1—10题为单选题，每小题只有一个正确答案，11—20题为不定项选择题，每小题有一个或一个以上的正确答案，共20题，每题1.5，共30分）

题号 1 2 3 4 5 6 7 8 9 10 答案 B A B D C B E C B D

题号 11 12 13 14 15 16 17 18 19 20 答案 DE BCE D CE ABCE ACE BCD AE ACDE A 二、问题解答：（共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]:=1 shl i； ②s>=two[b+1](或k>b)

③inc（m[(s mod two[i])+two[i]]） ④m[(i mod two[j])+two[j]]+m[i] ⑤max:=m[i] ⑥k:=k div 2 ⑦k=1

信息学竞赛初中组初赛模拟试题(四) 及答案

一、选择题：（每题1.5分，共计30分。每题有5个选项，前10题为单选题，后10题为不定项选择题，全部选对才得分）。

22

1. 二进制数11011011的十进制值是（ ） A. 202 B. 219 C. 193 D. 209

2. 我国研制的银河Ⅲ型的超级计算机通过基准程序的测试，其峰值速度是（ ） A. 80亿次 B. 100亿次 C. 130亿次 D. 150亿次 3. 程序段如下： FOR I:=1 TO 5 DO

FOR J:=2 TO I DO 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．7 B. 8 C. 9 D. 10 E. 11

7. 设有两个散列函数h1(k)=k mod 13 和 h2(k)=k mod 11

+1，散列表为T[0?12]，用二次散列法解决冲突。函数h1用来计算散列地址，当发生冲突时，h2作为计算下一个探测地址的地址增量。假定某一时刻散列表的状态为： 0 1 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题。 for h :=1 to n-1 do begin x :=A[h+1]; k :=h;

while (k>=1) and (A[k]>x) do begin A[k+1] :=A[k]; k:=k–1 end

A[k+1] :=x end

8. 假设在程序开始执行时，数组A[1?n]是一组随机整数。下列答案中，哪一个最好的描述了最差情况下的程序排序的时间复杂度？（ ）

A. O(n log2 n) B. O(n) C. O(log2n) D. O(n2) E. O(2n)

9. 假设在程序开始执行时，数组A[1?n]是按关键字非递减有序排列时，下列答案中，哪一个最好的描述了最好情况下的程序排序的时间复杂度？（ ）

23

A. O(n log2 n) 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. 离机器的硬件较远 D. 开发的时间较长 E. 程序的性能较好

14.以下数据结构中，哪一个是线性结构？（ ）

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 15.在下面关于计算机系统硬件的说法中不正确的是( A. 没有外部设备的计算机称为祼机

B. 当关闭计算机电源后，RAM中的程序和数据就消失了 C. 软盘和硬盘上的数据均可由 CPU直接存取

D. 软盘和硬盘驱动器既属于输入设备又属于输出设备 E. CPU主要由运算器、控制器和寄存器组成 16. 下面关于算法的正确说法是（ ） A. 算法必须有输出

B. 算法必须在计算机上用某种语言实现 C. 算法不一定有输入

D. 算法必须在有限步执行后能结束 E. 算法是程序的灵魂

17.以下关于结构化程序的说法中，正确的是（ ） A. 结构化程序是由单入口，单出口和循环三种结构组成 B. 结构化程序是出顺序、单入中和单出口三种结构组成

E. 队列 24

C. 结构化程序是由顺序、循环和GOTO语句结构组成 D. 结构化程序是由顺序、循环和分支三种结构组成

E. “自顶向下，逐步求精”是结构化程序设计方法的特点

18.栈S最多能容纳4个元素。现有6个元素按1，2，3，4，5，6的顺序进栈，问下列哪一个序列是可能的出栈序列？（ ） A. 5，4，3，2，1，6 B. 3, 2, 5, 4, 1, 6 C. 2, 3, 5, 6, 1, 4 D. 1, 4, 6, 5, 2, 3 E. 4，5，3，6，2，1

19.下列排序算法中，哪些排序是不稳定的（ ） A．快速排序 B. 基数排序 C. 希尔排序 D. 冒泡排序 E.选择排序 20.下列说法正确的是（ ）

A. 解释程序是接受参数，按照某一样板产生机器语言的计算机程序 B. BASIC语言程序通常需解释执行

C. 连接程序可以把经编译程序产生的目标程序变成可执行的机器语言程序 D. 就执行速度而言，编译程序比解释程序快 E. PASCAL通常是先编译后执行

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

1. 由四个结点可以构造多少种不同的二叉树 .

2. 下图是一个设想有11项活动的活动网。其中有9个事件V1，V2，?

V9,每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。V1表示整个工程的开始，V9表示结束，与每个活动相联系的数ax(x=1?11)是执行该活动所需的时间（单位：天）。问完成整项工程至少需要

天，影响工程进度的关键活动有哪些： 。

V2 V7

V1 V5 V9

V3 V8

25