第十九届2013全国青少年信息学奥林匹克联赛初赛试题C解析.doc

该【第十九届2013全国青少年信息学奥林匹克联赛初赛试题C解析 】是由【泰山小桥流水】上传分享，beplayapp体育下载一共【15】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【第十九届2013全国青少年信息学奥林匹克联赛初赛试题C解析 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。精选beplayapp体育下载第十九届全国青少年信息学奥林匹克联赛初赛提升组C++语言试题比赛时间:2013年10月13日14:30~16:30选手注意:试题纸共有12页,答题纸共有2页,满分100分。请在答题纸上作答,写在试题纸上的一律无效。不得使用任何电子设施(如计算器、手机、电子字典等)或查阅任何书本资料。一、单项选择题(共15题,,;每题有且仅有一个正确选项)(a)个字节。(d)。(a)算法有着异曲同工之妙。以前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:?从前有座山,山里有座庙,庙里有个老和尚在给小和尚讲故事:‘以前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事....’?,(d)将热力学中的熵引入信息通讯领域,标记着信息论研究的初步。.·诺伊曼(JohnvonNeumann)(AlanTuring)(LeonhardEuler)·香农(ClaudeShannon),则此中至多有(c)个节点有2个子节点。,假如随意两点之间都存在路径相连,则称其为连通图。右图是一个有5个极点、8条边的连通图。若要使它不再是连通图,起码要删去其中的(a)条边。:F1=1,F2=1,Fn=Fn–1+Fn–2(n≥3)。假如用下边的函数计算斐波那契数列的第n项,则其时间复杂度为(d)。intF(intn){if(n<=2)return1;elsereturnF(n-1)+F(n-2);}(Fn)(1)(n)(n):、小于其右子树上所有节点的值。那么,二叉查找树的(d)是一个有序序列。(2,6,10,17)分别储存到某个地点区间为0~10的哈希表中,假如哈希函数h(x)=(d),将不会产生矛盾,此中amodb表示a除以b的余数。,跟着其不停被分派,地点资源日益枯竭。所以,它正渐渐被使用(d)位地点的IPv6协议所代替。,每一部分内的极点间没有边相连的简单无向图。那么,12个极点的二分图至多有()条边。.()是一种通用的字符编码,它为世界上绝大多数语言设定了统一而且独一的二进制编码,以知足跨语言、跨平台的文本互换。目前它已经收录了超出十万个不一样字符。,不行能()。、m条边的带权有向简单图用Dijkstra算法计算单源最短路时,假如不使用堆或其余优先行列进行优化,()。(mn+n3)(n2)((m+n)logn)((m+n2)logn)(n)表示某个算法输入规模为n时的运算次数。假如T(1)为常数,且有递归式T(n)=2*T(n/2)+2n,那么T(n)=()。ΘΘΘ2Θ2A.(n)B.(nlogn)C.(n)D.(nlogn)二、不定项选择题(共5题,,;每题有一个或多个正确选项,多项选择或少选均不得分),正确计算1,2,,100这100个自然数之和sum(初始值为0)的是()。(i=1;i<=100;i++)=1;sum+=i;while(i>100){sum+=i;i++;}=1;=1;do{do{sum+=i;sum+=i;i++;i++;}while(i<=100);}while(i>100);2.()的均匀时间复杂度为O(nlogn),此中n是待排序的元素个数。,对下边的无向图进行深度优先遍历时(),最后一个遍历到的极点可能是()。4.()属于NP类问题。(输入规模的)指数时间内能够解决的问题FNOIP复赛考试结束后,因()提出的申述将不会被受理。,未提交源程序三、问题求解(共2题,每题5分,合计10分;每题所有答对得5分,没有不得分)。密码是n个数s1,s2,,sn,均为0或1。该系统每次随机生成n个数a1,a2,,an,均为或1,请用户回答(s1a1+s2a2++snan)除以2的余数。假如多次的回答老是正确,即以为掌握密码。该系统以为,即便问答的过程被泄漏,也无助于破解密码——由于用户并无直接发送密码。.精选beplayapp体育下载但是,适得其反。比如,当n=4时,有人窃听了以下5次问答:就破解出了密码s1=_________,s2=_________,s3=_________,s4=_________。,初始时在n号荷叶上。当它某一时刻在k号荷叶上时,下一时刻将等概率地随机跳到1,2,,k号荷叶之一上,直至跳到1号荷叶为止。当n=2时,均匀一共跳2次;当n=3时,。则当n=5时,均匀一共跳_________次。四、阅读程序写结果(共4题,每题8分,合计32分)1.#include#includeusingnamespacestd;intmain(){stringStr;cin>>str;intn=();.精选beplayapp体育下载boolisPlalindrome=true;for(inti=0;iusingnamespacestd;intmain(){inta,b,u,v,i,num;cin>>a>>b>>u>>v;num=0;for(i=a;I<=b;i++)if(((i%u)==0)||((i%v)==0))num++;.精选beplayapp体育下载count<usingnamespacestd;intmain(){constintSIZE=100;intheight[SIZE],num[SIZE],n,ans;cin>>n;for(inti=0;i>height[i];num[i]=1;for(intj=0;j=num[i]))num[i]=num[j]+1;}}ans=0;.精选beplayapp体育下载for(intI=1;ians)ans=num[j];}Cout<#includeusingnamespacestd;constintSIZE=100;intn,m,p,a[SIZE][SIZE],count;voidcolour(intx,inty){Count++;a[x][y]=1;if((x>1)&&(a[x-1][y]==0))colour(x-1,y);.精选beplayapp体育下载if((y>1)&&(a[x][y-1]==0))colour(x,y-1);if((x>n>>m>>p;for(i=1;I<=p;i++){cin>>x>>y;a[x][y]=1;}ans=0;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]==0).