《广东省汕头市金山中学高一信息技术 历年noip初赛试题13》由会员分享，可在线阅读，更多相关《广东省汕头市金山中学高一信息技术 历年noip初赛试题13（13页珍藏版）》请在金锄头文库上搜索。
1、广东省汕头市金山中学高一信息技术 历年NOIP初赛试题13提高组Pascal语言试题选手注意：l 试题纸共12页，答题纸共2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。l 不得使用任何电子试备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、 单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）1 一个32位整型变量占用（ ）个字节。A4B8C32D1282 二进制数11.01在十进制下是（ ）。A3.25B4.125C6.25D11.1253 下面的故事与（ ）算法有着异曲同工之妙。从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有
2、座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事”A枚举B递归C贪心D分治4 1948年，（ ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。A冯诺伊曼(John von Neumann)B图灵（Alan Turing）C欧拉（Leonhard Euler）D克劳德香农（Claude Shannon）5 已知一棵二叉树有2013个节点，则其中至多有（ ）个节点有2个子节点。A1006B1007C1023D10246 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再
3、是连通图，至少要删去其中的（ ）条边。A2B3C4D57 斐波那契数列的定义如下：F1=1，F2=1，Fn=Fn-1+Fn-2（n3）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（ ）。function F(n:longint):longint;beginif 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);until i=100;2 （ ）的平均时间复杂度为O(n log n)，其中n是待排序的元素个数。
4、A快速排序B插入排序C冒泡排序D归并排序3 以A0作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ ）。AA1BA2CA3DA44 （ ）属于NP类问题。A存在一个P类问题B任何一个P类问题C任何一个不属于P类的问题D任何一个在（输入规模的）指数时间内能够解决的问题5 CCF NOIP复赛考试结束后，因（ ）提出的申诉将不会被受理。A源程序文件名大小写错误B源程序保存在指定文件夹以外的位置C输出文件的文件名错误D只提交了可执行文件，未提交源程序三、 问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分）1 某系统自称使
5、用了一种防窃听的方式验证用户密码。密码是n个数s1，s2，sn，均为0或1。该系统每次随机生成n个数a1，a2，an，均为0或1，请用户回答（s1a1+s2a2+snan）除以2的余数。如果多次的回答总是正确，即认为掌握密码。该系统认为，即使问答的过程被泄露，也无助于破解密码因为用户并没有直接发送密码。然而，事与愿违。例如，当n=4时，有人窃听了以下5次问答：问答编号系统生成的n个数掌握密码的用户的回答a1a2a3a4111001200110301100411100510000就破解出了密码s1= ，s2= ，s3= ，s4= 。2 现有一只青蛙，初始时在n号荷叶上。当它某一时刻在k号荷叶上时
6、，下一时刻将等概率地随机跳到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;for i:=1 to (n idv 2) dobeginif (stristrn-i+1) thenisPlalindrome:=false;end;if (isPlalind
7、rome) thenwriteln(Yes)elsewriteln(No);end.输入：adceecba输出： 2 vara,b,u,v,I,num:integer;beginreadln(a,b,u,v);num:=0;for i:=a to b dobeginif (I mod u=0)or(I mod v=0) theninc(num);end;writeln(num);end.输入：1 1000 10 15输出： 3 const SIZE=100;varn,ans,I,j:integer;height,num:array1.SIZE of integer;beginread(n);f
8、or i:=1 to n dobeginread(heighti);numi:=1;for j:=1 to i-1 dobeginif (heightj=numi) thennumi:=numj+1;end;end;ans:=0;for i:=1 to n dobeginif (numians) thenans:=ans+numi;end;writeln(ans);end.输入：83 2 5 11 12 7 4 10输出： 4 const SIZE=100;varn,m,p,count,ans,x,y,I,j:integer;a:array1.SIZE,1.SIZE of integer;pr
9、ocedure colour(x,y:integer);begininc(count);axy:=1;if (x1)and(ax-1y=0) thencolour(x-1,y);if (y1)and(axy-1=0) thencolour(x,y-1);if (xn)and(ax+1y=0) thencolour(x+1,y);if (ym)and(axy+1=0) thencolour(x,y+1);end;beginfillchar(a,sizeof(a),0);readln(n,m,p);for i:=1 to p dobeginread(x,y);axy:=1;end;ans:=0;for i:=1 to n dofor j:=1 to m doif aij=0 thenbegincount:=0;colour(i,j);if (anscount) thenans:=count;end;writeln(ans);end.输入：6 5 91 42 32 43 24 14 34 55 46 4输出： 五、 完善程序（第1题15分，第2题13分，共计28分）1 （序列重排）全局数组变量a
