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

1. 鼠标器的发明者是

2. 一个无向简单图有10个点,它最多可以有的边数是:

3. 在Pascal中表达式(12 AND 13) XOR 14的值是

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

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

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

7. 有一个10行10列的对称矩阵，采用压缩存储方式来存储该矩阵的上三角元素，行优先次序，第1行第1列的存储地址为s，每个元素占用2个存储空间，则第8行第8列元素的首地址为：

8. 已知一棵二叉树的叶子结点数为100，则有二个子女的结点数为

9. 已知一棵二叉树的前序遍历为JFDECBHAIG，中序遍历结果为DFEJAHBICG，则这棵二叉树的深度为

10. 计算机的数有浮点表示和定点表示，浮点表示的数的两个部分是

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

12. 算式(2009)16-(2008)10+(2007)8的结果是

13. 与递归技术联系最弱的是

14. 以下哪些程序段的时间复杂度为O(n)的

15. 当原始待排序数据为从小到大排列时，运行时间比原始数据为乱序时快的算法是

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

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

18. 在下面各奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是

19. 栈是一种后进先出的数据结构，它有压入（push）和弹出（pop）两种操作。二个元素AB通过入栈和出栈操作，可以有AB和BA两种可能。现在3个元素ABC依次进栈，最终出栈序列有几种可能

20. 以下哪项不属于计算机程序设计竞赛

1. 已知a,b,c,d,e,f,g七个人中，a只会讲英语；b只会讲英语和汉语；c只会讲英语、 意大利语和俄语；d只会讲汉语和日语；e只会讲意大利语和德语；f只会讲俄语、日语和法语；g只会讲德语和法语。能否将他们的座位安排成一圆桌，使得每个人都能与他身边的 人交谈？如果可以，请以“a b”开头写出你的安排方案 _____________ 。
答案：a b d f g e c a

2. 某班有30个同学报名参加100米、400米、800米三项比赛已知有15人报了100米，8人报了400米，6人报了800米，且其中有3人这三个项目都报了。问该班最少有_________人一项都没有报过，最多有________人一项都没有报过？
答案：7|15

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

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

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

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

1. “高效”排序
以下程序实现输入n个数，使用类似冒泡排序的方法，依次比较相邻的两个数，如果前一个数比后一个大，则交换两者，最终将输入的n个数从小到大排序后输出。程序在运行中发现某遍扫描后所有数据已经有序了，将尽快结束工作。请将程序补充完整。

rogram nbcz09_5; 
var n,i,j,tmp:longint; 
    a:array[1..10000]of longint; 
    flag:boolean;  //本遍扫描有否交换发生 

begin 
   readln(n); 
   for i:=1 to n do read(a[i]); 
   i:=1; 
   
_____flag:=true________; 
   while flag and (i<=n-1) do begin  
      flag:=false; 
      for j:=1 to ____n-i___ do 
         if a[j]>a[j+1] then begin 
            tmp:=a[j]; 
            _____a[j]:=a[j+1]_____; 
            a[j+1]:=tmp; 
            _____flag:=true_____;  
         end; 
      _____inc(i)_____; 
   end; 
   for i:=1 to n-1 do write(a[i],' ');  
   writeln(a[n]); 
end. 

2. 正规和枢轴
在一棵有根树中，每个顶点有一个正整数的权值。每个顶点要么是正规顶点(regular vetex)，要么是枢轴顶点(pivot vertex)。一个枢轴顶点的代价等于它的权值，而正规顶点的代价等于顶点权值减去它所有枢轴祖先中权值的最大值(当然代价不能小于0)。选择一个顶点成为枢轴顶点会增加当前的顶点处的代价，但同时可能会减少一些后代的代价。树的代价等于所有顶点的代价之和。

在图1中，选择2号点为枢轴顶点，3号和4号点为正规顶点(1号点任选)时，得到此树的最小代价为 5+10+(13-10)+(12-10)=20
在图2中，选择1号点为枢轴顶点，2号、3号和4号点为正规顶点时，得到此树的最小代价为10+0+(13-10)+(12-10)=15
以下程序假定所有结点依次编号为1~n，根为1号点，每个结点子女数不超过2个。
程序求得一棵有根树的最小代价，请将程序空白处补充完整。

program nbcz09_6; 
const maxn=5; 
var value:array[1..maxn]of longint;//value[j]表示第j点的权值 
    son:array[1..maxn,1..2]of longint;//son[j,k]表示第j点的第k个儿子的顶点号 
    n,i,x,y:longint; 
 
function min(a,b:longint):longint; 
begin if a<b then min:=a else min:=b;end; 
 
function max(a,b:longint):longint; 
begin if a>b then max:=a else max:=b;end; 
 
function caculate(a,b:longint):longint; 
var s1,s2:longint; 
begin 
   s1:=value[a]; 
   if son[a,1]<>0 then 
      s1:=s1+caculate(_____________); 
   if son[a,2]<>0 then 
      s1:=s1+caculate(_____________); 
   s2:=___________; 
   if son[a,1]<>0 then 
      s2:=s2+caculate(son[a,1],b); 
   if son[a,2]<>0 then 
      s2:=s2+caculate(son[a,2],b); 
   caculate:= _________; 
end; 
 
begin 
   readln(n);//n个点 
   for i:=1 to n do read(value[i]); 
   fillchar(son,sizeof(son),0);//son数组所有元素初值0表示开始没有儿子结点 
   for i:=1 to n-1 do begin//读入树的n-1条边 
      readln(x,y); 
      if ___________ then 
         son[x,1]:=y 
      else 
         son[x,2]:=y; 
   end; 
   writeln(caculate(_______)); 
end.