第十七届全国青少年信息学奥林匹克联赛初赛试题

（ 提 组 Pascal 语言 两小时完成 ）

●● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●●

一、单项选择题（共10题，每题1.5分，共15分，每题有且仅有一个正确选项。） 1. 在二进制下，1011010+（ ）=1100111。 A.1011 B.1101 C.1010 D.1111 解析：简单的二进制运算，炮灰都会。直接用减法：1100111-1011010=00001101；也可用补码计算：

1100111-1011010=（1100111）补+（-1011010）补=（01100111）+（11011010）补=（01100111）+（10100101+00000001）=（01100111）+10100110）=100001101=1101（超过8位者溢出）。 答案：B

2. 字符“A”的ASCII码为十六进制41，则字符“Z”的ASCII码为十六进制的（ ）。 A．66 B.5A C.50 D.视具体的计算机而定 解析：每年必考进制转换题。若记得ASCII码的可以直接算出Z的码然后转回16进制，A的ASCII码是65，则Z的ASCII码为65+25=90，（90）10=（5A）16。若不记得的就把十六进制的41转回十进制，4*16+1=65，然后+25得90，再转成16进制得5A。 答案：B

A 3. 右图是一棵二叉树，它的先序遍历是（ ）。

B C

D E

A．ABDEFC B.DBEFAC C.DFEBCA D.ABCDEF

F

解析：每年必考树的遍历题。先序遍历就是先根遍历，就是先根，再左右子树的遍历。然后就ABDEFC出来了。 答案：A

4. 寄存器是（ ）的重要组成部分。 A. 硬盘 B. 高速缓存 C. 内存

D. 中央处理器（CPU）

解析：每年必考硬件知识题。计算机中能存储数据的部件有：寄存器，一级缓存，二级缓存，只读存储器ROM，随机存储器RAM和外存。其中寄存器和一级缓存在CPU内，一级缓存又名片上的缓存。二级缓存，只读存储器ROM和随机存储器RAM都在主板上，二级缓存又名板上的缓存，只读存储器ROM和随机存储器RAM共同构成内存。外存指硬盘、光盘和可移动磁盘等。CPU包括运算逻辑部件ALU、寄存器部件和控制部件等。 答案：D

5. 广度优先搜索时，需要用到的数据结构是（ ）。 A. 链表 B. 队列 C. 栈

D. 散列表

解析：数据结构题。广搜需要存每一层的一大堆东西，继续向下一层搜时需要用到，所以要用存取方便的队列。链表取数不便，栈是深搜用的，散列表就是hash表，和宽搜没啥必然联系。 答案：B

6. 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（ ） A. 程序运行时理论上所占的内存空间 B. 程序运行时理论上所占的数组空间 C. 程序运行时理论上所占的硬盘空间 D. 程序源文件理论上所占的硬盘空间

解析：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。常识题。BCD均明显错。 答案：A

7. 应用快速排序的分治思想，可以实现一个求第K大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（ ）。 A. O（n^2） B. O（n log n） C. O（n） D. O（1）

解析：快排的时间复杂度是O（nlogn），利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：

1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；

2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)。

答案：C

8. 为解决Web应用中的不兼容问题，保障信息的顺利流通，（ ）制定了一系列标准，涉及HTML、XML、CSS等，并建议开发者遵循。 A. 微软

B. 美国计算机协会（ACM） C. 联合国教科文组织 D. 万维网联盟（W3C）

解析：微软的业绩主要是开发操作系统和软件，但是这种标准一般不是微软定制的；联合国教科文组织总部设在法国巴黎。其宗旨是促进教育、科学及文化方面的国际合作，以利于各国人民之间的相互了解，维护世界和平。美国计算机协会（ACM）犹如中国计算机学会，没有这样大的权限。WWW是环球信息网（World Wide Web ）的缩写，中文名字为“万维网”, 万维网联盟（World Wide Web Consortium，W3C），又称W3C理事会。1994年10月在麻省理工学院计算机科学实验室成立。建立者是万维网的发明者蒂姆·伯纳斯-李。W3C为解决 Web 应用中不同平台、技术和开发者带来的不兼容问题，保障 Web 信息的顺利和完整流通，万维网联盟制定了一系列标准并督促 Web 应用开发者和内容提供者遵循这些标准。所以就是D了。 答案：D