noip信息学联赛2019模拟试卷(四).doc

(完整版)noip信息学联赛2019模拟试卷(四)第二十五届全国青少年信息学奥林匹克联赛初赛（普及组 C+语言试题）竞赛时间：2019年10月13日14:3016：30选手注意：l 试题纸共有7页,答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上一律无效。l 不得使用任何电子设备（如计算器、手机、电子词典等)或查阅任何书籍资料一 单项选择题 (共20题，每题1。5分，共计30分。每题有且仅有一个正确答案.）1。(2019）12+（9102）16=：A：(1001100110100111）2B：(116643）8C：（9DA7)16 D:（9DA5）162.图灵奖是信息学的最高奖项,以下获得过图灵奖的中国人是：A：姚期智B:姚期辉C：马云D：马化腾3. 国际信息学奥林匹克竞赛缩写是：A：NOIB：CTSCC：IOID：ACM4。 2。0E3=A：2000B：0.002C：8D:20005.计算201961=A：1B：31C：0D:20196.使用二分算法在一个大小为n（n=4)中寻找第4大的整数所需的时间复杂度为：A：O（1）B：O（nlogn）C：O(logn）D： O（n)7。若设函数f(x)= 1 （x=1,x=2) 3*f(sqrt(x)+f（x/2）+1 （x2） 当x=19时,计算过程中共调用的f（x)个数是（包括调用f(1)，f（2）:注释：此处运算默认下取整A:3B:4C:5D:68。上题函数中f（19）=A：30B:37C:36D：399。第7题中的函数值不可以用以下哪种方法求得：A:动态规划B:分治C：递推D:递归搜索10。以下部件损坏，主机仍可正常工作的是:A:内存条B：硬盘C：显示屏D：显卡11。对一下数据1000, 2，3,5,4，1， 5000进行冒泡排序，共计需交换次数为：A：5B:10C：15D：1812.如果将人体比作计算机，那么人体的记忆中枢相当于以下计算机部件的:A：运算器B：中央处理器C:控制器D：内存13。以下示意图中的数据结构不属于选项中的哪个数据结构:A：大根堆B：无向图C：连通图D：完全二叉树14.dos、unix和windows的共同点是：A:都是硬件B：都是联网系统软件C:都是应用软件D：都已经过时15.html是一种高级语言,以下操作可以查看html代码的是:A：打开浏览器按F11B：运行html.exeC：无法查看D：打开浏览器按F1216.以下关于计算机病毒的说法正确的是:A:防火墙可以防止感染B：通过生物传播C：一旦感染无法破解D：计算机一次感染终身免疫17.c+语言“实数下取整操作是:A:（int)xB：float（x）C：floor（x）D：ceil（x）18.一棵n层二叉树的最多节点数减去最少节点数等于:A：2nB:2n-nC:n2-nD:nlog2(n）-n19。现给出以下程序：includebits/stdc+.husing namespace std；int i，x；int a11=0,10，2,3，5，14，8，20，1,7,1；int main（)cinx；sort（a+1，a+11)；for (i=1；i=10；i+） if (ai=x） break；coutiendl；问若将此程序的输入输出看做函数,则此函数的图像不经过点：A:（0,2)B：（2,4）C：（11，9)D：（21，11）20。上题程序划线部分可替换为:A：coutupper_bound（a，a+10,x）endl;B:coutupper_bound（a+1，a+11,x)endl;C：coutupper_bound(a+1，a+11,x）-aendl；D: coutlower_bound(a+1,a+11，x)-a1includealgorithmusing namespace std；int n,a101,i;int main()cinn；for （i=1；iai；sort(a+1，a+n+1)；n=unique（a+1，a+n+1)a1；coutnendl；for （i=1;i=n;i+) coutai ；coutusing namespace std；long long o=1,minn=10000000,m；struct pa long long s； long long j； string n； long long cost;；pa p10005；int main() while(cinpo.spo.jpo.n） o+; for（int i=1;io;i+) for(int g=1；go;g+） pi.cost+=abs（pi.j-pg.j）*pg.s; if(pi.cost=minn) minn=pi。cost; m=i； coutpm。n pm.costendl； return 0;输入：7 9289 Vladivostok5 8523 Chabarovsk3 5184 Irkutsk8 2213 Yalutorovsk10 0 Moscow输出： 4. #includeusing namespace std;int a500001，b500001,i，n，A，B,l,r,mid；bool check（int mid)int ii,s=0；memcpy(b,a，sizeof（a)）；for (ii=1;ii=n；ii+) bii=mid*A;for (ii=1;ii0） s+=(int）ceil(（double)bii/B）；return s=mid;int main(）scanf（”%d%d%d,n，A，&B）;for （i=1；i=n;i+） scanf（d,&ai)；l=0；r=500010;while （lr）mid=（l+r)/2；if （check（mid） r=mid;else l=mid+1；printf(”%dn，l)；输入：10 2 39 10 3 12 7 4 8 15 9 24输出: 四完善程序 (前8空，每空2分，后4空，每空3分，共28分） 1。逆序对:逆序对的定义是：对于给定的一段正整数序列，逆序对就是序列中aiaj且ij的有序对。逆序对可以用冒泡排序和归并排序求得。试完善以下冒泡排序程序段与归并排序程序.s=0;for (i=1；i=n;i+) for (j=1；j= （1） ;j+) if (ajaj+1) (2） ； +s; coutsendl；/includebits/stdc+。husing namespace std;long long a500001,b500001，s,n；void guibing(long long l，long long r)if （rl=0) return;if (rl=1）if （aral）swap（ar，al）；+s；return；long long mid= （3） ,i=l,j=mid+1,k=l；guibing（l,mid)； (4） ；while ( （5） ） if （aiaj） s+= (6) bk=aj； +k；+j； else bk=ai; +k；+i； for (;i=mid；i+) bk+=ai； for （；j=r;j+) bk+=aj; for (k=l;k=r;k+) （7） ；int main（）long long i；scanf（%ld，n）；for (i=1；i=n;i+) scanf(”%ld”，ai）；guibing(1，n）；printf(%ldn”,s)；return 0;2.石子合并:在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法，计算出将N堆石子合并成1堆的最小得分和最大得分.#includen； for(int i=1;i=n；+i) cinti; t （1) =ti； for(int i=2；i=2n；+i) ti+=ti-1; memset（dp1,0，sizeof（dp1）; for（int i=2n-1； （2） ） for（int j= (3） ；j=2*n；+j) int b=2147483647; for(int k=i；kj；+k)dp1ij=max(dp1ij,dp1ik+dp1k+1j+tj-ti1）; b=min(b, （4) ）; dp2ij=b; int max0=0，min0=10000000; for(int i=1;i=n；+i） max0=max（ (5） ）； min0=min（min0,dp2ii+n1); coutmin0endlmax0=1;-i (3）i+1（4)dp2ik+dp2k+1j+tj-ti1（5）max0,dp1ii+n113