全国第十三届青少年信息学奥林匹克竞赛分区联赛初赛试题 [2007年]

1. 在以下各项中。（ ）不是 CPU 的组成部分。

2. 在关系数据库中, 存放在数据库中的数据的逻辑结构以( )为主。

3. 在下列各项中，只有（ ）不是计算机存储容量的常用单位。

4. ASCII码的含义是（ ）。

5. 在 Pascal 语言中，表达式 (23 or 2 xor 5)的值是（ ）

6. 在 Pascal 语言中，判断整数a 等于 0 或b等于 0或c等于0 的正确的条件表达式是（ ）

7. 地面上有标号为A、B、C的3根细柱, 在A柱上放有10个直径相同中间有孔的圆盘, 从上到下次依次编号为1, 2, 3, ……，将A柱上的部分盘子经过B柱移入C柱, 也可以在B柱上暂存。如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么, 在C柱上, 从下到上的盘子的编号为（ ）。

8. 与十进制数17.5625相对应的8进制数是（ ）。

9. 欧拉图G是指可以构成一个闭回路的图，且图G的每一条边恰好在这个闭回路上出现一次（即一笔画成）。在以下各个描述中, 不一定是欧拉图的是：（ ）。

10. 一个无法靠自身的控制终止的循环称为“死循环”，例如在C语言程序中，语句“while(1)printf("*")；”就是一个死循环，运行它将无休止地打印*号。下面关于死循环的说法中, 只有（ ）是正确的。

1. 设A=B=true，C=D=false，以下逻辑运算表达式值为真的有（ ）。

2. 命题“P→Q”可读做P蕴含Q， 其中P、Q是两个独立的命题. 只有当命题P成立而命题Q不成立时， 命题"P→Q"的值为false， 其它情况均为true. 与命题"P→Q"等价的逻辑关系式是（ ）。

3. (2070)16+(34)8的结果是（ ）。

4. 已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7(数字为结点的编号，以下同)， 后根遍历是4 6 5 2 7 3 1， 则该二叉树的可能的中根遍历是（ ）

5. 冗余数据是指可以由以他数据导出的数据，例如，数据库中已存放了学生的数学、语文、和英语的三科成绩，如果还存放三科成绩的总分，则总分就可以看做冗余数据。冗余数据往往会造成数据的不一致，例如上面4个数据如果都是输入的，由于操作错误使总分不等于三科成绩之和，就会产生矛盾。下面关于冗余数据的说法中， 正确的是（ ）。

6. 在下列各软件中，属于 NOIP 竞赛（复赛）推荐使用的语言环境有（ ）。

7. 以下断电之后将仍能保存数据的有（ ）。

8. 在下列关于计算机语言的说法中，正确的有（ ）。

9. 在下列关于算法复杂性的说法中， 正确的有（ ）。

10. 近20年来， 许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具. 在下列关于递归的说法中， 正确的是（ ）。

1. 给定n个有标号的球，标号依次为1，2，…，n。将这n个球放入r个相同的盒子里，不允许有空盒，其不同放置方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的放置方法依次为{(1) , (234)} , {(2) , (134)} , {(3) , (124)} , {(4) , (123)} , {(12) , (34)} , {(13) , (24)} , {(14) , (23)}。当n=7，r=4时，S(7,4)= ________ 。
答案：350

2. N个人在操场里围成一圈，将这N个人按顺时针方向从1到N编号，然后从第一个人起，每隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直到操场只剩下一个人，记这个人的编号为J(N)，例如，J(5)=3，J(10)=5，等等。 则J(400)=__________。
答案：289

1.

program s401;
var p,q:array[0..5] of integer;
    i,x,y:integer;
begin
   y:=20;
   for i:=0 to 4 do read(p[i]);
   readln;
   q[0]:=(p[0]+p[1])+(p[2]+p[3]+p[4]) div 7;
   q[1]:=p[0]+p[1] div ((p[2]+p[3]) div p[4]);
   q[2]:=p[0]*p[1] div p[2];
   q[3]:=q[0]*q[1];
   q[4]:=q[1]+q[2]+q[3];
   x:=(q[0]+q[4]+2)-p[(q[3]+3) mod 4];
   if (x>10) then
     y:=y+(q[1]*100-q[3]) div (p[p[4] mod 3]*5)
   else
     y:=y+20+(q[2]*100-q[3]) div (p[p[4] mod 3]*5);
   writeln(x,',',y);
