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万时,下列程序段哪个运行最快 (B)sum:=0;k:=1; while k<=n do begin (A)max:=0; for j:= 1 to k do for k:=1 to n-1 do sum:=sum+1; for j:=k+1 to n do k:=k+2; if max 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+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]);
第24届2009年中小学生计算机程序设计竞赛 小学组 含答案



