《第十七届NOIP2011 提高组初赛试题及答案解析》由会员分享，可在线阅读，更多相关《第十七届NOIP2011 提高组初赛试题及答案解析（30页珍藏版）》请在金锄头文库上搜索。
1、第十七届全国青少年信息学奥林匹克联赛初赛试题 （ 提 组 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）补 =（
2、01100111）+（10100101+00000001）=（01100111）+10100110）=100001101=1101（超 过 8 位者溢出） 。答案：B2. 字符“A”的 ASCII 码为十六进制 41，则字符“Z”的 ASCII 码为十六进制的（ ） 。A66 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
3、 得 90，再转成 16 进制得 5A。答案：B 3. 右图是一棵二叉树，它的先序遍历是（ ） 。AABDEFC B.DBEFAC C.DFEBCA D.ABCDEF解析：每年必考树的遍历题。先序遍历就是先根遍历，就是先根，再左右子树的遍历。 然后就 ABDEFC 出来了。答案：A 4. 寄存器是（ ）的重要组成部分。 A. 硬盘 B. 高速缓存 C. 内存 D. 中央处理器（CPU）解析：每年必考硬件知识题。计算机中能存储数据的部件有：寄存器，一级缓存，二级缓 存，只读存储器 ROM，随机存储器 RAM 和外存。其中寄存器和一级缓存在 CPU 内，一 级缓存又名片上的缓存。二级缓存，只读存储
4、器 ROM 和随机存储器 RAM 都在主板上， 二级缓存又名板上的缓存，只读存储器 ROM 和随机存储器 RAM 共同构成内存。外存指ABCDEF硬盘、光盘和可移动磁盘等。CPU 包括运算逻辑部件 ALU、寄存器部件和控制部件等。答案：D5. 广度优先搜索时，需要用到的数据结构是（ ） 。 A. 链表 B. 队列 C. 栈 D. 散列表解析：数据结构题。广搜需要存每一层的一大堆东西，继续向下一层搜时需要用到，所以 要用存取方便的队列。链表取数不便，栈是深搜用的，散列表就是 hash 表，和宽搜没啥必 然联系。答案：B 6. 在使用高级语言编写程序时，一般提到的“空间复杂度”中的“空间”是指（
5、） A. 程序运行时理论上所占的内存空间 B. 程序运行时理论上所占的数组空间 C. 程序运行时理论上所占的硬盘空间 D. 程序源文件理论上所占的硬盘空间解析：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法 在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输 入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。常识题。BCD 均明显错。答案：A7. 应用快速排序的分治思想，可以实现一个求第 K 大数的程序。假定不考虑极端的最 坏情况，理论上可以实现的最低的算法时间复杂度为（ ） 。 A. O（n2） B. O（n log
6、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)。答案：C8. 为解决 Web 应用中的不兼容问题，保障信息的顺利流通， （ ）制定了一系列标准， 涉及 HTML、XML、CSS 等，并建议开发者遵循。 A. 微软 B.
7、 美国计算机协会（ACM） C. 联合国教科文组织 D. 万维网联盟（W3C）解析：微软的业绩主要是开发操作系统和软件，但是这种标准一般不是微软定制的；联合 国教科文组织总部设在法国巴黎。其宗旨是促进教育、科学及文化方面的国际合作，以利 于各国人民之间的相互了解，维护世界和平。美国计算机协会（ACM）犹如中国计算机学 会，没有这样大的权限。WWW 是环球信息网（World Wide Web ）的缩写，中文名字为“万维网”, 万维网联盟（World Wide Web Consortium，W3C） ，又称 W3C 理事会。1994 年 10 月在麻省理工学院计算机科学实验室成立。建立者是万维网的
8、发明者蒂姆 伯纳斯- 李。W3C 为解决 Web 应用中不同平台、技术和开发者带来的不兼容问题，保障 Web 信息的顺利和完整流通，万维网联盟制定了一系列标准并督促 Web 应用开发者和内容提供者遵循这些标准。 所以就是 D 了。答案：D9. 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。 每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他 的后面。这种站队的方法类似于（ ）算法。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 归并排序解析：此题考查学员对各种排序思想的掌握。快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排
9、序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。假设要排序的数组是 A1AN，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：1） 、设置两个变量 I、J，排序开始的时候 I：=1，J：=N；2）以第一个数组元素作为关键数据，赋值给 X，即 X：=A1；3） 、从 J 开始向前搜索，即由后开始向前搜索（J：=J-1） ，找到第一个小于
10、X 的值，两者交换；4） 、从 I 开始向后搜索，即由前开始向后搜索（I：=I+1） ，找到第一个大于 X 的值，两者交换；5） 、重复第 3、4 步，直到 I=J；插入排序的基本思想：每次将一个待排序的记录按其关键字的大小插入到前面已经排好序 的子文件的适当位置，直到 全部的记录插入完成为止。 冒泡排序的基本思想是：将被排序的记录数组 R1n垂直排列，每个记录 Ri看作是 重量为 Ri.key 的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组 R：凡 扫描到违反本原则的轻气泡，就使其向上“飘浮“。如此反复进行，直到最后任何两个气泡 都是轻者在上，重者在下为止。 归并排序(Merge
11、 Sort)是利用“归并“技术来进行排序。归并是指将若干个已排序的子文 件合并成一个有序的文件。 两路归并算法基本思路两路归并算法基本思路设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：Rlowm， Rm+1high，先将它们合并到一个局部的暂存向量 R1(相当于输出堆)中，待合并完成后将 R1 复制回 Rlowhigh中。合并过程中，设置 i，j 和 p 三个指针，其初值分别指向这三个记录区的起始位置。合 并时依次比较 Ri和 Rj的关键字，取关键字较小的记录复制到 R1p中，然后将被复制记 录的指针 i 或 j 加 1，以及指向复制位置的指针 p 加 1。重复这一过程直至两个
12、输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将 另一非空的子文件中剩余记录依次复制到 R1 中即可。答案：B10. 1956 年（ ）授予肖克利（William Shockley）巴丁（John Bardeen）和布拉顿（Walter Brattain）,以表彰他们对半导体的研究和晶体管效应的发现。 A. 诺贝尔物理学奖 B. 约翰冯诺依曼奖 C. 图灵奖 D. 高德纳奖（Donald E.Knuth Prize）解析： 此题考查学生对 IT 方面的新闻和名人名事的相关熟知度。 诺贝尔物理学奖是根据诺贝尔的遗嘱而设立的，是诺贝尔奖之一。该奖项旨在 奖励那些对人类物理学领域里作出突出贡
13、献的科学家。由瑞典皇家科学院颁发 奖金，每年的奖项候选人由瑞典皇家自然科学院的瑞典或外国院士、诺贝尔物 理和化学委员会的委员、曾被授与诺贝尔物理或化学奖金的科学家、 在乌普萨 拉、隆德、奥斯陆、哥本哈根、赫尔辛基大学、卡罗琳医学院和皇家技术学院 永久或临时任职的物理和化学教授等科学家推荐。 约约翰翰冯冯诺诺依依曼曼奖奖由 IEEE 成立于于 1990 年，目的是表杨在计算机科学和 技术上具有杰出成就的科学家。该奖牌是以对计算机科学具有重大贡献的现 代电脑创始人之一约翰 冯诺伊曼命名。2011 年获奖者: 东尼霍尔 图灵奖（A.M. Turing Award，又译“杜林奖”），由美国计算机协会（
14、ACM） 于 1966 年设立，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自 计算机科学的先驱、英国科学家阿兰麦席森图灵。由于图灵奖对获奖条件 要求极高，评奖程序又是极严，一般每年只奖励一名计算机科学家，只有极少 数年度有两名合作者或在同一方向作出贡献的科学家共享此奖。因此它是计算 机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。2011 年 获奖者：Judea Pearl 犹大伯尔 高德纳奖（Donald E. Knuth Prize）， 授予为计算机科学基础做出杰出贡 献的人，以计算机科学家高德纳（ Donald E. Knuth）命名。 高德纳奖始于 1996 年
15、，每 1.5 年颁发一次，包括 5000 美元奖金。现在奖 项由 ACM 计算机理论研讨会和 IEEE 计算机科学基础研讨会交替颁发。答案：A二、不定项选择题（共 10 题，每题 1.5 分，共 15 分。每题有一个或多个正确选项。多选 或少选均不得分。 ） 1. 如果根节点的深度记为 1，则一棵恰有 2011 个叶子结点的二叉树的深度可能是（ ） 。A. 10 B. 11 C. 12 D. 2011解析：此题考查二叉树的性质方面的有关知识。 深度为 n 的叶子结点最多的二叉树是满二叉树，所能有的叶子结点数为 2（n-1） ， 210=1024，211=2048，深度为 11 的二叉怎么搞都搞不出 2011 个结点，所以 10 和 11 不 选。深度为 n 的一根树也可以有 n 个叶子结点。 答案：CD2. 在布尔逻辑中，逻辑“或”的性质有（ ） 。 A. 交换律：PVq=qVp B. 结合律：P V（Q V R）=（P V Q）V R C.