end.
/*注：本例中，给定的输入数据可以避免分母为 0 或下标越界。
输入：6 6 5 5 3

输出：129,43

2.

program s402;
var a,b:integer;
    x,y:^integer;
procedure fun(a,b:integer);
var k:integer;
begin
 k:=a; a:=b; b:=k;
end;
begin
 a:=3; b:=6;
 x:=@a; y:=@b;
 fun(x^,y^);
 write('No.1:',a,',',b,'  ');
 fun(a,b);
 writeln('No.2:',a,',',b);
end.
输出：No.1:3,6  No.2:3,6

3.

 program S403;
var a1:array[1..50] of integer;
var i,j,t,t2,n,n2:integer;
begin
 n:=50;
 for i:=1 to n do a1[i]:=0;
 n2:=round(sqrt(n));
 for i:=2 to n2 do
  if(a1[i]=0) then
    begin
      t2:=n div i;
      for j:=2 to t2 do a1[i*j]:=1;
    end;
  t:=0;
  for i:=2 to n do
  if (a1[i]=0) then
    begin
      write(i:4);  inc(t);
      if(t mod 10=0) then writeln;
    end;
  writeln;
 end.
输出：  2   3   5   7  11  13  17  19  23  29  31  37  41  43  47

4.

program S404;
const n=12;
  ch2:array[0..12] of char
    =('q','A','S','O','R','T','E','X','A','M','P','L','E');
var k:integer;
    ch:array[0..12] of char;
procedure  shift(k,n:integer);
var v:char;
    j:integer;
begin
  v:=ch[k]; j:=k+k;
  while (j<=n) do
    begin
      if (j<n) and (ord(ch[j])<ord(ch[j+1])) then inc(j);
      if (ord(v)<ord(ch[j])) then
        begin ch[j div 2]:=ch[j]; j:=j*2; end
      else
        exit;
      ch[j div 2]:=v;
    end;
end;
procedure hpsrt;
var k:integer;
    tmp:char;
begin
  for k:=n div 2 downto 1 do  shift(k,n);
  write('No.1: ');
  for k:=1 to n do  write(ch[k]);
  writeln;
  for k:=n downto 1 do
   begin
     tmp:=ch[1]; ch[1]:=ch[k]; ch[k]:=tmp;
     shift(1,k-1);
   end;
end;
begin
  for k:=0 to n do ch[k]:=ch2[k];
  hpsrt;
  write('No.2: ');
  for k:=1 to n do write(ch[k]);
  writeln;
end.

输出：No.1: XTORSEAAMPLE
No.2: AAEELMOPRSTX

1. (格雷码 Gray Code) Gray Code是一种二进制编码，编码顺序与相应的十进制数的大小不一致。其特点是，对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数间也仅有一个二进制位不同，以4位二进制数为例，编码如下：
十进制数 格雷码 十进制数 格雷码
0 0000 8 1100
1 0001 9 1101
2 0011 10 1111
3 0010 11 1110
4 0110 12 1010
5 0111 13 1011
6 0101 14 1001
7 0100 15 1000
如果把每个二进制的位看做一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数-模转换等领域。
下面程序的任务是：由键盘输入二进制的位数n(n<16)，再输入一个十进制数m(0≤m<2n)，然后输出对应于m的格雷码(共n位，用数组gr[ ]存放)

program s501; 
var bound，m，n，i，j，b，p:integer; 
gr:array[0..14]of integer; 
begin 
bound:=1; 
writeln('input n，m'); 
readln(n，m); 
for i:=1 to n do bound:= bound*2 ; 
if (m<0)or(m>=bound) then 
begin 
writeln('Data error!'); 
 exit ; 
end; 
b:=1; 
for i:=1 to n do 
begin 
p:=0; b:=b*2; 
for  j:=0  to m do 
if (  (j mod b-(b div 2))=0  ) then 
p:=1-p; 
gr:=p; 
end; 
for i:=n   downto 1  do 
write(gr); 
writeln; 
end.

2. （连续邮资问题）某国发行了n种不同面值的邮票，并规定每封信上最多允许贴m张邮票。在这些约束下，为了能贴出{1，2，3，…，maxvalue}连续整数集合的所有邮资，并使maxvalue的值最大，应该如何设计各邮票的面值?例如，当n=5和m=4时，面值设计为（1，3，11，15，32），可使maxvalue达到最大值70（或者说,用这些面值的1至4张邮票可以表示不超过70的所有邮资，但无法表示邮资71）。而用其他面值的1至4张邮票如果可以表示不超过k的所有邮资，必有k≤70）
下面是用递归回溯求解连续邮资问题的程序。数组x[1：n]表示n种不同的邮票面值，并约定各元素按下标是严格递增的。数组bestx[1：n]存放使maxvalue达到最大值的邮票面值（最优解），数组y[maxl]用于记录当前已选定的邮票面值x[1：i]能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。

program S502;
const NN=20;
      maxint=30000;
      maxl=500;
var bestx,x:array [0..NN] of integer;
    y:array [0..maxl] of integer;
    j,n,m,maxvalue:integer;
procedure result;
var j:integer;
begin
 writeln('max=',maxvalue);
 for j:=1 to n do  write(bestx[j]:4);
 writeln;
end;
procedure backtrace(i,r:integer);
var j,k:integer;
    z: array[0..maxl] of integer;
begin
 for j:=0 to x[i-2]*(m-1) do
   if (y[j]<m) then
      for k:=1 to m-y[j] do
       if (y[j]+k<=y[  j+x[i-1]*k  ]) then
         y[  j+x[i-1]*k  ]:=y[j]+k;
  while (y[r]<maxint) do inc(r);
  if (i>n) then
   begin
    if (r-1>maxvalue) then
     begin
       maxvalue:= r-1 ;
       for j:=1 to n do bestx[j]:=x[j];
     end;
    exit;
   end;
 for k:=0 to maxl do z[k]:=y[k];
 for j:= x[i-1]+1 to r do
  begin
   x[i]:=j;
   backtrace(i+1,r) ;
   for k:=0 to maxl do  y[k]:=z[k];
  end;
end;
begin
 maxvalue:=0;
 writeln('input n,m:');
 readln(n,m);
 for j:=1 to maxl do y[j]:=maxint;
 y[0]:=0;  x[0]:=0; x[1]:=1;
 backtrace(2,1);
 result;
end.