NOIP2018提高组初赛易错题解析
2.下列属于解释执行的程序设计语言是（）
A.C B.C++ C.Pascal D.Python
错误原因：忘记了
正解：
C、C++和Pascal都是编译性语言，而Python是解释性语言
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)
正解：
由T(n)=T(n-1)+n可得T(n)-T(n-1)=n,又得T(n)=n(n+1)/2,约等于n2
7.在一条长度为 1 的线段上随机取两个点，则以这两个点为端点的线段的期望长度是（ ）
A.1/2 B.1/3 C.2/3 D.3/5
正解：
随机取一个点的概率是1/2，且总概率不超过2/3，则答案为1/3
8.关于 Catalan 数 Cn=(2n)!/(n+1)/!n!，下列说法中错误的是（ ）
A. Cn 表示有 n+1 个结点的不同形态的二叉树的个数。
B. Cn 表示含 n 对括号的合法括号序列的个数。
C. Cn 表示长度为 n 的入栈序列对应的合法出栈序列个数。
D. Cn 表示通过连接顶点而将 n+2 边的凸多边形分成三角形的方法个数。
正解：
代入验证发现A是错误的
9.假设一台抽奖机中有红、蓝两色的球，任意时刻按下抽奖按钮，都会等概率获得红球或蓝球之一。有足够多的人每人都用这台抽奖机抽奖，假如他们的策略均为：抽中蓝球则继续抽球，抽中红球则停止。最后每个人都把自己获得的所有球放到一个大箱子里，最终大箱子里的红球与蓝球的比例接近于（ ）。
A.1:2 B.2:1 C.1:3 D.1:1
正解：
因为每次抽着红球的概率为1/2，所以加起来无限接近1，比就是1:1
二.2
2-3 树是一种特殊的树，它满足两个条件：
- 每个内部结点有两个或三个子结点；
- 所有的叶结点到根的路径长度相同。
如果一棵 2-3 树有 10 个叶结点，那么它可能有（ ）个非叶结点
A.5 B.6 C.7 D.8
正解：
手画一下即可