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

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

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

初中组初赛试题

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

AD

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

1、鼠标器的发明者是：

（A）Von Neumann （B）Marvin Lee Minsky （C）Ada Lovelace （D）Douglas Engelbart

2、一个无向简单图有10个点,它最多可以有的边数是:(A)100 (B)90 (C)50 (D)45

3、在Pascal中，表达式(12 AND 13) XOR 14的值是：

（A）2 （B）1 （C）13 （D）14

4、中缀表达式(a*(b+c)+d)*(e+f)的后缀表达式是：

（A）a*bc+d+ef+* （B）abc+*d+e+f* （C）*+*a+bcd+ef （D）abc+*d+ef+*

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

（A）布尔型大 （B）字符型大 （C）一样大 （D）因操作系统而异

6、一个字节的有符号数，以补码表示的最小二进制数是：

（A）10000000 （B）11111111 （C）01111111 （D）00000000

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、计算机的数有浮点表示和定点表示，浮点表示的数的两个部分是：

（A）指数和基数 （B）阶码和尾数 （C）尾数和小数 （D）整数和小数

11、在对数组进行插入排序时，我们可以使用二分查找，对要插入的元素快速找到在已经排好的元素序列中的位置。关于上述算法，下面叙述中正确的是：

（A）元素总的移动次数为O(nlogn)，排序的时间复杂度为O(nlogn) （B）元素间总的比较次数为O(nlogn)，排序的时间复杂度为O(nlogn) （C）元素总的移动次数为O(n2)，排序的时间复杂度为O(n2)

第1页 共7页

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

（D）元素间总的比较次数为O(n2)，排序的时间复杂度为O(n2) 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、以下哪些程序段的时间复杂度为O(n)的：

（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 maxx)do dec(j); for j:= 1 to n do if k

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

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

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

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

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

17、以下有关数组与链表的说法正确的是：

（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

第2页 共7页

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

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 nbcz09_1;

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 输出：

2、program nbcz09_2;

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;

第3页 共7页

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

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

3、program nbcz09_3;

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

输出： ______ _______________________

第4页 共7页

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

4、program nbcz09_4;

var n,n1,p,q,d,e:longint; i,x,y,s:longint;

function euclid(a,b:longint;var x,y:longint):longint; var d1,x1,y1:longint; begin

if b=0 then begin

x:=1;y:=0;d1:=a; end else begin

d1:=euclid(b,a mod b,x1,y1); x:=y1;y:=x1-a div b *y1; end;

euclid:=d1; end;

function MLE(a,b,n:longint):longint; var i,d,x,y:longint; begin

d:=euclid(a,n,x,y);

if b mod d=0 then MLE:=x

else begin writeln('Error!');halt;end; end;

begin

readln(p,q,e);

n:=p*q;n1:=(p-1)*(q-1); readln(x); s:=1;

for i:=1 to e do s:=(s*x)mod n; writeln(s);

d:=MLE(e,1,n1); readln(x); s:=1;

for i:=1 to d do s:=(s*x)mod n; writeln(s); end.

输出：_____________ 输入：3 11 7

9 _____________ 15

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

1、“高效”排序

以下程序实现输入n个数，使用类似冒泡排序的方法，依次比较相邻的两个数，如

第5页 共7页