十九届全国青少信息学奥林匹克联赛提高组初赛试题.docx
《十九届全国青少信息学奥林匹克联赛提高组初赛试题.docx》由会员分享，可在线阅读，更多相关《十九届全国青少信息学奥林匹克联赛提高组初赛试题.docx（16页珍藏版）》请在冰点文库上搜索。
十九届全国青少信息学奥林匹克联赛提高组初赛试题
第十九届全国青少年信息学奥林匹克联赛初赛
提高组Pascal语言试卷
竞赛时间：
2013年10月13日14：
30～16：
30
选手注意：
●试卷纸共12页，答题纸共2页，满分100分。
请在答题纸上作答，写在试卷纸上的一律无效。
●不得使用任何电子试备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）
1．一个32位整型变量占用（）个字节。
A．4B．8C．32D．128
2．二进制数11.01在十进制下是（）。
A．3.25B．4.125C．6.25D．11.125
3．下面的故事与（）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：
“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：
‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事…………………………’”
A．枚举B．递归C．贪心D．分治
4．1948年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A．冯·诺伊曼（JohnvonNeumann）B．图灵（AlanTuring）
C．欧拉（LeonhardEuler）D．克劳德·香农（ClaudeShannon）
5．已知一棵二叉树有2013个节点，则其中至多有（）个节点有2个子节点。
A．1006B．1007C．1023D．1024
6．在一个有向图中，如果任意两点之间都存在路径相连，则称其为连通图。
右图是一个有5个顶点、8条边的连通图。
若要使它不再是连通图，至少要删去其中的（）条边。
A．2B．3C．4D．5
7．斐波那契数列的定义如下：
F1=1，F2=1，Fn=Fn-1+Fn-2（n≥3）。
如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（）。
functionF（n:
longint）:
longint。
begin
ifn<=2then
F:
=1
else
F:
=F（n-1）+F（n-2）。
end。
A．O
（1）B．O（n）C．O（n2）D．O（Fn）
8．二叉查找树具有如下性质：
每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。
那么，二叉查找树的（）是一个有序序列。
A．先序遍历B．中序遍历C．后序遍历D．宽度优先遍历
9．将（2，6，10，17）分别存储到某个地址区间为0～10的哈希表中，如果哈希函数h（x）=（），将不会产生冲突，其中amodb表示a除以b的余数。
A．xmod11B．x2mod11
C．2xmod11D．
mod11，其中
表示
下取整
10．IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。
因此，它正逐渐被使用（）位地址的IPv6协议所取代。
A．40B．48C．64D．128
11．二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。
那么12个顶点的二分图至多有（）条边。
A．18B．24C．36D．66
12．（）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。
目前它已经收录了超过十万个不同字符。
A．ASCIIB．UnicodeC．GBK2312D．BIG5
13．把64位非零浮点数强制转换成32位浮点数后，不可能（）。
A．大于原数B．小于原数
C．等于原数D．与原数符号相反
14．对一个n个顶点、m条边的带权有向简单图用Dijkstr算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（）。
A．O（mn+n3）B．O（n2）
C．O（（m+n）logn）D．O（（m+n2）logn）
15．T（n）表示某个算法输入规模为n时的运算次数。
如果T
（1）为常数，且有递归式T（n）=2*T（n/2）+2n，那么T（n）=（）。
A．Θ（n）B．Θ（nlogn）C．Θ（n2）D．Θ（n2logn）
二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分）
1．下列程序中，正确计算1，2，…，100这100个自然数之和sum（初始值为0）的是（）。
A．
fori:
=1to100do
sum:
=sum+I。
B．
i:
=1。
whilei>100do
begin
sum:
=sum+I。
inc（i）。
end。
C．
i:
=1。
repeat
sum:
=sum+I。
inc（i）。
untili>100。
D．
i:
=1。
repeat
sum:
=sum+I。
inc（i）。
untili<=100。
2．（）的平均时间复杂度为O（nlogn），其中n是待排序的元素个数。
A．快速排序B．插入排序C．冒泡排序D．归并排序
3．以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（）。
A．A1B．A2C．A3D．A4
4．（）属于NP类问题。
A．存在一个P类问题
B．任何一个P类问题
C．任何一个不属于P类的问题
D．任何一个在（输入规模的）指数时间内能够解决的问题
5．CCFNOIP复赛考试结束后，因（）提出的申诉将不会被受理。
A．源程序文件名大小写错误
B．源程序保存在指定文件夹以外的位置
C．输出文件的文件名错误
D．只提交了可执行文件，未提交源程序
三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分）
1．某系统自称使用了一种防窃听的方式验证用户密码。
密码是n个数s1，s2，…，sn，均为0或1。
该系统每次随机生成n个数a1，a2，…，an，均为0或1，请用户回答（s1a1+s2a2+…+snan）除以2的余数。
如果多次的回答总是正确，即认为掌握密码。
该系统认为，即使问答的过程被泄露，也无助于破解密码——因为用户并没有直接发送密码。
然而，事与愿违。
例如，当n=4时，有人窃听了以下5次问答：
问答编号
系统生成的n个数
掌握密码的用户的回答
a1
a2
a3
a4
1
1
1
0
0
1
2
0
0
1
1
0
3
0
1
1
0
0
4
1
1
1
0
0
5
1
0
0
0
0
就破解出了密码s1=，s2=，s3=，s4=。
2．现有一只青蛙，初始时在n号荷叶上。
当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1，2，…，k号荷尔蒙叶之一上，直至跳到1号荷叶为止。
当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。
则当n=5时，平均一共跳次。
四、阅读程序写结果（共4题，每题8分，共计32分）
1．var
n,i:
integer。
str:
string。
isPlalindrome:
Boolean。
begin
readln（str）。
n:
=Length（str）。
isPlalindrome:
=true。
fori:
=1to（nidv2）do
begin
if（str[i]<>str[n-i+1]）then
isPlalindrome:
=false。
end。
if（isPlalindrome）then
writeln（‘Yes’）
else
writeln（‘No’）。
end.
输入：
adceecba
输出：
2．var
a,b,u,v,I,num:
integer。
begin
readln（a,b,u,v）。
num:
=0。
fori:
=atobdo
begin
if（Imodu=0）or（Imodv=0）then
inc（num）。
end。
writeln（num）。
end.
输入：
110001015
输出：
3．constSIZE=100。
var
n,ans,I,j:
integer。
height,num:
array[1..SIZE]ofinteger。
begin
read（n）。
fori:
=1tondo
begin
read（height[i]）。
num[i]:
=1。
forj:
=1toi-1do
begin
if（（height[j]=num[i]））then
num[i]:
=num[j]+1。
end。
end。
ans:
=0。
fori:
=1tondo
begin
if（num[i]>ans）then
ans:
=ans+num[i]。
end。
writeln（ans）。
end.
输入：
8
32511127410
输出：
4．constSIZE=100。
var
n,m,p,count,ans,x,y,I,j:
integer。
a:
array[1..SIZE,1..SIZE]ofinteger。
procedurecolour（x,y:
integer）。
begin
inc（count）。
a[x][y]:
=1。
if（x>1）and（a[x-1][y]=0）then
colour（x-1,y）。
if（y>1）and（a[x][y-1]=0）then
colour（x,y-1）。
if（xcolour（x+1,y）。
if（ycolour（x,y+1）。
end。
begin
fillchar（a,sizeof（a）,0）。
readln（n,m,p）。
fori:
=1topdo
begin
read（x,y）。
a[x][y]:
=1。
end。
ans:
=0。
fori:
=1tondo
forj:
=1tomdo
ifa[i][j]=0then
begin
count:
=0。
colour（i,j）。
if（ansans:
=count。
end。
writeln（ans）。
end.
输入：
659
14
23
24
32
41
43
45
54
64
输出：
五、完善程序（第1题15分，第2题13分，共计28分）
1．（序列重排）全局数组变量a定义如下：
constintSIZE=100。
inta[SIZE],n。
它记录着一个长度为n的序列a[1]，a[2]，…，a[n]。
现在需要一个函数，以整数p（1≤p≤n）为参数，实现如下功能：
将序列a的前p个数与后n-p个数对调，且不改变这p个数（或n-p个数）之间的相对位置。
例如，长度为5的序列1，2，3，4，5，当p=2时重排结果为3，4，5，1，2。
有一种朴素的算法可以实现这一需求，其时间复杂度为O（n）、空间复杂度为O（n）：
procedureswap1（p:
longint）。
var
I,j:
longint。
b:
array[1..SIZE]oflongint。
begin
fori:
=1topdo
b[
（1）]:
=a[i]。
//（2分）
fori:
=p+1tondo
b[i-p]:
=a[i]。
fori:
=1tondo
a[i]:
=b[i]。
end。
我们也可以用时间换空间，使用时间复杂度为O（n2）、空间复杂度为O
（1）的算法：
procedureswap2（p:
longint）。
var
I,j,temp:
longint。
begin
fori:
=p+1tondo
begin
temp:
=a[i]。
forj:
=Idownto
（2）do//（2分）
a[j]:
=a[j-1]。
（3）:
=temp。
//（2分）
end。
end。
事实上，还有一种更好的算法，时间复杂度为O（n）、空间复杂度为O
（1）。
procedureswap3（p:
longint）。
var
start1,end1,start2,end2,I,j,temp:
longint。
begin
start1:
=1。
end1:
=p。
start2:
=p+1。
end2:
=n。
whiletruedo
begin
i:
=star1。
j:
=start2。
while（i<=end1）and（j<=end2）do
begin
temp:
=a[i]。
a[i]:
=a[j]。
a[j]:
=temp
inc（i）。
inc（j）。
end。
ifi<=end1then
start1:
=i
elseif（4）then//（3分）
begin
start1:
=（5）。
//（3分）
end1:
=（6）。
//（3分）
start2:
=j。
end
else
break。
end。
end。
2．
（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。
如有多个子序列并列最长，输出任意一个即可。
例如，序列“11232323311131”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。
programtwo。
constSIZE=100。
var
n,I,j,cur1,cur2,count1,count2,
ans_length,ans_start,ans_end:
longint。
//cur1,cur2分别表示当前子序列中的两个不同整数
//count1,count2分别表示cur1，cur2在当前子序列中出现的次数
a:
array[1..SIZE]oflongint。
begin
readln（n）。
fori:
=1tondo
read（a[i]）。
i:
=1。
j:
=1。
//i，j分别表示当前子序列的首尾，并保证其中至多有两个不同整数
while（j<=n）and（a[j]=a[i]）do
inc（j）。
cur1:
=a[i]。
cur2:
=a[j]。
count1:
=
（1）。
//（3分）
count2:
=1。
ans_length:
=j-i+1。
whilejbegin
inc（j）。
ifa[j]=cur1then
inc（count1）
elseifa[j]=cur2then
inc（count2）
elsebegin
ifa[j-1]=
（2）then//（3分）
whilecount2>0do
begin
whilecount2>0do
begin
ifa[i]=cur1then
dec（count1）
else
dec（count2）。
inc（i）。
end。
cur2:
=a[j]。
count2:
=1。
end
elsebegin
whilecount1>0do
begin
ifa[i]=cur1then
（3）//（2分）
else
（4）。
//（2分）
inc（i）。
end。
（5）。
//（3分）
count1:
=1。
end。
end。
if（ans_lengthbegin
ans_length:
=j-i+1。
ans_start:
=I。
ans_end:
=j。
end。
end。
fori:
=ans_starttoans_enddo
write（a[i],’‘）。
end.
升级会员 