2013年信息学奥赛NOIP普及组初赛C++真题

第 十 九 届 全 国 青 少 年 信 息 学 奥 林 匹 克 联 赛 初 赛 普及组 C++ 语言试题 竞赛时间： 2013 年 10 月 13 日 14:30~16:30 选手注 意 ： 试题纸共有 9 页，答题纸共有 2 页，满分 100 分。请在答题纸上作答，写在试题纸上的 一律无效。 不得使用任何电子设备（如计算器、手机、电子词典等） 或查阅任何书籍资料。 一、单项选择题（ 共 20 题， 每 题 1.5 分， 共 计 30 分；每题有且仅有一个正确选 项） 一 个 32 位整型变量占用 （ ）个字节 。 A. 4 B. 8 C. 32 D. 128 二 进 制数 11.01 在十进制 下 是 （ ） 。 A. 3.25 B. 4.125 C. 6.25 D. 11.125 下 面 的故事 与 （ ）算法 有 着 异曲同工之妙 。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‚从前有座山，山 里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个 老和尚给小和尚讲故事 ’‛ A. 枚举 B. 递归 C. 贪心 D. 分治 逻 辑 表达式 （ ）的值与变 量 A 的真假无关 。 A. (A ˅ B) ˄ ¬A B. (A ˅ B) ˄ ¬B C. (A ˄ B) ˅ (¬A ˄ B) D. (A ˅ B) ˄ ¬A ˄ B 将（ 2, 6, 10 , 17 ） 分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数 h ( x ) = （ ） ，将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。 A. x mod 11 B. x 2 mod 11 C. 2 x mod 11 D. ⌊ √ 𝑥 ⌋ mod 11 ，其中 ⌊ √ 𝑥⌋ 表示 √ 𝑥 下取整 在十六进制表示法中，字 母 A 相当于十进 制中的 （ ） 。 A. 9 B. 10 C. 15 D. 16 下 图 中所使用的数据结构 是 （ ） 。 压入 A 压入 B 弹出 B 压入 C B C A A A A A. 哈希表 B. 栈 C. 队列 D. 二叉树 在 Windows 资源管理器中，用鼠标右键单击一个文 件时，会出现一个名为“ 复制”的 操 作 选项，它的意思 是 （ ） 。 A. 用剪切板中的文件替换该文件 B. 在该文件所在文件夹中，将该文件克隆一份 C. 将该文件复制到剪切板，并保留原文件 D. 将该文件复制到剪切板，并删除原文件 已 知 一棵二叉树有 10 个节 点 ，则其中至多 有 （ ） 个 节 点有 2 个子节点 。 A. 4 B. 5 C. 6 D. 7 在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。下图是一个有 4 个顶点、 6 条边的连通图 。 若 要使它不再是连通图， 至 少要删去其中的 （ ） 条 边 。 A. 1 B. 2 C. 3 D. 4 二 叉 树 的 （ ）第一个访问的节点是根节 点 。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 以上都是 以 A 0 作为起点，对下面的 无 向 图进行 深 度 优先遍历 时 ，遍历顺序 不 可 能 是 （ ） 。 A. A 0 , A 1 , A 2 , A 3 B. A 0 , A 1 , A 3 , A 2 C. A 0 , A 2 , A 1 , A 3 D. A 0 , A 3 , A 1 , A 2 IPv4 协议使用 32 位地址， 随着其不断被分配，地址 资源日趋枯竭。因此，它 正逐渐被 使 用 （ ）位地址的 IPv6 协议所取 代。 A. 40 B. 48 C. 64 D. 128 （ ）的 平均 时间复杂度为 O( n log n ) ，其中 n 是待排序的元素个数。 A. 快速排序 B. 插入排序 C. 冒泡排序 D. 基数排序 下 面 是根据欧几里得算法编 写 的函数，它所计算的是 a 和 b 的 （ ） 。 int euclid(int a, int b) { if (b == 0) return a; else return euclid(b, a % b); } A. 最大公共质因子 B. 最小公共质因子 C. 最大公约数 D. 最小公倍数 通 常 在搜索引擎中，对某 个 关 键词加上双引号表示 （ ） 。 A. 排除关键词，不显示任何包含该关键词的结果 B. 将关键词分解，在搜索结果中必须包含其中的一部分 C. 精确搜索，只显示包含整个关键词的结果 D. 站内搜索，只显示关键词所指向网站的内容 中 国 的国家顶级域名 是 （ ） 。 A. .cn B. .ch C. .chn D. .china 把 64 位非零浮点数强制转 换 成 32 位浮点数后， 不 可 能 （ ） 。 A. 大于原数 B. 小于原数 C. 等于原数 D. 与原数符号相反 下 列 程 序 中 ， 正确计算 1, 2, …, 100 这 100 个自然数之和 sum （初始值为 0 ）的 是 （ ） 。 A. i = 1; do { sum += i; i++; } while (i <= 100); B. i = 1; do { sum += i; i++; } while (i > 100); C. i = 1; while (i < 100) { sum += i; i++; } D. i = 1; while (i >= 100) { sum += i; i++; } CCF NOIP 复赛全国统一 评 测 时使用的系统软件是 （ ） 。 A. NOI Windows B. NOI Linux C. NOI Mac OS D. NOI DOS 二、问 题 求 解（ 共 2 题， 每 题 5 分， 共 计 10 分；每 题 全 部答对得 5 分，没 有 部 分分） 7 个同学围坐一圈，要选 2 个不相邻的作为代表，有 种不同的选法。 某系统自称使用了一种防窃听的方式验证用户密码。密码是 n 个数 s 1 , s 2 , …, s n