1、十九届全国青少信息学奥林匹克联赛提高组初赛试题第十九届全国青少年信息学奥林匹克联赛初赛提高组Pascal语言试卷竞赛时间：2013年10月13日14：3016：30选手注意： 试卷纸共12页，答题纸共2页，满分100分。请在答题纸上作答，写在试卷纸上的一律无效。 不得使用任何电子试备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）1一个32位整型变量占用（ ）个字节。A4 B8 C32 D1282二进制数11.01在十进制下是（ ）。A3.25 B4.125 C6.25 D11.1253下面的故事与（ ）算法有
2、着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事”A枚举 B递归 C贪心 D分治41948年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。A冯诺伊曼(John von Neumann) B图灵（Alan Turing）C欧拉（Leonhard Euler） D克劳德香农（Claude Shannon）5已知一棵二叉树有2013个节点，则其中至多有（ ）个节点有2个子节点。A1006 B1007 C1023 D10246在一个有向图中，如果任意
3、两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（ ）条边。A2 B3 C4 D57斐波那契数列的定义如下：F1=1，F2=1，Fn=Fn-1+Fn-2（n3）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ ）。function F(n:longint):longint。begin if n100 dobegin sum:=sum+I。 inc(i)。end。Ci:=1。repeat sum:=sum+I。 inc(i)。until i100。Di:=1。repeat sum:=sum+I。 inc(i)。un
4、til i=100。2（ ）的平均时间复杂度为O(n log n)，其中n是待排序的元素个数。A快速排序 B插入排序 C冒泡排序 D归并排序3以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ ）。AA1 BA2 CA3 DA44（ ）属于NP类问题。A存在一个P类问题B任何一个P类问题C任何一个不属于P类的问题D任何一个在（输入规模的）指数时间内能够解决的问题5CCF NOIP复赛考试结束后，因（ ）提出的申诉将不会被受理。A源程序文件名大小写错误B源程序保存在指定文件夹以外的位置C输出文件的文件名错误D只提交了可执行文件，未提交
5、源程序三、问题求解（共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个数掌握密码的用户的回答a1a2a3a4111001200110301100411100510000就破解出了密码s1=
6、，s2=，s3=，s4=。2 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时，下一时刻将等概率地随机跳到1，2，k号荷尔蒙叶之一上，直至跳到1号荷叶为止。当n=2时，平均一共跳2次；当n=3时，平均一共跳2.5次。则当n=5时，平均一共跳次。四、阅读程序写结果（共4题，每题8分，共计32分）1varn,i:integer。str:string。isPlalindrome:Boolean。begin readln(str)。 n:=Length(str)。 isPlalindrome:=true。 for i:=1 to (n idv 2) do begin if (stristr
7、n-i+1) then isPlalindrome:=false。 end。 if (isPlalindrome) then writeln(Yes) else writeln(No)。end.输入：adceecba输出：2vara,b,u,v,I,num:integer。begin readln(a,b,u,v)。num:=0。for i:=a to b dobegin if (I mod u=0)or(I mod v=0) then inc(num)。end。writeln(num)。 end.输入：1 1000 10 15输出：3const SIZE=100。var n,ans,I,j:
8、integer。height,num:array1.SIZE of integer。begin read(n)。 for i:=1 to n do begin read(heighti)。 numi:=1。 for j:=1 to i-1 do begin if (heightj=numi) then numi:=numj+1。 end。 end。 ans:=0。 for i:=1 to n do begin if (numians) then ans:=ans+numi。 end。 writeln(ans)。 end. 输入： 8 3 2 5 11 12 7 4 10 输出：4const S
9、IZE=100。var n,m,p,count,ans,x,y,I,j:integer。a:array1.SIZE,1.SIZE of integer。procedure colour(x,y:integer)。begin inc(count)。 axy:=1。 if (x1)and(ax-1y=0) then colour(x-1,y)。 if (y1)and(axy-1=0) then colour(x,y-1)。 if (xn)and(ax+1y=0) then colour(x+1,y)。 if (ym)and(axy+1=0) then colour(x,y+1)。end。begin
10、 fillchar(a,sizeof(a),0)。 readln(n,m,p)。 for i:=1 to p do begin read(x,y)。 axy:=1。 end。 ans:=0。 for i:=1 to n do for j:=1 to m do if aij=0 then begin count:=0。 colour(i,j)。 if (anscount) then ans:=count。 end。 writeln(ans)。end.输入：6 5 91 42 32 43 24 14 34 55 46 4输出：五、完善程序（第1题15分，第2题13分，共计28分）1（序列重排）全局
11、数组变量a定义如下：constint SIZE=100。int aSIZE,n。它记录着一个长度为n的序列a1，a2，an。现在需要一个函数，以整数p(1pn)为参数，实现如下功能：将序列a的前p个数与后n-p个数对调，且不改变这p个数（或n-p个数）之间的相对位置。例如，长度为5的序列1，2，3，4，5，当p=2时重排结果为3，4，5，1，2。有一种朴素的算法可以实现这一需求，其时间复杂度为O(n)、空间复杂度为O(n)：procedure swap1(p:longint)。var I,j:longint。 b:array1.SIZE of longint。begin for i:=1 to
12、 p do b （1） :=ai。 /（2分） for i:=p+1 to n do bi-p:=ai。 for i:=1 to n do ai:=bi。end。我们也可以用时间换空间，使用时间复杂度为O(n2)、空间复杂度为O(1)的算法：procedure swap2(p:longint)。var I,j,temp:longint。begin for i:=p+1 to n do begin temp:=ai。 for j:=I downto （2） do /（2分） aj:=aj-1。 （3） :=temp。 /（2分） end。end。事实上，还有一种更好的算法，时间复杂度为O(n)、
13、空间复杂度为O(1)。procedure swap3(p:longint)。var start1,end1,start2,end2,I,j,temp:longint。begin start1:=1。 end1:=p。 start2:=p+1。 end2:=n。 while true do begin i:=star1。 j:=start2。 while (i=end1)and(j=end2) do begin temp:=ai。 ai:=aj。 aj:=temp inc(i)。 inc(j)。 end。 if i=end1 then start1:=i else if （4） then /（3
14、分） begin start1:= （5） 。 /（3分） end1:= （6） 。 /（3分） start2:=j。 end else break。 end。end。2（两元序列）试求一个整数序列中，最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长，输出任意一个即可。例如，序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中，有两段满足条件的最长子序列，长度均为7，分别用下划线和上划线标出。program two。const SIZE=100。var n,I,j,cur1,cur2,count1,count2, ans_length,ans_start,ans_end
15、:longint。 /cur1,cur2分别表示当前子序列中的两个不同整数 /count1,count2分别表示cur1，cur2在当前子序列中出现的次数 a:array1.SIZE of longint。begin readln(n)。 for i:=1 to n do read(ai)。 i:=1。 j:=1。 /i，j分别表示当前子序列的首尾，并保证其中至多有两个不同整数 while (j=n)and(aj=ai) do inc(j)。 cur1:=ai。 cur2:=aj。 count1:= （1） 。 /（3分） count2:=1。 ans_length:=j-i+1。 while
16、 j0 do begin while count20 do begin if ai=cur1 then dec(count1) else dec(count2)。 inc(i)。 end。 cur2:=aj。 count2:=1。 end else begin while count10 do begin if ai=cur1 then （3） /（2分） else （4） 。 /（2分） inc(i)。 end。 （5） 。 /（3分） count1:=1。 end。 end。 if (ans_lengthj-i+1) then begin ans_length:=j-i+1。 ans_start:=I。 ans_end:=j。 end。 end。 for i:=ans_start to ans_end do write(ai, )。end.
