NOIP2016年第二十二届全国青少年信息学奥林匹克联赛提高组初赛

1、第二十二届全国青少年信息学奥林匹克联赛初赛提高组PascaI语言试题竞赛时间：2016年10月22日14:3016:30选手注意：试题纸共有13页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上 的一律无效。不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共 15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）1以下不是微软公司出品的软件是（）。A.Powerpoi ntC.EGcel B.Word D.AcrobatReader2如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock字母键A、字母键S和字母键

2、 D的顺序来回按键，即 CapsLock A、S D、S、A、CapsLock A、S、D、S、A、CapsLock A、S、D、S A、，屏幕上输出的第81个字符是字母（）。A.A B.S C.D D.a3. 二进制数 00101100和01010101异或的结果是（）。A.00101000B.01111001C.01000100D.001110004. 与二进制小数0.1相等的八进进制数是（）。A.0.8B.0.4C.0.2D.0.15. 以比较作为基本运算，在N个数中找最小数的最少运算次数为（）。A.N B.N-1C.N2D.IogN6. 表达式aG（b+c）-d的后缀表达形式为（）。A

3、.abcdG+-B.abc+Gd-C.abcG+d-D.-+Gabcd7. 棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（）。A.6B.7C.12D.148. G是一个非连通简单无向图，共有28条边，则该图至少有（）个顶点。A.10B.9C.8D.79. 某计算机的CPU和内存之间的地址总线宽度是32位（bit）,这台计算机最多可以使用（） 的内存。A.2GB B.4GBC.8GBD.16GB10. 有以下程序：vark,n:longint; begin k:=4; n

4、:=0; while n kdo begin inc（n）; ifnmod30the n con ti nue;dec（k）;en d;writein （k, n）;en d.程序运行后的输出结果是（）。A.2,2B.2,3C.3,2D.3,311. 有7个一模一样的苹果，放到3个一样的盘子中，一共有（）种放法。A.7B.8C.21D.3712. Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系 图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这Deina 个社交网站的规则是：如果某人A向他（她）的朋友B分享了某张照片，那么B 就可以对该照片

5、进行评论；如果B评论了该照片，那么他（她）的所有朋友都 可以看见这个评论以及被评论的照片， 但是不能对该照片进行评论（除非A也向他（她）分享了该照片）。现在Lucia 已经上传了一张照片，但是她不想让 Jacob看见这张照片，那么她可以向以下 朋友（）分享该照片。A.Da na,Michael,EveB.Da na,Eve,M on icaC.Michael,Eve,JacobD.Micheal,Peter,Mo nica13. 周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈 负责炒菜。假设做每道菜的顺序都是：先洗菜10分钟，然后切菜10分钟，最后炒菜10分钟。那

6、么做一道菜需要30分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要（）分钟。A.90B.60C.50D.4014. 假设某算法的计算时间表示为递推关系式J E 2T旧皿T（l）=l则算法的时间复杂度为（）。A.O（ ）B.O（Jni）C.O&Hlog ） D.O（ 2）15. 给定含有 n个不同的数的数组L=。如果 L中存在 G（ 1in ）使得G1G2.Gi-1G+1.Gn，则称L是单峰的，并称Gi是L的峰顶”。现在已知L是单峰的， 请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。a. Search（k+

7、1, n）b. Search（1,k-1）c. returnLkSearch（1, n）1. k?n/2?2.ifLkLk-1a ndLkLk+13. then4. elseifLkLk-1a ndLkLk+15. then6. else正确的填空顺序是（）。A.c,a,bB.c,b,a二、不定项选择题（共 或少选均不得分）C.a,b,cD.b,a,c5题，每题1.5分，共计7.5分；每题有一个或多个正确选项，多选1. 以下属于无线通信技术的有（）。A.蓝牙 B.WiFiC.GPRSD.以太网2. 可以将单个计算机接入到计算机网络中的网络接入通讯设备有（）A.网卡B.光驱C.鼠标D显卡3. 下

