第十九届全国青少年信息学奥林匹克联赛初赛
提高组Pascal语言试题
竞赛时间：2013年10月13日14:30~16:30
选手注意：
●试题纸共有12页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。
●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。
一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）
1.一个32位整型变量占用（A.4B.8）个字节。C.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
CCFNOIP2013初赛提高组Pascal语言试题第1页/共10页
7.斐波那契数列的定义如下：F1=1,F2=1,Fn=Fn–1+Fn-2(n≥3)。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（）。
funtionF(n:longint):longint;beginifn<=2thenF:=1elseF:=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.x2mod11C.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条边的带权有向简单图用Dijkstra算法计算单源最短路时，如果）。
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)
CCFNOIP2013初赛提高组Pascal语言试题第2页/共10页
二、不定项选择题（共5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分）
1.下列程序中，正确计算1,2,…,100这100个自然数之和sum（初始值为0）的是（）。
A.fori:=1to100dosum:=sum+i;B.i:=1;whilei>100dobeginsum:=sum+i;inc(i);end;C.i:=1;repeatsum:=sum+i;inc(i);untili>100;D.i:=1;repeatsum:=sum+i;inc(i);untili<=100;
2.（）的O(nlogn)，其中n是待排序的元素个数。A.快速排序B.插入排序C.冒泡排序D.归并排序
3.以A0作为起点，对下面的无向图进行无关），最后一个遍历到的顶点可能是（）。
A0
A1A4A3
A.A1
4.A.B.C.D.B.A2C.A32D.A4（）属于NP类问题。存在一个P类问题任何一个P类问题任何一个不属于P类的问题任何一个在（输入规模的）指数时间内能够解决的问题
CCFNOIP2013初赛提高组Pascal语言试题第3页/共10页
5.A.B.C.D.CCFNOIP复赛考试结束后，因（源程序文件名大小写错误源程序保存在指定文件夹以外的位置输出文件的文件名错误只提交了可执行文件，未提交源程序）提出的申诉将不会被受理。
三、问题求解（共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个数掌握密码的问答编号a1a2a3a4用户的回答
就破解出了密码s12342.现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1,2,…,k号荷叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳________次。
四、阅读程序写结果（共4题，每题8分，共计32分）
1.varn,i:integer;str:string;isPlalindrome:boolean;
beginreadln(str);n:=Length(str);isPlalindrome:=true;fori:=1to(ndiv2)dobeginif(str[i]<>str[n-i+1])thenisPlalindrome:=false;end;
第CCFNOIP2013初赛提高组Pascal语言试题4页/共10页
if
elsewriteln('Yes')(isPlalindrome)then
end.writeln('No');
输入：abceecba
输出：_________
2.a,varb,u,v,i,num:integer;
beginreadln(a,numb,
for:=u,v);
begini:=0;atobdo
if(imodu=0)or(imodv=0)thenend;inc(num);
end.writeln(num);
输入：110001015
输出：_________
3.varconstSIZE=100;
n,height,ans,i,numj::array[1..SIZE]integer;ofinteger;beginread(n);forbegini:=1tondo
read(height[i]);num[i]forbeginj:=:=11;toi-1do
ifnum[i]((height[j]:=num[j]+1;<height[i])and(num[j]>=num[i]))end;end;
ans:=0;
CCFNOIP2013第初赛提高组5页/共10Pascal页语言试题then
fori:=1tondobeginif(num[i]>ans)thenans:=num[i];end;writeln(ans);end.
输入：
832511127410输出：_________
4.constSIZE=100;varn,m,p,count,ans,x,y,i,j:integer;a:array[1..SIZE,1..SIZE]ofinteger;procedurecolour(x,y:integer);begininc(count);a[x][y]:=1;if(x>1)and(a[x-1][y]=0)thencolour(x-1,y);if(y>1)and(a[x][y-1]=0)thencolour(x,y-1);if(x<n)and(a[x+1][y]=0)thencolour(x+1,y);if(y<m)and(a[x][y+1]=0)thencolour(x,y+1);end;
beginfillchar(a,sizeof(a),0);readln(n,m,p);fori:=1topdobeginread(x,y);a[x][y]:=1;end;ans:=0;fori:=1tondoforj:=1tomdoifa[i][j]=0then
CCFNOIP2013初赛提高组Pascal语言试题第6页/共10页
begincount:=0;colour(i,j);if(ans<count)thenans:=count;end;writeln(ans);end.
输入：
659142324324143455464输出：_________
五、完善程序（第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);vari,j:longint;b:array[1..SIZE]oflongint;beginfor
do:=a[i];//（2分）forndob[i-p]:=a[i];
fori:=1tondo
CCFNOIP2013初赛提高组Pascal语言试题第7页/共10页
end;a[i]:=b[i];
我们也可以用时间换空间，使用时间复杂度为O(n2)、空间复杂度为O(1)的算法：procedureswap2(p:longint);vari,j,temp:longint;beginfori:=p+1tondobegintemp:=a[i];forj:=idownto
do//（2分）
a[j-:=temp;//（2分）end;
事实上，还有一种更好的算法，时间复杂度为O(n)、空间复杂度为O(1)：procedureswap3(p:longint);varstart1,end1,start2,end2,i,j,temp:longint;beginstart1:=1;end1:=p;start2:=p+1;end2:=n;whiletruedobegini:=start1;j:=start2;while(i<=end1)and(j<=end2)dobegintemp:=a[i];a[i]:=a[j];a[j]:=temp;inc(i);inc(j);end;ifi<=end1then
elseifthen//（3分）begin
CCFNOIP2013初赛提高组Pascal语言试题第8页/共10页
endelsebreak;end;end;start1
//（3分）end1:=//（3分）start22.（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长，输出任意一个即可。例如，序列“11232323311131”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。programtwo;
constSIZE=100;
varn,i,j,cur1,cur2,count1,count2,ans_length,ans_start,ans_end:longint;//cur1,cur2分别表示当前子序列中的两个不同整数//count1,count2分别表示cur1,cur2在当前子序列中出现的次数a:array[1..SIZE]oflongint;
beginreadln(n);fori:=1tondoread(a[i]);i:=1;j:=1;//i,j分别表示当前子序列的首尾，并保证其中至多有两个不同整数while(j<=n)
and(a[j]=a[i])doinc(j);cur1:=a[i];cur2:=count1:=//（3分）count2:=ans_length:=j-i+1;whilej<ndobegininc(j);ifa[j]=cur1theninc(count1)elseifa[j]=cur2then
CCFNOIP2013初赛提高组Pascal语言试题第9页/共10页
inc(count2)elsebeginifa[j-1]=
then//（3分）beginwhilecount2>0dobeginifa[i]=cur1thendec(count1)elsedec(count2);inc(i);end;cur2:=a[j];count2:=1;endelsebeginwhilecount1>0dobeginif
then//
（2分）//（
2分）//（3分）1;end;end;if(ans_length<j-i+1)thenbeginans_length:=j-i+1;ans_start:=i;ans_end:=j;end;end;fori:=ans_starttoans_enddowrite(a[i],'');end.
CCFNOIP2013初赛提高组Pascal语言试题第10页/共10页
www.99jianzhu.com/包含内容：建筑图纸、PDF/word/ppt 流程，表格，案例，最新,免费下载,施工方案、工程书籍、建筑论文、合同表格、标准规范、CAD图纸等内容。