当前位置:首页 >> 其它课程 >>

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

2009 年宁波市第 24 届中小学生计算机程序设计竞赛 一、选择题(1.5 每题) 1、 以下不属于程序的基本结构的是: 顺序结构 选择分支结构 循环结构 树形结构 2、 由 2 个 a,2 个 b 和 2 个 c 构成的所有字符串中,包含子串“abc”的共有( 20 8 16 24 )个。

3、假设 A=TRUE,B=TRUE ,C=TRUE, D=FALSE,逻辑运算表达式 A and B or C and D 的值是: false true 0 1 4、下列数种最大的数是( ) (11111)2 (F)16

(30)10

(35)8 )

5、布尔型(boolean)和字符型(char)变量所占用的存储的空间大小关系是( 布尔型大 字符型大 一样大 因操作系统而异 6、用八位二进制可以表示的最大二进制数是: ( 99999999 11111111 255 ) 265

7、有一个 10 行 10 列的对称矩阵,采用压缩存储方式来存储该矩阵的上三角元素(行 优先次序) ,第 1 行第 1 列的存储地址为 s,每个元素占用 2 个存储空间,则第 8 行第 8 列元素的首地址为: ( ) s+100 s+98 s+72 s+70 8、已知一棵二叉树的前序遍历为 JFDECBHAIG,中序遍历结果为 DFEJAHBICG,则 这棵二叉树的深度为: 6 5 4 3 9、已知一棵二叉树的叶子节点数为 100,在有二个子女的结点数为: 101 100 99 不能确定 10、算术表达式(3a+1)÷5 在程序设计中表达为
3a ? 1 5

(3a+1)/5

(3*a+1)\5

(3*a+1)/5

11、将数组{ 1、2、4、3、5、6、7、8 }中的元素用插入排序的方法从大到小的顺序排 列,需要比较的次数是: 7 27 28 64 12、算式(2009)16-(2008)10-(2007)8 的结果是: ( ) (16170)8 (7234)10 (1C36)16 (1110000111000)2

13、计算机内部使用的数是: 二进制数 八进制数

十进制数

十六进制数

14、当 n 大于 100 万时,下列程序段哪个运行最快: (A). max:=0; for k:=1 to n-1 do for j:=k+1 to n do if max<abs(a[k]-a[j]) then max:=abs(a[k]-a[j]) (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:=a[1]; while k<j do begin while (k<j)and(a[j]>x) do dec(j); if k<j then begin a[k]:=a[j]; inc(k); end; while (k<j)and(a[k]<x) do inc(k); if k<j then begin a[j]:=a[k]; dec(j); end; end;

15、当原始待排序数据为从小到大排列时,运行时间比原来数据为乱序时快的算法是: 选择排序 归并排序 插入排序 快速排序 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 B4 C5 D 6 20、以下哪项不属于计算机程序设计竞赛( A NOIP B 电子作品制作 )

C ACM 大学生程序设计赛

D 宁波市中小学生程序设计竞赛

二、问题求解(每小题 5 分) 1、 已知 a,b,c,d,e,f,g 七个人中,a 会讲英语和汉语,c 会讲英语、意大利语和俄语,d 会讲 汉语和日语, e 会讲意大利语和德语, f 会讲俄语、日语和法语, g 会讲德语和法 语。能否将他们的座位安排在圆桌旁,使得每个人都能与他的身边人交谈,如果可以, 请以“a b”开头写出你的安排方案: adfgecb 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<>b 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 33324 输出:

四、程序填空(前 5 空,每空 2 分,后 6 空,每空 3 分,共 28 分) 1、 “高效”排序 以下程序实现输入 n 个数,使用类似冒泡排序的方法,依次比较相邻的两个数,如果 前一个数比后一个数大,则交换两者,最终将输入的 n 个数从小到大排序后输出。程序运行 中发现某遍扫描后,没有数据交换发生,说明已经有序了,此时将退出扫描。请将程序补充 完整。 program nbxx09_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 ② 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]);

do // 前一个比后一个大

end. 2、 数独游戏 在 n 行 n 列的方格中, 每个格子填入一个 1——n 之间数字, 使得每行中没有重复数字, 每列上也没有重复数字。如图 1 所示是一个 3 行 3 列的合法安排方案。 1 2 3 2 3 1 图1 3 1 2 图2 图3 图4 1 1 1 2 2 1 1 2

游戏开始可以规定某些格子已经有给定的数字。如图 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 行 9 列,2 行 1 列,2 行 2 列,??2 行 9 列,9 行 1 列,9 行 2 列,??,9 行 9 列。 请你将空白处的程序补充完整。

program nbxx09_6; var h:array[1..9,1..9] of boolean; //h[i,j] 表示数字 j 是否出现在第 i 行 v:array[1..9,1..9] of boolean; // v[i,j] 表示数字 j 是否出现在第 i 列 change: array[1..9,1..9] of boolean; //change[i,j] 表示第 i 行第 j 列是否为规定的数字 a: array[1..9,1..9] of integer; //保存方案 i,j,k,n,x:integer; procedure print; //输出找到的方案 var i,j:integer; begin for i:=1 to 9 do begin for j:=1 to 8 do write(a[i,j],’ ‘); writeln( ⑥ ); end; end; procedure search(i,j:integer); //从 i 行 j 列开始填充 var k:integer; begin if ( ⑦ ) then begin print; halt;

end; if change[i,j] then begin for k:=1 to 9 do if (not h[i,k])and(not v[j,k]) then begin h[i,k]:=true; v[j,k]:=true; ⑧ ; if j<9 then search(i,j+1); else search( ⑨ ); h[i,k]:=false; v[j,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 h[i,j]:=false; //第 i 行没有数字 j 出现 v[i,j]:=false; //第 i 列没有数字 j 出现 a[i,j]:=0; //第 i 行第 j 列没有数字填入 change[i,j]:=true; //第 i 行第 j 列允许填充(没有给定的输入数字) end; readln(n); for k:=1 to n do begin readln(i,j,x); a[i,j]:=x; //第 i 行第 j 列给定的数字为 x h[i,x]:=true; //第 i 行出现数字 x v[j,x]:=true; //第 j 列出现数字 x change[i,j]:false; //第 i 行第 j 列不允许填充(以后给定的输入数字) end; search( ⑩ ); writeln( ⑾ ); end.


相关文章:
更多相关标签: