第十一届全国青少年信息学奥林匹克联赛初赛提PC试题与答案.docx

第十一届全国青少年信息学奥林匹克联赛初赛提PC试题与答案.docx

《第十一届全国青少年信息学奥林匹克联赛初赛提PC试题与答案.docx》由会员分享，可在线阅读，更多相关《第十一届全国青少年信息学奥林匹克联赛初赛提PC试题与答案.docx（17页珍藏版）》请在冰点文库上搜索。

第十一届全国青少年信息学奥林匹克联赛初赛提PC试题与答案

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

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

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

一、单项选择题（共10题，每题1.5分，共计15分。

每题有且仅有一个正确答案.）。

1.字符串“ababacbab”和字符串“abcba”的最长公共子串是（）。

A.abcbaB.cbaC.abcD.abE.bcba

=={a,b,c,d,e,f}，CA2.设全集I={a,b,c,d,e,f,g,h}，集合BA{c,d,e}，

为（）。

={a,d}，那么集合CBABA~

A.{c,e}B.{d,e}C.{e}D.{c,d,e}E.{d,f}

3.以下二进制数的值与十进制数23.456的值最接近的是（）。

A.10111.0101B.11011.1111C.11011.0111D.10111.0111E.10111.1111

4.完全二叉树的结点个数为4*N+3，则它的叶结点个数为（）。

A.2*NB.2*N-1C.2*N+1D.2*N-2E.2*N+2

5.平面上有五个点A（5,3）,B（3,5）,C（2,1）,D（3,3）,E（5,1）。

以这五点作为完全图G的顶点，每两点之间的直线距离是图G中对应边的权值。

图G的最小生成树中的所有边的权值综合为（）。

A.8B.7+5C.9D.6+5E.4+22+5

6.下列设备中没有计算功能的是（）。

A.笔记本电脑B.掌上电脑C.智能手机D.电子计算器E.液晶显示器

7.Intel的首颗64位处理器是（）。

A.8088B.8086C.80386D.80486E.Pentium

8.常见的邮件传输服务器使用（）协议发送邮件。

A.HTTPB.SMTPC.TCPD.FTPE.POP3

9.不能在Linux上使用的网页浏览器是（）。

A.InternetExploreB.NetscapeC.OperaD.FirefoxE.Mozilla

10.一位艺术史学家有20000幅1024*768的真彩色图像，如果将这些图像以位图形式保存在CD光盘上（一张CD光盘的容量按600M计算），大约需要（）张CD光盘。

A.1B.10C.100D.1000E.10000

二、不定项选择题（共10题，每题1.5分，共计15分。

多选或少选均不得分）。

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

A.（AB∧）∨（CD∧）B.（（AB∧）C∨）D∧C.A∧（（BC∨）D∨）

D.（A∧（BC∨））D∨E.（AB∨）∧（CD∨）

12.（3725）8+（B）16的运算结果是（）。

A.（3736）8B.（2016）10C.（11111100000）2D.（3006）10E.（7E0）16

13.二叉树T的宽度优先遍历序列为ABCDEFGHI，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（）。

A.AB.BC.CD.DE.F

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

A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,c,b,d,f,g

D.d,c,f,e,b,a,gE.g,e,f,d,c,b,a

15.下列外设接口中可以通过无线连接的方式连接设备的是（）。

A.USB2.0高速版B.红外C.蓝牙D.串口E.IEEE802.11g无线网卡

16.处理器A每秒处理的指令数是处理器B的2倍。

某一特定程序P分别编译为处理器A和处理器B的指令，编译结果处理器A的指令数是处理器B的4倍。

已知程序P的算法时间复杂度为O（n2），如果处理器A执行程序P时能在一小时内完成的输入规模为n，则处理器B执行程序P时能在一小时内完成的输入规模为（）。

A.4*nB.2*nC.nD.n/2E.n/4

17.以下哪个（些）不是计算机的输出设备（）。

A.鼠标B.显示器C.键盘D.扫描仪E.绘图仪

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

A.硬盘B.寄存器C.显存D.内存E.高速缓存

19.下列活动中属于信息学奥赛系列活动的是（）。

A.NOIPB.NOIC.IOID.冬令营E.国家队选拔赛

20.下列关于高级语言的说法正确的有（）。

A.Ada是历史上的第一个高级语言B.Pascal和C都是编译执行的高级语言

C.C++是历史上的第一个支持面向对象的语言D.编译器将高级语言程序转变为目标代码

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

三．问题求解（请在空格处填上答案，每空5分，共计10分）

1.将数组{32,74,25,53,28,43,86,47}中的元素按从小到大的顺序排列，每次可以交换任

意两个元素，最少需要交换次。

2.取火柴游戏的规则如下：

一堆火柴有N根，A、B两人轮流取出。

每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。

如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。

当N分别为100，200，300，400，500时，先取者有无必胜策略的标记顺序为（回答应为一个由0和/或1组成的字符串）。

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

==================PASCAL语言==================

1．var

a,b,c,p,q:

integer;

r:

array[0..2]ofinteger;

begin

read（a,b,c）;

p:

=adivbdivc;

q:

=b-c+a+p;

r[0]:

=a*pdivq*q;

r[1]:

=r[0]*（r[0]-300）;

if（3*q-pmod3<=r[0]）and（r[2]=r[2]）then

r[1]:

=r[r[0]divpmod2]

elser[1]:

=qmodp;

writeln（r[0]-r[1]）;

end.

输入：

10073

输出：

2．var

a:

array[1..50]ofinteger;

n,i,sum:

integer;

procedurework（p,r:

integer）;

var

i,j,temp:

integer;

begin

ifp

i:

=p-1;

forj:

=ptor-1do

ifa[j]>=a[r]thenbegin

inc（i）;

temp:

=a[i];a[i]:

=a[j];a[j]:

=temp;

end;

temp:

=a[i+1];a[i+1]:

=a[r];a[r]:

=temp;

work（p,i）;

work（i+2,r）;

end;

end;

begin

read（n）;

fori:

=1tondoread（a[i]）;

work（1,n）;

fori:

=1ton-1dosum:

=sum+abs（a[i+1]-a[i]）;

writeln（sum）;

end.

输入：

1023435123453123434561232-100

输出：

3．var

str:

string;

len,i,j:

integer;

nchr:

array[0..25]ofinteger;

mmin:

char;

begin

mmin:

='z';

readln（str）;

len:

=length（str）;

i:

=len;

whilei>=2dobegin

ifstr[i-1]

dec（i）;

end;

ifi=1thenbegin

writeln（'Noresult!

'）;

exit;

end;

forj:

=1toi-2dowrite（str[j]）;

fillchar（nchr,sizeof（nchr）,0）;

forj:

=itolendobegin

if（str[j]>str[i-1]）and（str[j]

mmin:

=str[j];

inc（nchr[ord（str[j]）-ord（'a'）]）;

end;

dec（nchr[ord（mmin）-ord（'a'）]）;

inc（nchr[ord（str[i-1]）-ord（'a'）]）;

write（mmin）;

fori:

=0to25do

forj:

=1tonchr[i]do

write（chr（i+ord（'a'）））;

writeln;

end.

输入：

zzyzcccbbbaaa

输出：

4.var

n:

longint;

functiong（k:

longint）:

longint;

begin

ifk<=1theng:

=k

elseg:

=（2002*g（k-1）+2003*g（k-2））mod2005;

end;

begin

read（n）;

writeln（g（n））;

end.

输入：

2005

输出：

　==================C语言==================

1．#include