8、列算法中运用分治思想的有（）。A.快速排序B.归并排序C.冒泡排序D.计数排序4. 下图表示一个果园灌溉系统，有A、B、C、D 四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的有（）。A. B打开，其他都关上C. A打开，其他都关上B. AB都打开，CD都关上D. D打开，其他都关上5参加NOI比赛，以下能带入考场的有（）。A.钢笔B.适量的衣服C.U盘D.铅笔三、问题求解（共 2题，每题5分，共计10分；每题全部答对得 5分，没有部分分）1一个1X 8的方格图形（不可旋转）用黑、白两种颜色填涂每个方格。如果每个方格只能 填涂一种颜色，且不允许两个黑

9、格相邻，共有 种填涂方案。2某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列出了哪些学生参加哪些考试（用表示要参加相应的考试）。最少要安排个不同的考试时间段才能避免冲突？考试学生1学生2学生3学生4学生5学生6学生7通用技术VVV物理VVV化学VV生物VVV历史VVV地理VVV政治VV四、阅读程序写结果(共 4题，每题8分，共计32分)1. vara:array1.6ofl on gi nt=(1,2,3,4,5,6);pi,pj,t,i:lo ngint;beginpi:=1;pj:=6;whilepivpjdobegint:=api;api：=apj;apj:=t;in

10、c(pi);dec(pj);en d;fori:=1to6dowrite(ai,);write In;en d.输出：2. varn ,i,j,k:l ongint;total_le n:array1.100oflo ngint;len: array1.100,1.3oflo ngint;a,b:array1.100,1.100ofchar;c:array1.100ofstri ng100;begini:=0;j:=0;k:=1;readl n(n);fori:=1t ondobeginread In (ci);total_le ni:=le ngth(ci); en d;fori:=1t o

11、ndo begin j:=1;while(ci,j:)do begin ai,k:=ci,j; k:=k+1; in c(j);en d;len i,1:=k-1; ai,k:=chr(0);k:=1;forj:=j+1tototal_le n ido beginbi,k:=ci,j; k:=k+1;en d;len i,2:=k-1; bi,k:=chr(0);k:=1;en d;fori:=1t ondo beginif(le n i,1=le n i,2)then write(NO,) elsebegink:=1;forj:=1tole n i,2do begin ifai,k=bi,j

12、the n k:=k+1;ifkle ni,1the n break;en d;ifj=le n i,2then write(NO,)elsewrite(YES,);en d;en d; write In;en d.输入：3AB:ACDEbFBkBDAR:ACDBrTSARS:SevereAtypicalRespiratoryS yn drome 输出：(注：输入各行前后均无空格)3. fu nction lps(seq:stri ng;i,j:l ongin t):l ongint;varlen 1,le n2:lo ngint;beginifi=jthe neGit(1);ifijthe

