第24届2009年中小学生计算机程序设计竞赛 小学组 含答案

2009年宁波市第24届中小学生计算机程序设计竞赛

小学组初赛试题

（说明：答案请写在答题卷上。考试时间120分钟，满分100分）

一、选择题（每题有且仅有一个正确答案，选对得1.5分，选错、不选或多选均不得分）

1、若已知一个栈的入栈顺序是1，2，3， ，n，其输出序列为P1，P2，P3， ，Pn，若P1是n，则Pi是( )

A)i B)n-1 C)n-i+1 D)不确定

2、满二叉树的叶结点个数为N，则它的结点总数为（ ）。 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1

3、 二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为（ ）。

A. 4 2 5 7 6 3 1 B. 4 2 7 5 6 3 1 C. 4 2 7 5 3 6 1 D. 4 7 2 3 5 6 1 E. 4 5 2 6 3 7 1

4、完全二叉树的结点个数为11，则它的叶结点个数为（ ）。 A. 4 B.3 C.5 D. 2 E. 6

5、布尔型(boolean)和字符型(char)变量所占用的存储空间大小的关系是

（A）布尔型大 （B）字符型大 （C）一样大 （D）因操作系统而异 6、用八位二进制可以表示的最大十进制数是：

（A）99999999 （B）11111111 （C）255 （D）256

7、有一个10行10列的对称矩阵，采用压缩存储方式来存储该矩阵的上三角元素（行优先次序），第1行第1列的存储地址为s，每个元素占用2个存储空间，则第8行第8列元素的首地址为： （A）s+100 （B）s+98 （C）s+72 （D）s+70

8、已知一棵二叉树的叶子结点数为100，则有二个子女的结点数为： （A） 101 （B） 100 （C） 99 （D） 不能确定

9、已知一棵二叉树的前序遍历为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则这棵二叉树的深度为： （A） 6 （B）5 （C）4 （D）3

10、在Pascal语言中，表达式 （23 or 2 xor 5）的值是（ ）。 A．18 B．1 C．23 D．32

11、将数组{ 1, 2, 4, 3, 5, 6, 7, 8 }中的元素用插入排序的方法按从大到小的顺序排列，需要比较的次数是：

（A）7（B）27（C）28（D）64

12、算式(2009)16-(2008)10+(2007)8的结果是：

（A）(16170)8 （B）(7234)10 （C）(1C36)16 （D）(1110000111000)2

13、计算机内部使用的数是：

（A）二进制数 （B） 八进制数 （C） 十进制数 （D） 十六进制数

14、当n大于100万时,下列程序段哪个运行最快

15、当原始待排序数据为从小到大排列时，运行时间比原始数据为乱序时快的算法是： （A）选择排序 （B）归并排序 （C）插入排序 （D）快速排序

16、关于算法的下列叙述不正确的是：

（A）算法的每一步必须没有歧义，不能有半点含糊 （B）算法必须有输入

（C）同一问题可能存在多种不同的算法

（D）同一算法可以用多种不同的形式来描述

17、FOR语句中的循环变量，其类型必须是：

（A）整型 （B）实型 （C）自定义类型 （D）有序类型

18、在下面各奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是：

（A）沃尔夫奖 （B）图灵奖 （C）诺贝尔奖 （D）菲尔兹奖

19、栈是一种后进先出的数据结构，它有压入（push）和弹出（pop）两种操作。二个元素AB通过入栈和出栈操作，可以有AB和BA两种可能。现在3个元素ABC依次进栈，出栈序列最终有几种可能？

（A）3 （B）4 （C）5 （D）6

20、以下哪项不属于计算机程序设计竞赛

（A）NOIP （B）电子作品制作

（C）ACM大学生程序设计竞赛 （D）宁波市中小学生程序设计竞赛

二．问题求解（每小题5分，共10分）

1、已知a, b, c, d, e, f, g七个人中，a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲汉语和日语；e会讲意大利语和德语；f会讲俄语、日语和法语；g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？如果可以，请以“a b”开头写出你的安排方案： _____________ 。

2、某班有30个同学报名参加100米、400米、800米三项比赛，已知有15人报了100米，8人报了400米，6人报了800米，且其中有3人这三个项目都报了。问该班最少有______人一项都没有报过？最多有_____人一项都没有报过？

三、阅读程序写结果（每题8分，共32分）

1、program nbxx09_1;

var a,b,s:longint; begin

readln(a); s:=a; b:=0;

while a<>0 do begin b:=b*10+a mod 10; a:=a div 10; end; s:=s+b; writeln(s); end.

输入：123456789 输出：

2、program nbXX09_2;

var u:array[0..3]of integer; a,b,c,x,y,z:integer; begin read(u[0],u[1],u[2],u[3]); a:=u[0]+u[1]+u[2]+u[3]-5; b:=u[0]*(u[1]-u[2]div u[3]+8); c:=u[0]*u[1] div u[2]*u[3]; x:=(a+b+2)*3-u[(c+3)mod 4]; y:=(c*100-13)div a div(u[b mod 3]*5);

z:=(a+b+c-x-y)*2; if((x+y)mod 2=0)then z:=(a+b+c+x+y)div 2; writeln(x+y-z); end.

输入：2 5 7 4 输出：

3、program nbXX09_3;

var a,work:array[1..100] of integer; i,j,x,d,max:integer; begin

readln(max);

for i:=1 to max do begin read(a[i]); work[i]:=a[i]; end;

d:=max div 2;

while d>=1 do begin

for i:=d+1 to max do begin x:=work[i]; j:=i-d;

while (j>0) and (x<work[j]) do begin work[j+d]:=work[j]; dec(j,d); end;

work[j+d]:=x; end;

d:=d div 2; end;

for i:= max downto 1 do

if a[i]=work[i] then write('1') else write('0'); writeln; end. 输入：8

输出： ______

71 88 149 32 66 90 144 99

4、program nbXX09_4;

var p:array[1..10000]of longint; n,i,x:longint;

function find(x:longint):longint; begin

if p[x]=x then find:=x else begin

p[x]:=find(p[x]);

find:=p[x]; end; end;

begin

readln(n,x);

for i:=1 to n do read(p[i]); writeln(find(x));

for i:=1 to n-1 do write(p[i],' '); //两数之间输出一个空格 writeln(p[n]); end.

输入：5 5 3 3 3 2 4

输出： ______ _______________________

四．程序填空（前5空，每空2分，后6空，每空3分，共28分）

1、“高效”排序

以下程序实现输入n个数，使用类似冒泡排序的方法，依次比较相邻的两个数，如果前一个数比后一个大，则交换两者，最终将输入的n个数从小到大排序后输出。程序在运行中发现某遍扫描后，没有数据交换发生，说明已经有序了，此时将退出扫描。请将程序补充完整。

program nbcz09_5; var n,i,j,tmp:longint;

a:array[1..10000]of longint;

flag:boolean; //flag=true表示有交换发生，flag=false表示没有交换

begin

readln(n);

for i:=1 to n do read(a[i]); i:=1;

①__________________;

while flag and (i<=n-1) do begin flag:=false;

for j:=1 to ②_____________ do

if a[j]>a[j+1] then begin //前一个比后一个大 tmp:=a[j];

③ a[j+1]:=tmp;

④______________; end;

⑤_______________;

end;

for i:=1 to n-1 do write(a[i],' '); writeln(a[n]);