intmain（）{

inta,b,c,p,q,r[3];

scanf（“%d%d%d”,&a,&b,&c）;

p=a/b/c;

q=b–c+a+p;

r[0]=a*p/q*q;

r[1]=r[0]*（r[0]–300）;

if（3*q–p%3<=r[0]&&r[2]==r[2]）

r[1]=r[r[0]/p%2];

else

r[1]=q%p;

printf（“%d\n”,r[0]–r[1]）;

return0;

}

输入：

10073

输出：

2．#include

#include

inta[50];

voidwork（intp,intr）{

if（p

inti=p-1,j,temp;

for（j=p;j

if（a[j]>=a[r]）{

i++;

temp=a[i];a[i]=a[j];a[j]=temp;

}

}

temp=a[i+1];a[i+1]=a[r];a[r]=temp;

work（p,i）;

work（i+2,r）;

}

}

intmain（）{

intn,i,sum=0;

scanf（"%d",&n）;

for（i=0;i

work（0,n-1）;

for（i=0;i

printf（"%d\n",sum）;

return0;

}

输入：

1023435123453123434561232-100

输出：

3．#include

#include

intmain（）{

charstr[60];

intlen,i,j,chr[26];

charmmin='z';

scanf（"%s",str）;

len=strlen（str）;

for（i=len-1;i>=1;i--）

if（str[i-1]

if（i==0）{

printf（"Noresult!

\n"）;

return0;

}

for（j=0;j

memset（chr,0,sizeof（chr））;

for（j=i;j

if（str[j]>str[i-1]&&str[j]

mmin=str[j];

chr[str[j]-'a']++;

}

chr[mmin-'a']--;

chr[str[i-1]-'a']++;

putchar（mmin）;

for（i=0;i<26;i++）

for（j=0;j

putchar（i+'a'）;

putchar（'\n'）;

return0;

}

输入：

zzyzcccbbbaaa

输出：

4.#include

longg（longk）{

if（k<=1）returnk;

return（2002*g（k-1）+2003*g（k-2））%2005;

}

intmain（）{

longn;

scanf（"%ld",&n）;

printf（"%ld\n",g（n））;

return0;

}

输入：

2005

输出：

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

==================PASCAL语言==================

1．木材加工

题目描述:

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有

剩余），需要得到的小段的数目是给定的。

当然，我们希望得到的小段越长越好，你的任务

是计算能够得到的小段木头的最大长度。

木头长度的单位是cm。

原木的长度都是正整数，我们要求切割得到的小段木头的长度

也是正整数。

输入:

第一行是两个正整数N和K（1≤N≤10000，1≤K≤10000），N是原木的数目，

K是需要得到的小段的数目。

接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。

输出:

输出能够切割得到的小段的最大长度。

如果连1cm长的小段都切不出来，输出”0”。

输入样例:

37

232

124

456

输出样例:

114

程序：

var

n,k:

integer;

len:

array[1..10000]ofinteger;

i,left,right,mid:

integer;

functionisok（t:

integer）:

boolean;

var

num,i:

integer;

begin

num:

=0;

fori:

=1tondobegin

ifnum>=kthenbreak;

num:

=①;

end;

if②thenisok:

=true

elseisok:

=false;

end;

begin

readln（n,k）;

right:

=0;

fori:

=1tondobegin

readln（len[i]）;

ifright

=len[i];

end;

inc（right）;

③;

while④

mid:

=（left+right）div2;

if⑤thenright:

=mid

elseleft:

=mid;

end;

writeln（left）;

end.

2．N叉树

题目描述:

我们都了解二叉树的先根遍历，中根遍历和后根遍历。

当知道先根遍历的结果和中根遍

历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍

历结果，二叉树也是唯一确定的。

但是如果只知道先根遍历和后根遍历的结果，二叉树就不

是唯一的了。

但是我们可以计算满足条件的不同二叉树一共有多少个。

这不是一个很困难的

问题，稍微复杂一点，我们把这个问题推广到N叉树。

我们用小写英文字母来表示N叉树的结点，不同的结点用不同的字母表示。

