宁波市第24届中小学生计算机程序设计竞赛初赛试题（小学组）.doc

《宁波市第24届中小学生计算机程序设计竞赛初赛试题（小学组）.doc》由会员分享，可在线阅读，更多相关《宁波市第24届中小学生计算机程序设计竞赛初赛试题（小学组）.doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 更多试题请登陆2009年宁波市第24届中小学生计算机程序设计竞赛一、选择题（1.5每题）1、以下不属于程序的基本结构的是：顺序结构选择分支结构循环结构树形结构2、由2个a，2个b和2个c构成的所有字符串中，包含子串“abc”的共有（ ）个。20816243、假设A=TRUE,B=TRUE ,C=TRUE, D=FALSE，逻辑运算表达式A and B or C and D 的值是： false true014、下列数种最大的数是（ ） （11111）2（F）16（30）10（35）85、布尔型（boolean）和字符型（char）变量所占用的存储的空间大小关系是（ ） 布尔型大字符型大一样大

2、因操作系统而异6、用八位二进制可以表示的最大二进制数是：（ ） 99999999111111112552657、有一个10行10列的对称矩阵，采用压缩存储方式来存储该矩阵的上三角元素（行优先次序），第1行第1列的存储地址为s，每个元素占用2个存储空间，则第8行第8列元素的首地址为：（ ） s+100s+98s+72s+708、已知一棵二叉树的前序遍历为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则这棵二叉树的深度为： 65439、已知一棵二叉树的叶子节点数为100，在有二个子女的结点数为： 10110099不能确定10、算术表达式（3a+1）5在程序设计中表达为 (3a+1)/5

3、(3*a+1)5(3*a+1)/511、将数组 1、2、4、3、5、6、7、8 中的元素用插入排序的方法从大到小的顺序排列，需要比较的次数是： 727286412、算式（2009）16-（2008）10-（2007）8 的结果是：（ ） （16170）8(7234)10(1C36)16(1110000111000)213、计算机内部使用的数是： 二进制数八进制数十进制数十六进制数14、当n大于100万时，下列程序段哪个运行最快：(A). max:=0;for k:=1 to n-1 do for j:=k+1 to n do if maxabs(ak-aj) then max:=abs(ak-

4、aj)(B). sum:=0; k:=1;while k=n do begin for j:=1 to k do sum:=sum+1; k:=k+2;end;(C). sum:=0; k:=1;while k=n do begin for j:=1 to n do sum:=sum+1;k:=k*2; end;(D). k:=1; j:=n; x:=a1;while kj do begin while (kx) do dec(j); if kj then begin ak:=aj; inc(k); end; while (kj)and(akx) do inc(k); if kj then b

5、egin aj:=ak; dec(j); end;end;15、当原始待排序数据为从小到大排列时，运行时间比原来数据为乱序时快的算法是：选择排序归并排序插入排序快速排序16、关于算法的下列叙述不正确的是：A、算法的每一步必须没有歧义，不能有半点含糊B、算法必须有输入C、同一问题可能存在多种不同的算法D、同一算法可以用多种不同的形式来描述17、for语句中的循环变量，其类型必须是： A、整型B、实型C、自定义类型 D 有序类型18、下列各种奖项中，为计算机领域作出杰出贡献的科学家设立的奖项是： A 沃尔夫奖B 图灵奖C 诺贝尔奖D 菲尔兹奖19、栈是一种后进先出的数据结构，他有压入（push）和

6、弹出（pop）两种操作。二个元素AB通过入栈和出栈操作，可以有AB和BA两种可能。现在3个元素ABC依次进栈、出栈序列最终有几种可能（ ） A 3B 4C 5D 620、以下哪项不属于计算机程序设计竞赛（ ） A NOIP B 电子作品制作 C ACM大学生程序设计赛 D 宁波市中小学生程序设计竞赛二、问题求解（每小题5分）1、已知a,b,c,d,e,f,g七个人中，a会讲英语和汉语，c会讲英语、意大利语和俄语，d会讲汉语和日语， e会讲意大利语和德语， f会讲俄语、日语和法语， g会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他的身边人交谈，如果可以，请以“a b”开头写出你

