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

CCF NOIP201 8初赛提高组 C++语言试题 第 1页，共 9页 第 二十 四 届全国青少年信息学奥林匹克联赛 初赛 提高 组 C++ 语言 试题 竞赛时间： 201 8 年 10 月 13 日 14:30~16:30 选手 注意：  试题 纸 共有 10页， 答题纸 共有 2页 ，满分 100 分 。 请在 答题纸 上作答 ，写 在 试题 纸 上的一律无效。  不得 使用 任何电子设备（如 计算器 、手机、电子词典等）或 查阅 任何书籍资 料 。 一、单项选择题（共 10题，每题 2分，共计 20 分 ；每题有且仅有一个正确选项） 1. 下列四个不同进制的数中，与其它三项数值上不相等的是（ ）。 A. (269) 16 B. (617) 10 C. (1151) 8 D. (1001101011) 2 2. 下列属于解释执行的程序设计语言是（ ）。 A. C B. C++ C. Pascal D. Python 3. 中国计算机学会于（ ） 年创办全国青少年计算机程序设计竞赛 。 A. 1 983 B. 1 984 C. 1 985 D. 1 986 4. 设 根节点 深度为 0，一棵深度为 h的满 k（ k>1 ） 叉树， 即除最后一层无任何 子节点外，每一层上的所有结点都有 k个子结点的树，共 有 （ ） 个结点 。 A. (k h+1 - 1) / (k - 1) B. k h-1 C. k h D. (k h-1) / (k - 1) 5. 设某算法 的时间复杂度函数的递推方程是 T(n) = T(n - 1) + n （ n为正整数） 及 T(0) = 1 ， 则该算法的时间复杂度为（ ）。 A. O(log n) B. O(n log n) C. O(n) D. O(n 2) CCF NOIP201 8初赛提高组 C++语言试题 第 2页，共 9页 6. 表达式 a * d - b * c 的前缀形式是（ ）。 A. a d * b c * - B. - * a d * b c C. a * d - b * c D. - * * a d b c 7. 在一条长度为 1的线段上随机取两个点，则以这两个点为端点的线段的期望 长度是（ ）。 A. 1 / 2 B. 1 / 3 C. 2 / 3 D. 3 / 5 8. 关于 Catalan 数 Cn = (2n)! / (n + 1)! / n ！，下列说法中错误的是（ ）。 A. Cn 表示有 n + 1 个 结点 的 不同形态的 二叉树的个数 。 B. Cn 表示含 n对 括号的合法 括号序列 的个数 。 C. Cn 表示长度为 n的入栈序列对应的合法出栈序列个数。 D. Cn 表示通过 连接 顶点而将 n + 2 边的凸多边形分成三角形的方法个数 。 9. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率 获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的 策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获 得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于 （ ）。 A. 1 : 2 B. 2 : 1 C. 1 : 3 D. 1 : 1 10. 为了统计一个非负整数的二进制形式中 1的个数，代码如下： int CountBit(int x) { int ret = 0; while (x) { ret++; ________ ; } return ret; } 则空格内要填入的语句是（ ）。 A. x >>= 1 CCF NOIP201 8初赛提高组 C++语言试题 第 3页，共 9页 B. x &= x - 1 C. x |= x >> 1 D. x <<= 1 二 、 不定 项选择题（共 5题，每题 2分，共计 10 分 ；每题有一个或多个正确选 项，多选或少选均不得分 ） 1. NOIP 初赛中，选手可以带入考场的有（ ）。 A. 笔 B. 橡皮 C. 手机（关机） D. 草稿纸 2. 2-3树是一种特殊的树，它满足两个条件： （ 1）每个内部结点有两个或三个子结点； （ 2）所有的叶结点到根的路径长度相同 。 如果一棵 2-3树有 10 个叶结点，那么它可能有 （ ） 个非叶结点。 A. 5 B. 6 C. 7 D. 8 3. 下列关于最短路算法的说法正确的有（ ）。 A. 当图中不存在负权回路但是存在负权边时， Dijkstra 算法不一定能求出源 点到所有点的最短路。 B. 当图中不存在负权边时， 调用多次 Dijkstra 算法能求出每对顶点间最短路 径。 C. 图中存在负权回路时， 调用 一次 Dijkstra 算法也一定能求出源点到所有点 的最短路。 D. 当图中不存在负权边时， 调用 一次 Dijkstra 算法不能用于每对顶点间最短 路计算。 4. 下列说法中，是树的性质的 有 （ ）。 A. 无环 B. 任意两个结点之间 有且 只有一条简单路径 C. 有且只有一个简单环 D. 边的数目恰是顶点数目减 1 5. 下列关于图灵奖的说法中，正确的有（ ）。 A. 图灵奖是由 电气和电子工程师协会 （ IEEE ）设立的。 B. 目前获得该奖项的华人学者只有姚期智教授一人。 C. 其名称取自计算机科学的先 驱、英国科学家艾伦·麦席森·图灵。 CCF NOIP201 8初赛提高组 C++语言试题 第 4页，共 9页 D. 它是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖” 之称。 三、 问题求解（共 2题，每 题 5分，共计 10分） 1. 甲