13、neGit(O);if(seqi=seqj)the n eGit(lps(seq,i+1,j-1)+2);len 1:=lps(seq,i,j-1);len 2:=lps(seq,i+1,j);ifle n1le n2the neGit(le n1)elseeGit(le n2);en d;varn :lo ngint; seq:stri ng;beginseq:=acmera ndacm;n:=le ngth(seq); write In (lps(seq,1, n);en d.输出：4. varmap:array1.100,1.100oflo ngint; sum,weight,visit

14、:array1.100ofl ongint; n ,i,G,y,a ns,a nsn :lo ngint;proceduredfs (no de:l ongin t);varv,maGw:lo ngint;beginvisit no de:=1;sumno de:=1;maGw:=0;forv:=1to ndobeginif(map nodev=0)or(visitv0)then con ti nue;dfs(v);in c(su mno de,sumv); ifsumvmaGwthe n maGw:=sumv;en d;ifn-sum no demaGwthe nmaGw:=n-sumno

15、de; weight no de:=maGw; en d;beginfillchar(map,sizeof(map),0); fillchar(sum,sizeof(sum),0); fillchar(weight,sizeof(weight),0);fillchar(visit,sizeof(visit),0);readl n(n);fori:=1to n-1dobeginread(G,y);mapG,y:=1;mapy,G:=1;en d;dfs(1);ans:=n;ansn:=O;fori:=1t ondoifweightia nsthe nbeginan s:=weighti;ansn

16、:=i;en d;write ln(ansn，”,a ns);en d.输入：111213242526377871169910输出：五、完善程序(共2题，每题14分，共计28分)1. (交朋友)根据社会学研究表明，人们都喜欢找和自己身高相近的人做朋友。现在有n名身高两两不相同的同学依次走入教室，调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时，这名同学会更想和高的那个人做朋友。比如一名身高为1.80米的同学进入教室时，有一名身高为1.79米的同学和一名身高为1.81米的同学在教室里，那么这名身高为1.80米的同学会更想和身高为1.81米

17、的同学做朋友。对于第一个走入教室的同学我们不做预测。由于我们知道所有人的身高和走进教室的次序，所以我们可以采用离线的做法来解决这样的问题，我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最 相近的人。(第一空2分，其余3分)con stmaG n=20XX00;infin ity=2147483647;varan swer,height,previous ,n eGt:arrayO.maG nofl ongint;ran k:arrayO.maG noflongint;n ,higher,shorter,i:l ongint;proceduresort(l,r:lo ngi

18、n t);varG,i,j,temp:l ongint;beginG:=heightra nk(l+r)div2;i:=l;j:=r;whilei=jdobeginwhileheightra nkiGdodec(j);if (1) the nbegintemp:=ra nki;ra nki:=ra nkj;ra nkj:=temp;in c(i);dec(j);en d;en d;ifirthe nsort(i,r);ifljthe nsort(l,j);en d;beginreadl n(n);fori:=1t ondobeginread(heighti);ran ki:=i;en d;so

19、rt(1, n);fori:=1t ondobeginpreviousra nki:=ra nki-1;121;en d;fori:=n dow nto2dobeginhigher:=infin ity;shorter:=infin ity;ifpreviousiOthe nshorter:=heighti-heightpreviousi;ifneG ti0the n(31;If(4)the nan sweri:=previousielsean sweri:=neGti;n eGtpreviousi:=neGti;(5)_;en d;fori:=2t ondowritel n( i,:,a n

20、sweri);en d.2. (交通中断)有一个小国家，国家内有n座城市和m条双向的道路，每条道路连接着两座不同的城市。其中1号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道，如果只有第i(i1)个城市因地震而导致交通中断时，首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第i个城市而导致从首都出发无法到达某个城市，也认为到达该城市的最短路径长度改变。对于每一个城市i，假定只有第i个城市与外界交通中断，输出有多少个城市会因此导 致到首都的最短路径长度改变。我们采用邻接表的方式存储图的信息，其中headG表示顶点 G的第一条边的编号，neGti

21、表示第i条边的下一条边的编号，pointi表示第i条边的终点，weighti表示第i条边的长度。(第一空2分，其余3分)con stmaG n=6000;maGm=100000;in f=2147483647;varn eGt,poi nt,weight:array1.maGmoflo ngint; head,dist,visit:array1.maG noflongint; queue:arrayO.maG n-1ofl ongint;n, m,i,j,s,t,total,G,y,z,a nswer:l ongint; procedureli nk(G,y,z:l ongin t);begi

22、nin c(total);neGttotal:=headG; headG:=total;poin ttotal:=y;weighttotal:=z;in c(total);neGttotal:=heady; heady:=total;poi nttotal:=G;weighttotal:=z;en d;begintotal:=0;readl n(n, m);fori:=1tomdobeginreadl n(G,y,z);li nk(G,y,z);en d;fori:=1ton dodisti:=inf;(1!;queue1:=1;visit1:=1;s:=1;t:=1;/使用SPFA求出第一个

23、点到其余各点的最短路长度 whiles=tdobeginG:=queuesmodmaG n;j:=headG;whilej0dobeginif (2) the nbegindistpoi ntj:=distG+weightj;if(visitpoi ntj=0)the n beginin c(t);queuetmodmaG n:=po in tj; visitpoi ntj:=1;en d;en d;j:=neGtj;en d;in c(s);en d;fori:=2t ondobeginqueue1:=1; fillchar(visit,sizeof(visit),0); visit1:=1;s:=1;t:=1;whiles=tdo判断最短路长度是否不变beginG:=queues;j:=headG;whilej0doif(poi ntji)a nd( (4)an d(visitpo in tj=0)the n begin(5);in c(t);queuet:=poi n