2018年全国青少年信息学初赛提高组试题答案.pdfVIP

NOIP2018初赛提高组真题及答案 说明：难题解析比较详细，简单题没有解析 一、单项选择题 （共 10 题，每题 2 分，共计 20 分；每题有且仅有一个正确选 项） 1. 下列四个不同进制的数中，与其它三项数值上不相等的是 （）。 A. (269) 16 B. (617) 10 C. (1151) 8 D. (1001101011) 2 答案：D 解析：考察进制转换，我们可以先将A,B转换为二进制，就可以发现A,B相等，但是 与D不同，所以选 D 2. 下列属于解释执行的程序设计语言是 （）。 A. C B. C++ C. Pascal D. Python 答案：D 解析：因为C,C++,pascal都是需要编译的语言，非解释性语言 而 python 是交互式的，也是解释性语言 3. 中国计算机学会于 （）年创办全国青少年计算机程序设计竞赛。 A. 1983 B. 1984 C. 1985 D. 1986 答案：B 4. 设根节点深度为 0，一棵深度为 h 的满 k （k1）叉树，即除最后一层无任何子 节点外，每一层上的所有结点都有 k 个子结点的树，共有 （）个结点。 答案：A 解析：等比数列求和， 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(n2) 答案：D 解析： 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 答案：B 解析：先建一棵表达式树，其先序遍历就是前缀表达式 7. 在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望 长度是 （）。 A. 1 / 2 B. 1 / 3 C. 2 / 3 D. 3 / 5 答案：B 解析：我们先考虑固定一个端点的情况，如果左端点固定在了最左边那么答案为 1/2， 既然左端点更大，那么肯定答案会小于 1/2，因此只能是 B 熟悉ODT （即珂朵莉树）理论的同学可以发现 ODT 复杂度证明里面有这个东西，即随 机意义下期望区间长度。 8. 关于 Catalan 数 Cn (2n)! / (n + 1)! / n！，下列说法中错误的是 （）。 A. Cn 表示有 n + 1 个结点的不同形态的二叉树的个数。 B. Cn 表示含 n 对括号的合法括号序列的个数。 C. Cn 表示长度为 n 的入栈序列对应的合法出栈序列个数。 D. Cn 表示通过连接顶点而将 n + 2 边的凸多边形分成三角形的方法个数。 答案：A 解析：对于A，令 n 1，2个节点的二叉树形态有 2种，但是C1 1，显然错误 9. 假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率 获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的 策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获 得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于 （）。 A. 1 : 2 B. 2 : 1 C. 1 : 3 D. 1 : 1 答案：D 10. 为了统计一个非负整数的二进制形式