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

1、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 13、二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3

2、 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 14、完全二叉树的结点个数为11，则它的叶结点个数为（ ）。A. 4 B.3 C.5 D. 2 E. 65、布尔型(boolean)和字符型(char)变量所占用的存储空间大小的关系是（A）布尔型大 （B）字符型大 （C）一样大 （D）因操作系统而异6、用八位二进制可以表示的最大十进制数是：（A）99999999 （B）11111111 （C）255 （D）2567、有一个10行10列的对称矩阵，采

3、用压缩存储方式来存储该矩阵的上三角元素（行优先次序），第1行第1列的存储地址为s，每个元素占用2个存储空间，则第8行第8列元素的首地址为： （A）s+100 （B）s+98 （C）s+72 （D）s+708、已知一棵二叉树的叶子结点数为100，则有二个子女的结点数为：（A） 101 （B） 100 （C） 99 （D） 不能确定9、已知一棵二叉树的前序遍历为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则这棵二叉树的深度为： （A） 6 （B）5 （C）4 （D）310、在Pascal语言中，表达式 （23 or 2 xor 5）的值是（ ）。A18 B1 C23 D3211、将数

4、组 1, 2, 4, 3, 5, 6, 7, 8 中的元素用插入排序的方法按从大到小的顺序排列，需要比较的次数是：（A）7（B）27（C）28（D）6412、算式(2009)16-(2008)10+(2007)8的结果是：（A）(16170)8 （B）(7234)10 （C）(1C36)16 （D）(1110000111000)213、计算机内部使用的数是：（A）二进制数      （B） 八进制数 （C） 十进制数     （D） 十六进制数14、当n大于100万时,下列程序段哪个运行最快（D）k:=1;j:=n

5、;x:=a1;while k<j do begin while (k<j)and(aj>x)do dec(j); if k<j then begin ak:=aj;inc(k);end; while (k<j)and(ak<x)do inc(k); if k<j then begin aj:=ak;dec(j);end;end;（C）sum:=0;k:=1;while k<=n do begin for j:= 1 to n do sum:=sum+1; k:=k*2;end;（B）sum:=0;k:=1;while k<=n do beg

6、in for j:= 1 to k do sum:=sum+1; k:=k+2;end;（A）max:=0;for k:=1 to n-1 do for j:=k+1 to n do if max<abs(ak-aj) then max:=abs(ak-aj) 15、当原始待排序数据为从小到大排列时，运行时间比原始数据为乱序时快的算法是： （A）选择排序 （B）归并排序 （C）插入排序 （D）快速排序 16、关于算法的下列叙述不正确的是：（A）算法的每一步必须没有歧义，不能有半点含糊（B）算法必须有输入（C）同一问题可能存在多种不同的算法（D）同一算法可以用多种不同的形式来描述17、FO

7、R语句中的循环变量，其类型必须是：（A）整型 （B）实型 （C）自定义类型 （D）有序类型18、在下面各奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是：（A）沃尔夫奖 （B）图灵奖 （C）诺贝尔奖 （D）菲尔兹奖19、栈是一种后进先出的数据结构，它有压入（push）和弹出（pop）两种操作。二个元素AB通过入栈和出栈操作，可以有AB和BA两种可能。现在3个元素ABC依次进栈，出栈序列最终有几种可能？（A）3 （B）4 （C）5 （D）620、以下哪项不属于计算机程序设计竞赛（A）NOIP （B）电子作品制作 （C）ACM大学生程序设计竞赛 （D）宁波市中小学生程序设计竞赛二问题

8、求解（每小题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、

9、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;varu:array0.3of integer;a,b,c,x,y,z:integer;beginread(u0,u1,u2,u3);a:=u0+u1+u2+u3-5; b:=u0*(u1-u2div u3+8);c:=u0*u1