7、的安排方案： a d f g e c b 2、某班有30个同学报名参加100米、400米、800米三项比赛，已知有15人报了100米，8人报了400米，6人报了800米，其中有3人这三个项目都报了，问该班最少有 人一项都没有报过？最多有 人一项都没有报过？三、阅读程序写结果（每题8分，共32分）program nbxx09_1;var a,b,s:longint; begin readln(a); s:=a; b:=0; while ab do begin b:=b*10+a mod 10; a:=a div 10; end; s:=s+b; writeln(s);end;输入：1234567

8、89 输出： program nbxx09_2;var u:array0.3 of integer; a,b,c,x,y,z:integer;begin read(u0,u1,u2,u3); a:=u0+ u1+ u2+ u3-5; b:=u0*(u1-u2 div u3+8); c:= u0*u1 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+

9、y-z);end;输入：2 5 7 4 输出 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 beginread(ai); worki:=ai; end; d:=max div 2; while d=1 do begin for i:=d+1 to max do begin x:=worki; j:=i-d; while (j0) and (xworkj) do begin workj+d:=workj; dec(j,d);

10、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. 输入：888 149 32 66 90 144 99 输出： program nbxx09_4;var p:array1.10000 of longint; n,i,x:longint;function find(x:longint):longint;begin if px=x then find:=x else begin px:=find(px); find:

11、=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, ); /两数之间输出一个空格 writeln(pn); end. 输入：5 5 3 3 3 2 4 输出： 四、程序填空（前5空，每空2分，后6空，每空3分，共28分） 1、“高效”排序以下程序实现输入n个数，使用类似冒泡排序的方法，依次比较相邻的两个数，如果前一个数比后一个数大，则交换两者，最终将输入的n个数从小到大排序后输出。程序运行中发现某遍扫描后，没有数据交换发生，说明已经有

12、序了，此时将退出扫描。请将程序补充完整。program nbxx09_5;var n,i,j,tmp:longint; a:array1.10000 of longint; flag:boolean; /flag=true 表示有交换发生，flag=false 表示没有交换begin readln(n); for i:=1 to n do read(ai); i:=1; while flag and (iaj+1 then begin / 前一个比后一个大 tmp:=aj; aj+1:=tmp; end; end; for i:=1 to n-1 do write(ai, ); writeln

13、(an);end.2、数独游戏在n行n列的方格中，每个格子填入一个1n之间数字，使得每行中没有重复数字，每列上也没有重复数字。如图1所示是一个3行3列的合法安排方案。12323131211122112 图4图3图2图1游戏开始可以规定某些格子已经有给定的数字。如图2所示，在2行2列的方格中，规定1行1列和2行2列的数字均为1，则得到唯一的如图3所示的方案。但如果规定1行1列数字为1，2行2列数字为2，则无法得到任何方案（如图4所示）下面得程序求9行9列的一个安排方案，程序首先读入若干个已知格子上的数字，找到一个合理的安排方案后输出。如果没有任何合法方案，则输出No Solution!”(注意引

14、号不用输出)程序填充格子的次序依次为：1行1列，1行2列，1行9列，2行1列，2行2列，2行9列，9行1列，9行2列，9行9列。请你将空白处的程序补充完整。program nbxx09_6;var h:array1.9,1.9 of boolean; /hi,j 表示数字j是否出现在第i行 v:array1.9,1.9 of boolean; / vi,j 表示数字j是否出现在第i列 change: array1.9,1.9 of boolean; /changei,j 表示第i行第j列是否为规定的数字 a: array1.9,1.9 of integer; /保存方案 i,j,k,n,x:i

15、nteger;procedure print; /输出找到的方案var i,j:integer;begin for i:=1 to 9 do beginfor 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 b

16、egin hi,k:=true; vj,k:=true; ； if j9 then search(i,j+1);else search( )；hi,k:=false;vj,k:=false; end; end else begin if j9 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( )； end._宁波e度论坛： 奥数、小升初家长交流QQ群：220500793