第十七届noip2011 提高组初赛试题及答案解析

《第十七届noip2011 提高组初赛试题及答案解析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十七届全国青少年信息学奥林匹克联赛初赛试题（提组Pascal语言两小时完成）●●全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效●●一、单项选择题（共10题，每题1.5分，共15分，每题有且仅有一个正确选项。）1.      在二进制下，1011010+（）=1100111。A.1011B.1101C.1010D.1111解析：简单的二进制运算，炮灰都会。直接用减法：1100111-1011010=00001101；也可用补码计算：1100111-1011010=（1100111）补+（-1011010）补=（01100111）+（11011010）补=（01100111）+（101

2、00101+00000001）=（01100111）+10100110）=100001101=1101（超过8位者溢出）。 答案：B2.      字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（）。A．66B.5AC.50D.视具体的计算机而定解析：每年必考进制转换题。若记得ASCII码的可以直接算出Z的码然后转回16进制，A的ASCII码是65，则Z的ASCII码为65+25=90，（90）10=（5A）16。若不记得的就把十六进制的41转回十进制，4*16+1=65，然后+25得90，再转成16进制得5A。 答案：BABCDEF3.      右图是一

3、棵二叉树，它的先序遍历是（）。A．ABDEFCB.DBEFACC.DFEBCAD.ABCDEF解析：每年必考树的遍历题。先序遍历就是先根遍历，就是先根，再左右子树的遍历。然后就ABDEFC出来了。 答案：A4.      寄存器是（）的重要组成部分。A.       硬盘B.       高速缓存C.       内存D.       中央处理器（CPU）解析：每年必考硬件知识题。计算机中能存储数据的部件有：寄存器，一级缓存，二级缓存，只读存储器ROM，随机存储器RAM和外存。其中寄存器和一级缓存在CPU内，一级缓存又名片上的缓存。二级缓存，只读存储器ROM和随机存储器RAM都在主板上，二

4、级缓存又名板上的缓存，只读存储器ROM和随机存储器RAM共同构成内存。外存指硬盘、光盘和可移动磁盘等。CPU包括运算逻辑部件ALU、寄存器部件和控制部件等。 答案：D5.      广度优先搜索时，需要用到的数据结构是（）。A.       链表B.       队列C.       栈D.       散列表解析：数据结构题。广搜需要存每一层的一大堆东西，继续向下一层搜时需要用到，所以要用存取方便的队列。链表取数不便，栈是深搜用的，散列表就是hash表，和宽搜没啥必然联系。 答案：B6.      在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（）A.       程

5、序运行时理论上所占的内存空间B.       程序运行时理论上所占的数组空间C.       程序运行时理论上所占的硬盘空间D.       程序源文件理论上所占的硬盘空间解析：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。常识题。BCD均明显错。 答案：A7.      应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。A.       O（n

6、^2）B.       O（nlogn）C.       O（n）D.       O（1）解析：快排的时间复杂度是O（nlogn），利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：1.Sa中元素的个数小于k，则Sb中的第k-

7、Sa

8、个元素即为第k大数；2.Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)。 答案：C8.      为解决Web应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。A.       微软

9、B.       美国计算机协会（ACM）C.       联合国教科文组织D.       万维网联盟（W3C）解析：微软的业绩主要是开发操作系统和软件，但是这种标准一般不是微软定制的；联合国教科文组织总部设在法国巴黎。其宗旨是促进教育、科学及文化方面的国际合作，以利于各国人民之间的相互了解，维护世界和平。美国计算机协会（ACM）犹如中国计算机学会，没有这样大的权限。WWW是环球信息网（WorldWideWeb）的缩写