比如，对

于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以

得到6个不同的4叉树（如下图）。

输入:

输入数据包括3行。

第一行是一个正整数N（2≤N≤20），表示我们要考虑N叉树。

第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。

输出:

输出不同的N叉树的数目。

题目中给的数据保证得到的结果小于2

31

。

输入样例:

4

abdefgc

defgbca

输出样例:

6

程序：

var

str1,str2:

string;

N,len:

integer;

com:

array[0..100,0..100]oflongint;

functiongetcom（x,y:

integer）:

longint;

begin

if（y=0）or（x=y）then①

elseifcom[x][y]<>0thengetcom:

=com[x][y]

elsebegin

com[x][y]:

=getcom（x-1,y）+②;

getcom:

=com[x][y];

end;

end;

functioncount（a,b,c:

integer）:

longint;

var

sum:

longint;

k,s,t,p:

integer;

begin

sum:

=1;k:

=0;s:

=a+1;t:

=c;

ifa=bthencount:

=1

elsebegin

whiles<=bdobegin

p:

=t;

whilestr1[s]<>str2[t]doinc（t）;

sum:

=sum*count（s,s+t-p,p）;

s:

=③;

④;inc（k）;

end;

count:

=⑤*getcom（N,k）;

end;

end;

begin

readln（N）;readln（str1）;readln（str2）;

len:

=length（str1）;

writeln（count（⑥））;

end.

　==================C语言==================

1．木材加工

题目描述:

木材厂有一些原木，现在想把这些木头切割成一些长度相同的小段木头（木头有可能有

剩余），需要得到的小段的数目是给定了的。

当然，我们希望得到的小段越长越好，你的任

务是计算能够得到的小段木头的最大长度。

木头长度的单位是cm。

原木的长度都是正整数，我们要求切割得到的小段木头的长度

也是正整数。

输入:

第一行是两个正整数N和K（1≤N≤10000，1≤K≤10000），N是原木的数目，

K是需要得到的小段的数目。

接下来的N行，每行有一个1到10000之间的正整数，表示一根原木的长度。

输出:

输出能够切割得到的小段的最大长度。

如果连1cm长的小段都切不出来，输出”0”。

输入样例:

37

232

124

456

输出样例:

114

程序：

#include

intn,k,len[10000];

intisok（intt）{

intnum=0,i;

for（i=0;i

if（num>=k）break;

num=①;

}

if（②）return1;

elsereturn0;

}

intmain（）{

inti,left,right,mid;

scanf（"%d%d",&n,&k）;

right=0;

for（i=0;i

scanf（"%d",&（len[i]））;

if（right

}

right++;

③;

while（④

mid=（left+right）/2;

if（⑤）right=mid;

elseleft=mid;

}

printf（"%d\n",left）;

return0;

}

2．N叉树

题目描述:

我们都了解二叉树的先根遍历，中根遍历和后根遍历。

当知道先根遍历的结果和中根遍

历结果的时候，我们可以唯一的确定二叉树；同样的，如果知道了后根遍历的结果和中根遍

历结果，二叉树也是唯一确定的。

但是如果只知道先根遍历和后根遍历的结果，二叉树就不

是唯一的了。

但是我们可以计算满足条件的不同二叉树的一共有多少个。

这不是一个很困难

的问题，稍微复杂一点，我们把这个问题推广到N叉树。

我们用小写英文字母来表示N叉树的结点，不同的结点用不同的字母表示。

比如，对

于4叉树，如果先根遍历的结果是abdefgc，后根遍历的结果是defgbca，那么我们可以

得到6个不同的4叉树（如下图）。

输入:

输入数据包括3行。

第一行是一个正整数N（1≤N≤20），表示我们要考虑N叉树。

第二行和第三行分别是两个字符串序列，分别表示先根遍历和后根遍历的结果。

输出:

输出不同的N叉树的数目。