NOIP2017提高组初赛模拟题

第二十三届全国青少年信息学奥林匹克联赛初赛提高组 语言模拟试题竞赛时间：201年10月日14:30~16:30选手注意•试题纸共有13页，答题纸共有2页，满分100分。请在答题纸上作答，写在试题纸上的一律无效。•不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。一、单项选择题（共15题，每题L5分，共计22.5分；每题有且仅有一个正确选项）.年（）授予肖克利（ ）、巴丁（ B和布拉顿（ ），以表彰他们对半导体的研究和晶体管效应的发现。诺贝尔物理学奖 约翰•冯•诺依曼奖图灵奖 高德纳奖（ ）.如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CaPSLOck、字母键A、字母键S和字母键D的顺序来回按键即CaPSLOCkA、S、D、S、A、CaPSLOck、A、S、D、S、A、CaPSLOck、A、S、D、S、A、……,屏幕上输出的第81个字符是字母（）。AA BS CD DA3.二进制数00101100和01010101异或的结果是（ ）。A00101000B01111001C01000100D00111000.与二进制小数0.1相等的八进进制数是（）。A0.8 B0.4 C0.2 D0.1.以比较作为基本运算，在N个数中找最小数的最少运算次数为（）。AN BN-1 CN2DlogN.表达式a*（b+c）-d的后缀表达形式为（）。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd. 一棵二叉树如右图所示，若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指

针）。如果没有左孩子或者右孩子，则对应的为空指针。

