第十二届全国青少年信息学奥林匹克联赛(提P&C)试题及答案

NOIP2006第十二届全国青少年信息学奥林匹克联赛初赛

（提高组P&C）试题及答案

●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●

一、单项选择题（共10题，每题1.5分，共计15分。每题有且仅有一个正确答案.）。

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

A.控制器

B.运算器

C.寄存器

D.ALU

E.RAM

2.BIOS（基本输入输出系统）是一组固化在计算机内（）上一个ROM芯片上的程序。

A.控制器

B.CPU

C.主板

D.内存条

E.硬盘

3.在下面各世界顶级的奖项中，为计算机科学与技术领域作出杰出贡献的科学家设立的奖项是（）。

A.沃尔夫奖

B.诺贝尔奖

C.菲尔兹奖

D.图灵奖

E.南丁格尔奖

4．在编程时（使用任一种高级语言，不一定是C），如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组），按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（）。

A.没有区别

B.有一些区别，但机器处理速度很快，可忽略不计

C.按行读的方式要高一些

D.按列读的方式要高一些

E.取决于数组的存储方式。5．在C语言中，表达式21^2的值是（）

A.441

B.42

C.23

D.24

E.25

6．在C语言中，判断a不等于0且b不等于0的正确的条件表达式是（）

A.!a==0||!b==0

B.!((a==0)&&(b==0))

C.!(a==0&&b==0)

D.a!=0||b!=0

E.a&&b 7．某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）。

A.1,2,3,4,5

B.1,2,4,5,7

C.1,4,3,7,6

D.1,4,3,7,2

E.1,4,3,7,5

8．高度为n的均衡的二叉树是指：如果去掉叶结点及相应的树枝，它应该是高度为n-1的满二叉树。在这里，树高等于叶结点的最大深度，根结点的深度为0，如果某个均衡的二叉树共有2381个结点，则该树的树高为（）。

A.10

B.11

C.12

D.13

E.210–1

9.与十进制数1770.625对应的八进制数是（）。

A.3352.5

B.3350.5

C.3352.1161

D.3350.1151

E.前4个答案都不对

10．将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。

A.6

B.7

C.8

D.9

E.10

二、不定项选择题（共10题，每题1.5分，共计15分。每题正确答案的个数大于或等于1。多选或少选均不得分）。

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

A.(A∧B)∨(C∧D)∨?E

B.??(((A∧B)∨C)∧D∧E)

C.A∧(B∨C∨D∨E)

D.(A∧(B∨C))∧D∧E

12.(2010)16+(32)8的结果是（）。

A.(8234)10

B.(202A)16

C.(100000000110)2

D.(2042)16

13.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（）。

A.a,b,c,e,d

B.b,c,a,e,d

C.a,e,c,b,d

D.d,c,e,b,a

14.已知6个结点的二叉树的先根遍历是123456（数字为结点的编号，以下同），后根遍历是325641，则该二叉树的可能的中根遍历是（）

A.321465

B.321546

C.231546

D.231465

15.在下列各数据库系统软件中，以关系型数据库为主体结构的是（）。

A.ACCESS

B.SQL Server

C.Oracle

D.Foxpro

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

A.gcc/g++

B.Turbo Pascal

C.Turbo C

D.free pascal

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

A.硬盘

B.ROM

C.显存

D.RAM

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

A.Pascal和C都是编译执行的高级语言

B.高级语言程序比汇编语言程序更容易从一种计算机移植到另一种计算机上

C.C++是历史上的第一个支持面向对象的计算机语言

D.高级语言比汇编语言更高级，是因为它的程序的运行效率更高

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

A.一个正确的算法至少要有一个输入

B.算法的改进，在很大程度上推动了计算机科学与技术的进步

C.判断一个算法的好坏，主要依据它在某台计算机上具体实现时的运行时间

D.目前仍然存在许多涉及到国计民生的重大课题，还没有找到能够在计算机上实施的有效算法

20.在下列关于青少年信息学竞赛的说法中，你赞成的是（）（本题不回答为0分，答题一律满分）。

A.举行信息学竞赛的目的，是为了带动广大青少年学科学、爱科学，为造就一大批优秀的计算机科学与技术人才奠定良好的基础

B.如果竞赛优胜者不能直接保送上大学，我今后就不再参与这项活动了

C.准备竞赛无非要靠题海战术，为了取得好成绩，就得拼时间、拼体力

D.为了取得好成绩，不光要看智力因素，还要看非智力因素。优秀选手应该有坚韧不拔的意志，有严谨求实的作风，既要努力奋进，又要胜不骄败不馁

三．问题求解（共2题，每题5分，共计10分）

1．将2006个人分成若干不相交的子集，每个子集至少有3个人，并且：（1）在每个子集中，没有人认识该子集的所有人。（2）同一子集的任何3个人中，至少有2个人互不认识。（3）对同一子集中任何2个不相识的人，在该子集中恰好只有1个人认识这两个人。则满足上述条件的子集最多能有___________个？

2．将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为_____________。

四．阅读程序写结果（共4题，每题8分，共计32分）

Pascal语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1.Program ex401;

var

u,v:array[0..3]of integer;

i,x,y:integer;

begin

x:=10;y:=10;

for i:=0to3do

read(u[i]);

v[0]:=(u[0]+u[1]+u[2]+u[3])div7;

v[1]:=u[0]div((u[1]-u[2])div u[3]);

v[2]:=u[0]*u[1]div u[2]*u[3];

v[3]:=v[0]*v[1];

x:=(v[0]+v[1]+2)-u[(v[3]+3)mod4];

if(x>10)then

y:=y+(v[2]*100-v[3])div(u[u[0]mod3]*5)

else

y:=y+20+(v[2]*100-v[3])div(u[v[0]mod3]*5);

writeln(x,',',y);

end.{*注：本例中，给定的输入数据可以避免分母为0或下标越界。)输入：9394

输出：_______________

2.Program ex402;

const

m:array[0..4]of integer=(2,3,5,7,13);

var

i,j:integer;

t:longint;

begin

4for i:=0to4do

begin

t:=1;

for j:=1to m[i]-1do t:=t*2;

t:=(t*2-1)*t;

write(t,'');

end;writeln;end.

输出:____________________

3.Program ex403;

Const NN=7;

Type

Arr1=array[0..30]of char;

var

s:arr1;

k,p:integer;

function fun1(s:arr1;a:char;n:integer):integer;

var

j:integer;

begin

j:=n;

while(a0)do dec(j);

fun1:=j;

end;

Function fun2(s:arr1;a:char;n:integer):integer; var

j:integer;

begin

j:=1;

while(a>s[j])and(j

fun2:=j;

end;begin

for k:=1to NN do

s[k]:=chr(ord('A')+2*k+1);

k:=fun1(s,'M',NN)+fun2(s,'M',NN);

5writeln(k);

end.

输出：_____________

4.program ex404;

var

x,x2:longint;

procedure digit(n,m:longint);

var n2:integer;

begin

if(m>0)then

begin

n2:=n mod10;

write(n2:2);

if(m>1)then digit(n div10,m div10);

n2:=n mod10;

write(n2:2);

end;

end;begin

writeln('Input a number:');

readln(x);

x2:=1;

while(x2

x2:=x2div10;

digit(x,x2);

writeln;end.

输入：9734526

输出：______________________________

C语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1.#include

int main()

{int i,u[4],v[4],x,y=10;

for(i=0;i<=3;i++)

scanf("%d",&u[i]);

v[0]=(u[0]+u[1]+u[2]+u[3])/7;

v[1]=u[0]/((u[1]-u[2])/u[3]);

v[2]=u[0]*u[1]/u[2]*u[3];

v[3]=v[0]*v[1];

x=(v[0]+v[1]+2)-u[(v[3]+3)%4];

if(x>10)

y+=(v[2]*100-v[3])/(u[u[0]%3]*5);

else

y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5);

printf("%d,%d\n",x,y);

return0;

}/*注：本例中，给定的输入数据可以避免分母为0或下标越界。*/输入：9394

输出：_______________

2．#include

main()

{int i,j,m[]={2,3,5,7,13};

long t;

for(i=0;i<=4;i++)

{t=1;

for(j=1;j

printf("%ld",(t*2-1)*t);

}

printf("\n");

}

输出:____________________

3．#include"stdio.h"

#define N7

int fun1(char s[],char a,int n)

{int j;

j=n;

while(a0)j--;

return j;

}

int fun2(char s[],char a,int n)

{int j;

while(a>s[j]&&j<=n)j++;

return j;

}

void main()

{char s[N+1];

int k,p;

for(k=1;k<=N;k++)

s[k]='A'+2*k+1;

p=fun1(s,'M',N);

printf(“%d\n”,p+fun2(s,'M',N));

}

输出：_____________

4.#include

void digit(long n,long m)

{if(m>0)

printf("%2ld",n%10);

if(m>1)

digit(n/10,m/10);

printf("%2ld",n%10);

}

main()

{long x,x2;

printf("Input a number:\n");scanf("%ld",&x);

x2=1;

while(x2

x2/=10;

digit(x,x2);

printf("\n");

}

输入：9734526

输出：______________________________

五．完善程序(前5空，每空2分，后6空，每空3分，共28分)

Pascal语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1．（选排列）下面程序的功能是利用递归方法生成从1到n(n<10)的n个数中取k(1<=k<=n)个数的

全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输出5个排列）：

1213212332

31

程序：

6Program ex501;

i,n,k:integer;

a:array[1..10]of integer;

count:longint;

Procedure perm2(j:integer);

var i,p,t:integer;

begin if

①then

begin

for i:=k to n do

begin

inc(count);

t:=a[k];a[k]:=a[i];a[i]:=t;

for②do write(a[p]:1);

write('');

t:=a[k];a[k]:=a[i];a[i]:=t;

if(count mod5=0)then writeln;

end;exit;end;

for i:=j to n do

begin

t:=a[j];a[j]:=a[i];a[i]:=t;

③;

t:=a[j];④;

end

end;begin

writeln('Entry n,k(k<=n):');read(n,k);

count:=0;

for i:=1to n do a[i]:=i;

⑤;

end.

2．（TSP问题的交叉算子）TSP问题(Traveling Salesman Problem)描述如下：给定n个城

市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环

路，每个城市恰好经过一次，求使总代价达到最小的一条环路。

7遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法

之一是1到n这n个数字的一个排列，每个数字为一个城市的编号。例如当n=5时，“34 215”

表示该方案实施的路线为3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两

个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：

(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。

(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：

(2.1)将两个互换段中，共同的数字标记为0，表示已处理完。

(2.2)将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。

例如：n=12，两个个体分别是：

a1:1354*2679*1012811

a2:32112*671011*8549

t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从1开始，互换后有：

a1:1354*671011*1012811

a2:32112*2679*8549

然后，将数字6,7对应的项标记为0，星号内数字2,9,10,11对应的项标记为1，并且按顺序对

应关系为:10<->2，11<->9。于是，将a1[9]=10替换为a1[9]=2，将a2[2]=2替换为a2[2]=10，

类似再做第2组替换。这样处理后，就得到了两个新个体：

a1:135467*********

a2:310112267985411

（3）输出两个新个体的编码。

程序：

program ex502;

type arr1=array[1..20]of integer;

var

a1,a2,kz1,kz2:arr1;

n,k,t1,t2:integer;

function rand1(k:integer):integer;

var t:integer;

begin

t:=0;

while(t<2)or(t>k)do

t:=random(k+1)-2;

rand1:=t;

end;

procedure read1(var a:arr1;m:integer);

{读入数组元素a[1]至a[m]，a[0]=0，略。}

procedure wrt1(var a:arr1;m:integer);

{输出数组元素a[1]至a[m]，略。}

8procedure cross(var a1,a2:arr1;t1,t2,n:integer);

var

i,j,t,kj:integer;

begin

for i:=t1to t2do

begin

t:=a1[i];①;

end;

for i:=1to n do

if(it2)then

begin

kz1[i]:=-1;kz2[i]:=-1;

end else begin

②;end;

for i:=t1to t2do

for j:=t1to t2do

if(a1[i]=a2[j])then

begin③;break;end;

for i:=t1to t2do

if(kz1[i]=1)then

begin

for j:=t1to t2do

if(kz2[j]=1)then

begin kj:=j;break;end;

for j:=1to n do

if④then

begin a1[j]:=a2[kj];break;end;

for j:=1to n do

if⑤then

begin a2[j]:=a1[i];break;end;

kz1[i]:=0;kz2[kj]:=0;

end;end;begin

writeln('input(n>5):');

readln(n);

writeln('input array1:');read1(a1,n);

9writeln('input array2:');read1(a2,n);

t1:=rand1(n-1);

repeat

t2:=rand1(n-1);

until(t1<>t2);

if(t1>t2)then

begin k:=t1;t1:=t2;t2:=k;end;

⑥;

wrt1(a1,n);wrt1(a2,n);

end.

10

C语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1．（选排列）下面程序的功能是利用递归方法生成从1到n(n<10)的n个数中取k(1<=k<=n)个数的全部可能的排列（不一定按升序输出）。例如，当n=3，k=2时，应该输出（每行输

出5个排列）：

1213212332

31

程序：

#include

int n,k,a[10];

long count=0;

void perm2(int j)

{int i,p,t;

if(①)

{for(i=k;i<=n;i++)

{count++;

t=a[k];a[k]=a[i];a[i]=t;

for(②)

printf("%1d",a[p]);/*"%1d"中是数字1，不是字母l*/

printf("");

t=a[k];a[k]=a[i];a[i]=t;

if(count%5==0)printf("\n");

}

return;

}

for(i=j;i<=n;i++)

{t=a[j];a[j]=a[i];a[i]=t;

③;

t=a[j];④;

}

}

main()

{int i;

printf("\nEntry n,k(k<=n):\n");

scanf("%d%d",&n,&k);

for(i=1;i<=n;i++)a[i]=i;

⑤;

}

2．（TSP问题的交叉算子）TSP问题(Traveling Salesman Problem)描述如下：给定n个城市，构成一个完全图，任何两城市之间都有一个代价（例如路程、旅费等），现要构造遍历所有城市的环路，每个城市恰好经过一次，求使总代价达到最小的一条环路。

遗传算法是求解该问题的一个很有效的近似算法。在该算法中，一个个体为一条环路，其编码方法之一是1到n这n个数字的一个排列，每个数字为一个城市的编号。例如当n=5时，“34215”表示该方案实施的路线为3->4->2->1->5->3。遗传算法的核心是通过两个个体的交叉操作，产生两个新的个体。下面的程序给出了最简单的一种交叉算法。具体过程如下：

(1)选定中间一段作为互换段，该段的起止下标为t1，t2，随机生成t1，t2后，互换两段。

(2)互换后，在每个新的排列中可能有重复数字，因而不能作为新个体的编码，一般再做两步处理：(2.1)将两个互换段中，共同的数字标记为0，表示已处理完。

(2.2)将两个互换段中其余数字标记为1，按顺序将互换段外重复的数字进行替换。

例如：n=12，两个个体分别是：

a1:1354*2679*1012811

a2:32112*671011*8549

t1=5，t2=8。上述每一行中，两个星号间的部分为互换段。假定数组的下标从1开始，互换后有：

a1:1354*671011*1012811

a2:32112*2679*8549

然后，将数字6,7对应的项标记为0，星号内数字2,9,10,11对应的项标记为1，并且按顺序对应关系为:10<->2，11<->9。于是，将a1[9]=10替换为a1[9]=2，将a2[2]=2替换为a2[2]=10，类似再做第2组替换。这样处理后，就得到了两个新个体：

a1:135467*********

a2:310112267985411

（3）输出两个新个体的编码。

程序：

#include

#include

#define N20

int a1[N],a2[N],kz1[N],kz2[N]，n;

int rand1(int k)

{int t=0;

while(t<2||t>k)

t=(int)((double)rand()/RAND_MAX*k);

return t;

}

void read1(int a[],int m)

{读入数组元素a[1]至a[m]，a[0]=0，略。}

void wrt1(int a[],int m)

{输出数组元素a[1]至a[m]，略。}

void cross(int a1[],int a2[],int t1,int t2,int n)

{int i,j,k,t,kj;

for(i=t1;i<=t2;i++)

{t=a1[i];①；

}

for(i=1;i<=n;i++)

if(it2)

kz1[i]=kz2[i]=-1;

else

②；

for(i=t1;i<=t2;i++)

for(j=t1;j<=t2;j++)

if(a1[i]==a2[j])

{③;break;

}

for(i=t1;i<=t2;i++)

if(kz1[i]==1)

{for(j=t1;j<=t2;j++)

if(kz2[j]==1)

{kj=j;break;

}

for(j=1;j<=n;j++)

if(④)

{a1[j]=a2[kj];break;

}

for(j=1;j<=n;j++)

if(⑤)

{a2[j]=a1[i];break;

}

kz1[i]=kz2[kj]=0;

}

}

main()

{int k,t1,t2;

printf("input(n>5):\n");scanf("%d",&n);

printf("input array1(%d'numbers):\n",n);read1(a1,n);

printf("input array2(%d'numbers):\n",n);read1(a2,n);

t1=rand1(n-1);

do

{t2=rand1(n-1);

}while(t1==t2);

if(t1>t2)

{k=t1;t1=t2;t2=k;

}

⑥

wrt1(a1,n);wrt1(a2,n);

}

参考答案与评分标准

一、单项选择题：（每题1.5分）

1.E

2.C

3.D

4.E

5.C

6.（满分）

7.C

8.B

9.A10.B

二、不定项选择题：（每题1.5分）

11.ABC12.AB13.C14.BC15.ABCD16.AD17.CD18.AB19.BD20.（满分，空白0分）

三、问题求解：（每题5分）

1.401

2.9!（或362880）

四、阅读程序写结果

1.-13，57（对1个数给4分，无逗号扣1分）

2.628496812833550336（前2个对1个数给1分，后3个对1个数给2分）

3.11

4.62543799734526（数字之间无空格扣2分）

五、完善程序(前5空，每空2分，后6空，每空3分)

PASCAL语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1．①j=k（或k=j）

②p:=1to k

③perm2(j+1)

④a[j]:=a[i];a[i]:=t

⑤perm2(1)

2．①a1[i]:=a2[i];a2[i]:=t

②kz1[i]:=1;kz2[i]:=1;

③kz1[i]:=0;kz2[j]:=0;

④(a1[j]=a1[i])and(kz1[j]=-1)

⑤(a2[j]=a2[kj])and(kz2[j]=-1)IFans.c收集

⑥cross(a1,a2,t1,t2,n)

C语言

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

1．①j=k（或k=j）

②p:=1to k

③perm2(j+1)

④a[j]:=a;a:=t

⑤perm2(1)

2．①a1:=a2;a2:=t

②kz1:=1;kz2:=1;

③kz1:=0;kz2[j]:=0;

④(a1[j]=a1)and(kz1[j]=-1)

⑤(a2[j]=a2[kj])and(kz2[j]=-1)

⑥cross(a1,a2,t1,t2,n)