2011第17届NOIP试题及解析

第十七届NOIP2011提高组初赛试题+答案+解析（pascal）一、单项选择题（共10题，每题1.5分，共15分，每题有且仅有一个正确选项。）在二进制下，1011010+（）=1100111。1011 B.1101C.1010D.1111答案：B解析：简单的二进制运算，炮灰都会。字符“A”的ASCII码为十六进制41，则字符“Z^的ASCII码为十六进制的（）。A.66B.5AC.50 D.视具体的计算机而定答案：B解析：每年必考进制转换题。背得ASCII码的可以直接算出Z的码然后转回16进制。像我不背得的就把十六进制的41转回十进制，4*16+1=65，然后+25得90，再转成16进制得5A。右图是一棵二叉树，它的先序遍历是（）。（我就不画图了==带鱼语口述一下：根是A，左右子树分别为B和C，B的左右子树分别为D和E，E的右子树为F）ABDEFCB.DBEFACC.DFEBCAD.ABCDEF答案：A解析：每年必考树的遍历题。先序遍历就是先根遍历，就是先根，再左右子树的遍历。然后就ABDEFC出来了。从这个解析可以看出这个解析是新手向的解析-。-寄存器是（）的重要组成部分。硬盘高速缓存内存中央处理器（CPU）答案：D解析：每年必考硬件知识题。寄存器在CPU里。广度优先搜索时，需要用到的数据结构是（）。链表队列栈散列表答案：B解析：数据结构题。广搜需要存每一层的一大堆东西，继续向下一层搜时需要用到，所以要用存取方便的队列。链表取数不便，栈是深搜用的，散列表就是hash表，和宽搜没啥必然联系。在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）程序运行时理论上所占的内存空间程序运行时理论上所占的数组空间程序运行时理论上所占的硬盘空间程序源文件理论上所占的硬盘空间答案：A解析：常识题。BCD均明显错。应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。O （nA2）O （nlogn）O （n）O （1）答案：C解析：快排思想找第K大的数以前初赛就出过，那时是个补完程序题。快排的时间复杂度是O（nlogn），这题我费解了一下，我认为是O（logn），不过没这个选项，于是我猜是O（n）。刚才上网查，这个方法找第K大的数时间复杂度的确是O（n）。为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。微软美国计算机协会（ACM）联合国教科文组织万维网联盟（W3C）答案：D解析：姿势题，我承认我不会，不过我根据丰富的经验，猜对了。虽然微软很流弊，但是这种标准一般不是微软定制的；联合国教科文组织总部设在法国巴黎。其宗旨是促进教育、科学及文化方面的国际合作，以利于各国人民之间的相互了解，维护世界和平。所以就是D了。体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高道矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。快速排序插入排序冒泡排序归并排序答案：B解析：排序问题。这个站队方法与插排相同，找个位置插进去！1956年（）授予肖克利（WilliamShockley）（带鱼：“有没有一种‘Youareshock!’的感觉啊〜”）、巴丁（JohnBardeen）和布拉顿（WalterBrattain），以表彰他们对半导体的研究和晶体管效应的发现。诺贝尔物理学奖约翰•冯•诺依曼奖图灵奖D. 高德纳奖（DonaldE.KnuthPrize）答案：A解析：超级姿势题，没啥人做得对，我也错了…我看D标了英文，很犀利的样子，我就选D了，结果竟然是A。D的那个也是计算机的奖，始于1996年。1996年姚期智得了高德纳奖，2000年姚期智得了图灵奖，不过姚期智太不注重名利了，没啥人知道，搜狗拼音都打不出来。1997年莱斯利得了高德纳奖，2010年得了图灵奖，我以为会考最新的图灵奖得主，背了这人名字，结果没考，考的是几十年前的人……冏二、不定项选择题（共10题，每题1.5分，共15分。每题有一个或多个正确选项。多选或少选均不得分。）（这部分较难得分，我错了很多题）如果根节点的深度记为1，则一棵恰有2011个叶子结点的二叉树的深度可能是（）。TOC\o"1-5"\h\z1011122011答案：CD解析：可以自己推出，深度为n的满二叉树叶子结点数为2A（n-1），2人10=1024,2人11=2048,深度为11的数怎么搞都搞不出2011个结点，所以10和11不选。深度为n的一根蛋疼树也可以有n个叶子结点…这个我没考虑到，果断错了。在布尔逻辑中，逻辑“或”的性质有（）。（原题ABCD选项里的或是个类似V的表示或的符号，为了该文档流通方便我都改成了“V”）交换律：PVq=qVp结合律：PV（QVR）=（PVQ）VR幕等律：PVP=P有界率：PV1=1（1表示逻辑真）答案：ABCD解析：基础题。虽然我不知道or是否有什么交换律结合律，思考一下就行了。A，位置交换肯定不影响结果；B，不管怎么括，都是其中有1就是1，都为0才为0,；C肯定，D更不用说。一个正整数在十六进制下有100位，则它在二进制下可能有（）位。TOC\o"1-5"\h\z399400401404答案：AB解析：一个十六进制数字可用4个二进制数字表示，100位的十六进制可以用400位二进制表示，当然刚开始那几位可能是0，所以也可能是399、398、397位二进制表示。汇编语言（）。A. 是一种与硬件无关的程序设计语言在编写复杂程序时，相对于高级语言而言代码量较大，且不易调试可以直接访问寄存器、内存单元、I/O端口随着高级语言的诞生，如今已完全被淘汰，不再使用答案：BC解析：姿势题，我姿势不够没做对。A，与硬件有关；B，这是肯定的；C，百度说汇编语言能够直接访问与硬件相关的存储器或I/O端口。D，百度说汇编语言是一种功能很强的程序设计语言，也是利用计算机所有硬件特性并能直接控制硬件的语言。汇编语言是比较底层的语言，不会不再使用，只是不用来直接编程而已。现有一段文言文，要通过二进制哈弗曼编码进行压缩。简单起见，假设这段文言文只由4个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为700、600、300、400。那么，“也”字的编码长度可能是（）。TOC\o"1-5"\h\z1234答案：BC解析：初赛常考的哈夫曼编码。哈夫曼编码是一种很犀利的编码，按那啥的使用频率，把使用频率高的那啥编为短一点的编码，使用频率高的长一点。一般方法是建一棵哈弗曼树，然后左子树为0右子树为1，从上到下的一条路为这个叶子结点的编码。百度说把所有东西放到一个集合F中，在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。这样，从这题来看，先弄300和400的两个，变成一个根为700的树。然后现在就有600,700,700，选600和其中一个700再做一颗树。这样就会有两种情况，“也”可能是2位也可能是3位，所以选BC。生物特征识别是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（）。指静脉验证步态验证ATM机密码验证声音验证答案：ABD解析：蛋疼题。主要纠结于选不选D，你需要一定的考试经验和对出题老师的心理分析，得出D这个选项就是特指生物的声音而不是各种声音，选上D。对于序列“7、5、1、9、3、6、8、4”，在不改变顺序的情况下，去掉（）会使逆序对的个数减少3.TOC\o"1-5"\h\z7536答案：CD解析:姿势题，我没姿势我不自豪，做错。百度说，对于一个包含N个非负整数的数组A[1..n],如果有i<j，且A[i]>A[j]，则称（A[i],A[j]）为数组A中的一个逆序对。现在知道逆序对是啥了，就容易做了，数字这么少，穷举两个数只需C（2,8）=28次，找到所有的逆序对，自己在草稿纸上开个数组，每找到一个就在这个数下面加一，然后看哪个数在数组里等于3的就选它。计算机中的数值信息分为整数和实数（浮点数）。实属之所以能表示很大或者很小的数是由于使用了（）。阶码补码反码较长的位数答案：A解析：姿势题，我略看了一点这方面的姿势，我有姿势我自豪。对右图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离【B】初始时赋值为8,在算法的执行过程中还会出现的值有（）。（原试题右图，为照顾手机党我字述边集（（a,b,c）代表a到b有条长c的边）：（S,A,2），（S,B,8），（S,D,3），（A,B,5），（B,C,1），（B,D,3），（C,D,1）TOC\o"1-5"\h\z3765答案：BCD解析：学过Dijkstra就知道，我是太久没用这个忘记了冏„Dijkstra的思想是建个一维数组记录起点到其他各点的距离（没路为无限大），然后找一个这个距起点最近的点作为中间结点，更新起点到各个点的距离，然后把中心结点加个用过的标记，继续找下一个距离起点最近的点为中心结点，直到所有的点都当过中心结点就结束。这题中，第一个找到的中间结点是A，这时把SB更新为7，然后找到的中心结点为D，这时把SB更新为6，把SC更新为4；下一个找到的中心结点为C，这时把SB更新为5。所以选BCD。为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为（原题写的是“成为”）网络协议。下列英文缩写中，（）是网络协议。HTTPTCP/IPFTPWWW答案：ABC解析：网络协议不单指某一协议，而是指各种为计算机网络中进行数据交换而建立的规则、标准或约定的集合。所以HTTP（超文本传输协议）、TCP/IP、FTP（文件传输协议）都属于网络协议。WWW是万维网，不是协议。三、问题求解（共2题，每题5分，共计10分）平面图是可以画在平面上，且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至多有6条边，如右图所示。那么，5个顶点的平面图至多有―条边。(图我就不画了，比较简单，是一个口画一条对角线，然后没有对角线的那2个点从口外面连了一条曲线)答案：9解析：手画，怎么画最多都只能画9条，所以……定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串“BCA”，可以将A移到B之前，变成字符串“ABC”。如果要将字符串"DACHEBGIF”变成“ABCDEFGHI”，最少需要次操作。答案：4解析：这个不是交换位置喔，是取出再插入。先在原序列中找个最长上升子序列(除去某些元素，但不影响相对位置的序列称为子序列)，发现是ACEGI，长度为5,最长了，剩下4个移动一下就能成有序的ABCDEFGHI了。四、阅读程序写结果(共4题，每题8分，共计32分)1.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输出： 答案：3解析：这是个求中位数的程序。注意读入的时候不是把数读进a[i],而是让a[x]+1。简单模拟也可以。啊varn:ineger;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输出： 答案：1251334解析：模拟一下，发现是隔一个输出一个的斐波那契数列，注意主程序调用的是^1而不是f2,我没注意看以为是f2结果整个都错位了冏。啊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);vari: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.输入：46TOC\o"1-5"\h\z2103204301402460输出： 答案：150解析：一眼看去，过程名叫DFS,输入是个无向图，len>ans的话ans:=len，可以得知这是个在图中用DFS找最长的路径的程序。DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4个点，最多就走3条边，看看最长的那3条，605040,可以一次走完，即走2-4-1-3可以走完这3条边，所以ans是150。4.啊constSIZE=10000;LENGTH=10;varsum:longint;n,m,I,j:integer;a:array[1..SIZE,