那么该链表中空指针的数目为（）。A6B7C12 D14.G是一个非连通简单无向图，共有28条边，则该图至少有（）个顶点。A10CDB9.某计算机的CPU和内存之间的地址总线宽度是32位（bit）,这台计算机最多可以使用（）的内存。A.2GB B.4GB C.8GB D.16GB.无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（）。A.中国公司的经理与波兰公司的经理交互商业文件第4层中国公司经理波兰公司经理~∏-H_第渥_ɪ二国史亘道理秘书五三仓■司经理程三ππ第£层*国务司第裆波兰公司翻译-H≡1≡-书里就递员-f波兰邮递员B.军队发布命令第4层■第4层司令第源军长1军长£ψI第2层师长1师长£师长3师长4II第1层团长也长2团长3团长4团长5团长6团长7团长吕C.国际会议中，每个人都与他国地位对等的人直接进行会谈第4层英国女王W—>瑞典国王第3层英国首相Y—*瑞典首相第渥英国外交大臣—*瑞典外交大臣第1层英国注是孰大便一.—>瑞热驻英国大便D∙体育比赛中，每一级比赛的优胜者晋级上一级比赛第4层奥运金fsɜs全运会ts≡≡省运金tSiS.有7个一模一样的苹果放到3个一样的盘子中一共有（）种放法。A7B8C21D.Lucia和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人A向他（她）的朋友B分享了某张照片，那么B就可以对该照片进行评论；如果B评论了该照片，那么他（她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论(除非A也向他(她)分享了该照片)。现在LUCia已经上传了一张照片但是她不想让Jacob看见这张照片那么她可以向以下朋友()分享该照片。ADana,MiChael,Eve BDana,Eve,MonicaCMichael,Eve,Jacob DMicheal,Peter,Monica.周末小明和爸爸妈妈三个人一起想动手做三道菜。小明负责洗菜、爸爸负责切菜、妈妈负责炒菜。假设做每道菜的顺序都是：先洗菜10分钟，然后切菜10分钟，最后炒菜10分钟。那么做一道菜需要30分钟。注意：两道不同的菜的相同步骤不可以同时进行。例如第一道菜和第二道的菜不能同时洗，也不能同时切。那么做完三道菜的最短时间需要()分钟。A.90 B.60 C.50 D.40.假设某算法的计算时间表示为递推关系式T(n)=2T(n)+√n.、 4T(I)=14则算法的时间复杂度为£)。 _A.On B.O√n C.OCnlognD.On215给定含有n个不同的数的数组L=<x1,x2,...,xn>。如果L中存在xi(1<i<n)使得x1<x2<...<xi1<xi>xi+1>...>xn,则称L是单峰的，并称xi是L的“峰顶”。现在已知L是单峰的，请把a-c三行代码补全到算法中使得算法正确找到L的峰顶。Search(k+1,n)Search(1,k-1)returnL[k]Search(1,n)kθ[n/2]ifL[k]>L[k-1]andL[k]>L[k+1]then elseifL[k]>L[k-1]andL[k]<L[k+1]then else 正确的填空顺序电£一)。A.c,a,b B.c,b,a C.a,b,C D.b,a,C二、不定项选择题(共5题，每题L5分，共计7.5分；每题有一个或多个正确选项，多选或少选均不得分).以下属于无线通信技术的有（）。A.蓝牙 B. WiFi C. GPRS D.以太网.可以将单个计算机接入到计算机网络中的网络接入通讯设备有（）。A.网卡 B. 光驱 C. 鼠标 D. 显卡.下列算法中运用分治思想的有（）。A.快速排序 B.归并排序C.冒泡排序D,计数排序4.下图表示一个果园灌溉系统，有A、B、C、D四个阀门，每个阀门可以打开或关上，所有管道粗细相同，以下设置阀门的方法中，可以让果树浇上水的B. AB都打开，CD都关上D.D打开，其他都关上有（）。A.B打开，其他都关上C.A打开，其他都关上5.参加NOI比赛，以下能带入考场的有（）。A.钢笔B, 适量的衣服 C.U盘D.铅笔三、问题求解（共2题，每题5分，共计10分；每题全部答对得5分，没有部分分）在和之间（包括和在内）不能被、、三个数任意一个数整除的数有 个。结点数为的不同形态的二叉树一共有 种。（结点数为的二叉树一共有种：一种是根结点和左儿子，另一种是根结点和右儿子。）四、阅读程序写结果（共4题，每题8分，共计32分）ConstSIZE=100;Varn,i,sum,X:integer;a:array[1..SIZE]ofinteger;beginreadln(n);fillchar(a,Sizeof(a),0);fori:=1tondobeginread(x);inc(a[x]);end;i:=0;sum:=0;whilesum<(ndiv2+1)dobegininc(i);sum:=Sum+a[i];end;writeln(i);end.输入：1145664332321输出：Varn:integer;proceduref2(x,y:integer);forward;proceduref1(x,y:integer);beginifx<nthenf2(y,x+y);end;proceduref2(x,y:integer);beginwrite(x,’');f1(y,x+y);end;beginreadln(n);f1(0,1);end.输入：30输出： constV=100;Varvisited:array[1..v]ofboolean;e:array[1..V,1..V]ofinteger;n,m,ans,i,j,a,b,C:integer;proceduredfs(x,len:integer);Var:integer;beginVisited[x]:=true;iflen>ansthenans:=len;fori:=1tondoif(notvisited[i])and(e[x,i]<>-1)thendfs(i,len+e[x,i]);visited[x]:=false;end;beginreadln(n,m);fori:=1tondoforj:=1tondoe[i][j]:=-1;fori:=1tomdobeginreadln(a,b,c);e[a][b]:=c;e[b][a]:=c;end;fori:=1tondovisited[i]:=false;ans:=0;fori:=1tondodfs(i,0);writeln(ans);end.输入：46210320430140350460输出： 4.constSIZE=10000;LENGTH=10;Varsum:longint;n,m,i,j:integer;a:array[1..SIZE,1..LENGTH]ofinteger;functionh(u,V:integer):integer;Varans,i:integer;beginans:=0;fori:=1tondoifa[u][i]<>a[v][i]theninc(ans);h:=ans;end;beginreadln(n);filichar(a,Sizeof(a),0);m:=1;repeat:=1;while(i<=n)and(a[m][i]=1)doinc(i);ifi>nthenbreak;inc(m);a[m][i]:=1;forj:=i+1tondoa[m][j]:=a[m-1][j];untilfalse;sum:=0;fori:=1tomdoforj:=1tomdosum:=sum+h(i,j);writeln(sum);end.输入：7输出： 五、完善程序(共2题，每题14分，共计28分)(双子序列最大和)给定一个长度为n(3≤n≤1000)的整数序列，要求从中选出两个连续子序列，使得这两个连续子序列的序列和之和最大，最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求：每个连续子序列长度至少为1且两个连续子序列之间至少间隔个数。（第五空分，其余分）为仅含 及 左侧整数的连续子序列的序列和中，最大的序列和为仅含 及 右侧整数的连续子序列的序列和中，最大的序列和（最短路径问题）无向连通图有