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

CCF NOIP2018初赛提高组 C++语言试题 第1页，共9页 第二十四届全国青少年信息学奥林匹克联赛 初赛 提高组C++语言试题 竞赛时间： 2018年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. 1983 B. 1984 C. 1985 D. 1986 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 NOIP2018初赛提高组 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