10、 div u2*u3;x:=(a+b+2)*3-u(c+3)mod 4;y:=(c*100-13)div a div(ub 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:array1.100 of integer; i,j,x,d,max:integer;begin readln(max); for i:=1 to max do begin read(ai); worki:=ai;

11、 end; d:=max div 2; while d>=1 do begin for i:=d+1 to max do begin x:=worki; j:=i-d; while (j>0) and (x<workj) do begin workj+d:=workj; dec(j,d); end; workj+d:=x; end; d:=d div 2; end; for i:= max downto 1 do if ai=worki then write('1') else write('0'); writeln;end.输出： _ 输入：

12、871 88 149 32 66 90 144 994、program nbXX09_4;var p:array1.10000of longint; n,i,x:longint;function find(x:longint):longint;begin if px=x then find:=x else begin px:=find(px); find:=px; end;end;begin readln(n,x); for i:=1 to n do read(pi); writeln(find(x); for i:=1 to n-1 do write(pi,' '); /两数

13、之间输出一个空格 writeln(pn);输出： _ _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:array1.10000of longint; flag:boolean; /flag=true表示有交换

14、发生，flag=false表示没有交换begin readln(n); for i:=1 to n do read(ai); i:=1; _; while flag and (i<=n-1) do begin flag:=false; for j:=1 to _ do if aj>aj+1 then begin /前一个比后一个大 tmp:=aj; _ _; aj+1:=tmp; _; end; _; end; for i:=1 to n-1 do write(ai,' '); writeln(an);end.2、数独游戏在n行n列的方格中，每个格子填入一个1n之间

15、的数字，使得每行中没有重复数字，每列上也没有重复数字。如图1所示是一个3行3列的合法的安排方案。12图41221图311图21223图131312游戏开始可以规定某些格子已经有给定的数字。如图2所示，在2行2列的方格中，规定1行1列和2行2列的数字均为1，则得到唯一的如图3所示的方案。但如果规定1行1列数字为1，2行2列数字为2，则无法得到任何合法的方案（如图4所示）下面的程序求9行9列的一个安排方案，程序首先读入若干个已知格子上的数字，找到一个合理的安排方案后输出。如果没有任何合法方案，则输出“No Solution!”(注意引号不用输出)。程序填充格子的次序依次为：1行1列、1行2列、1行

16、9列、2行1列、2行2列、2行9列、9行1列、9行2列、9行9列。请你将空白处的程序补充完整。program nbxx09_6;var h:array1.9,1.9of boolean;/hi,j表示数字j是否出现在第i行 v:array1.9,1.9of boolean; /vi,j表示数字j是否出现在第i列 change:array1.9,1.9of boolean;/changei,j表示第i行第j列是否为规定的数字 a:array1.9,1.9of integer;/保存方案 i,j,k,n,x:integer;procedure print;/输出找到的方案var i,j:integ

17、er;begin for i:=1 to 9 do begin for j:=1 to 8 do write(ai,j,' '); writeln(_); end;end;procedure search(i,j:integer); /从i行j列开始填充var k:integer;begin if (_) then begin print; halt; /结束程序 end; if changei,j then begin for k:=1 to 9 do if (not hi,k) and(not vj,k) then begin hi,k:=true; vj,k:=true;

18、 _; if j<9 then search(i,j+1) else search(_); hi,k:=false; vj,k:=false; end end else begin if j<9 then search(i,j+1) else search(_); end;end;begin for i:=1 to 9 do for j:=1 to 9 do begin hi,j:=false; /第i行没有数字j出现 vi,j:=false; /第i列没有数字j出现 ai,j:=0; /第i行第j列没有数字填入 changei,j:=true; /第i行第j列允许填充(没有给定的输入数字) end; readln(n); for k:=1 to n do begin readln(i,j,x); ai,j:=x; /第i行第j列给定的数字为x hi,x:=true; /第i行出现数字x vj,x:=true; /第j列出现数字x changei,j:=false; /第i行第j列不允许填充(已有给定的输入数字) end; search(_); writeln(_);