2011年信息学奥赛NOIP提高组初赛C++真题

N OIP20 11 初赛 提高组 C++ 1 第十 七 届全国青少年信息学奥林匹克联赛初赛试题 （ 提高组 C++ 语言 两 小时完成 ） ● ● 全部试题答案均要求写在答卷纸上，写在试卷纸上一律无效 ●● 一 、 单项选择题 （ 共 10 题，每题 1.5 分，共计 15 分。每题有且 仅 有一个正确 选项 。 ） 1 ． 在二进制下， 1011001 + （ ） = 1100110 。 A ． 1011 B ． 1101 C ． 1010 D ． 1111 2 ． 字符“ A ”的 ASCII 码为十六进制 41 ，则字符“ Z ”的 ASCII 码为十六 进制的（ ） 。 A ． 66 B ． 5A C ． 50 D ． 视具体的计算机而定 3 ． 右图 是一棵二叉树，它的先序遍历是（ ） 。 A ． ABDEFC B ． DBEFAC C ． DFEBCA D ． ABCDEF 4 ． 寄存器是（ ）的重要组成部分。 A ． 硬盘 B ． 高速缓存 C ． 内存 D ． 中央处理器（ CPU ） 5 ． 广度优先搜索时，需要用到的数据结构是（ ） 。 A ． 链表 B ． 队列 C ． 栈 D ． 散列表 6 ． 在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（ ） 。 A ． 程序运行时理论上所占的内存空间 B ． 程序运行时理论上所占的数组空间 C ． 程序运行时理论上所占的硬盘空间 D ． 程序源文件 理论上所占的硬盘空间 7 ． 应用快速排序的分治思想，可以实现一个求第 K 大数的程序。假定不考虑极端的最坏情况，理论 上可以实现的最低的算法时间复杂度为（ ） 。 A ． O (n 2 ) B ． O (n log n ) C ． O (n) D ． O (1) 8 ． 为解决 web 应用中的不兼容问题，保障信息的顺利流通，（ ）制 定 了 一 系 列 标 准 ，涉 及 HTML 、 XML 、 CSS 等，并建议开发者遵循 。 A ． 微软 B ． 美国计算机协会（ ACM ） C ． 联合国教科文组织 D ． 万维网联盟（ W3C ） 9 ． 体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。每个同学按顺 序来到操场时，都从排尾走到排头，找到第一个比自己高的同学， 并站在他的后面。这种站队的方 法类似于（ ）算法 。 A ． 快速排序 B ． 插入排序 C ． 冒泡排序 D ． 归并排序 10 ． 1956 年（ ）授 予 肖 克 利（ William Shockley ）、巴 丁（ John Bardeen ）和 布 拉 顿（ Walter Brattain ） A ． 诺贝尔物理学奖 B ． 约翰 ·冯·诺依曼奖 C ． 图灵奖 D ． 高德纳奖 （ Donald E. Knuth Prize ） N OIP20 11 初赛 提高组 C++ 2 二 、 不定项选择题 （共 10 题，每题 1.5 分，共计 15 分。每题正确答案的个数不少于 1 。多选或少 选均不得分）。 1 ． 如果根结点的深度记为 1 ，则一棵恰有 2011 个叶子结点的二叉树的深度可能是（ ） 。 A ． 10 B ． 11 C ． 12 D ． 2011 2 ． 在布尔逻辑中，逻辑“或”的性质有（ ） 。 A ． 交换律： P V Q = Q V P B ． 结合律： P V （ Q V R ） = （ P V Q ） V R C ． 幂等律： P V P = P D ． 有界律： P V 1 = 1 （ 1 表示逻辑真） 3 ． 一个正整数在十六进制下有 100 位，则它在二进制下可能有（ ）位 。 A ． 399 B ． 400 C ． 401 D ． 404 4 ． 汇编语言（ ） 。 A ． 是一种与具体硬件无关的程序设计语言 B ． 在编写复杂程序时，相对于高级语言而言代码量大，且不易调试 C ． 可以直接访问寄存器、内存单元、 I/O 端口 D ． 随着高级语言的诞生，如今已被完全淘汰，不再使用 5 ． 现有一段文言文，要通过二进制哈夫曼 编码进行压缩。简单起见，假设这段文言文只由 4 个汉字 “之”、“乎”、“者”、“也”组成，它们出现的次数分别为 700 、 600 、 300 、 400 。那么，“也” 字的编码长度可能是（ ） 。 A ． 1 B ． 2 C ． 3 D ． 4 6 ． 生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识 别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其 应用的是（ ） 。 A ． 指静脉