NOIP 2018提高组初赛C/C++答案详解

一、单项选择题

1 D 思路： 这种题一般先算2,8,16进制的，十进制难算，另三个很好互相转。

分析： 二进制化八进制：从低位（右）往高位（左），每三位直接换成八进制即可。 (1001101011)2 = (10 0110 1011)2 = (26B)16 二进制化十六进制：从低位（右）往高位（左），每四位直接换成十六进制即可。 (1001101011)2 = (1 001 101 011)2 = (1153)8 这里可以看出，D答案和A、C答案都不相同，答案必然就是D。

可以进一步将八进制转化成十进制和十六进制。 十进制：(1151)8 = (1 * 83 + 1 * 82 + 5 * 8 + 1)10 = (512 + 64 + 40 + 1)10 = (617)10 十六进制：(1151)8 = (1 001 101 001)2 = (10 0110 1001)2 = (269)16

2 D （一）定义： 编译型语言：把做好的源程序全部编译成二进制代码的可运行程序。然后，可直接运行这个程序。 解释型语言：把做好的源程序翻译一句，然后执行一句，直至结束！ （二）区别： 编译型语言，执行速度快、效率高；依靠编译器、跨平台性差些。 解释型语言，执行速度慢、效率低；依靠解释器、跨平台性好。 （三）分类 编译型的语言包括：C、C++、Delphi、Pascal、Fortran 解释型的语言包括：Java、Basic、javascript、Python。 （四）特例Java 个人认为，java是解释型的语言，因为虽然java也需要编译，编译成.class文件，但是并不是机器可以识别的语言，而是字节码，最终还是需要 jvm的解释，才能在各个平台执行，这同时也是java跨平台的原因。所以可是说java即是编译型的，也是解释型，但是假如非要归类的话，从概念上的定义，恐怕java应该归到解释型的语言中。

1-2.png

3 B 1984年邓小平指出：“计算机的普及要从娃娃做起。”教育部和中国科协委托中国计算机学会举办了全国青少年计算机程序设计竞赛（简称：NOI），1984年参加竞赛的有8000多人。这一新的活动形式受到党和政府的关怀，得到社会各界的关注与支持。

4 A （1）相关概念 ① 二叉树：树中每个节点至多有两个子节点 ② 二叉搜索树：对于树中任何节点，如果其左子节点不为空，那么该节点的value值永远 >= 其左子节点；如果其右子节点不为空，那么该节点的value值永远 <= 其右子节点 ③ 满二叉树（完美二叉树）：树中除了叶子节点，每个节点都有两个子节点 ④ 完全二叉树：最后一层的叶子节点均需在最左边（上层的结点没有排满不能排下层的，左边的结点没排满不能排右边的）

1-4-1.jpg

（2）根结点的深度 通常算做0或是1，具体是0还是1无所谓，保证程序上下文统一即可。 题目中明确指出了根结点是0，所以上面左图中的深度是3，不是4。 （3）解法一：举特例 k = 2时，即满二叉树。 上面左图中，h = 3, 结点总数为15 = (23+1 - 1) / (2 - 1)，A答案对，其他答案都错。

解法二：高年级的学生还可以直接用等比数列求和公式

1-4-2.gif

注意，这里是h + 1层，不是h层。所以分子公比的幂是h + 1。

5 D 这题跟2015年普及组的第19题完全一样。 解法一： T(n) = T(n - 1) + n = T(n - 2) + (n - 1) + n = T(n - 3) + (n - 2) + (n - 1) + n = T(1) + 2 + …… + (n - 2) + (n - 1) + n = T(0) + 1 + 2 + …… + (n - 2) + (n - 1) + n = 1 + n*(n + 1) / 2 = n2 / 2 + n / 2 + 1 最高阶是n2，所以时间复杂度为n2 。

解法二： 因为T(n) - T(n - 1) = n, 求和

1-5.png

6 B 2017年普及组考了后缀表达式，这里考的是前缀表达式。 （一）后缀表达式（逆波兰表达式） 中缀表达式转换成后缀表达式的规则： （1）遇到操作数：直接输出（添加到后缀表达式中） （2）栈为空时，遇到运算符，直接入栈 （3）遇到左括号：将其入栈 （4）遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出 （5）遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈 （6）最终将栈中的元素依次出栈，输出

对于a * d - b * c, （1）打印a （2）* 入栈 （3）打印d （4）* 优先级大于 -， * 出栈并打印， - 入栈 （5）打印b （6）打印c （7）* 出栈并打印 （8）- 出栈并打印 所以，后缀表达式的打印顺序为 a d * b c * - （二）前缀表达式（波兰表达式） 中缀表达式转前缀表达式的规则： (1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2； (2) 从右至左扫描中缀表达式； (3) 遇到操作数时，将其压入S2； (4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； (4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较； (5) 遇到括号时： (5-1) 如果是右括号“)”，则直接压入S1； (5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃； (6) 重复步骤(2)至(5)，直到表达式的最左边； (7) 将S1中剩余的运算符依次弹出并压入S2； (8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

对于a * d - b * c， （1）从右往左扫描，遇到操作数c，压入S2 （2）遇到运算符 * ， 压入S1 （3）遇到操作数b，压入S2 （4）遇到运算符 - ,因为 - 优先级低于 * ，将 * 从S1中弹出并压入S2，再将 - 压入S1 （5）遇到操作数d，将d压入S2 （6）遇到运算符 * ,因为 * 优先级高于S1内的 - ，将 * 压入S1 （7）遇到操作数a，将a压入S2 （8）弹出S1中的 * ，并压入S2；再弹出S1中的 - ，并压入S2 （9）将S2中的所有元素挨个弹出，即 - * a d * b c

7 B ① 求X的分布函数 在(0,1)线段上任意投两点(M, N)～(0,1)×(0,1)的均匀分布。0 < x < 1时，F(x) = P(X < x) = P(|M - N| < x) = 阴影部分的面积S。

1-7-1.png

1-7-2.png

8 A 这题证明较难，可用举例法来做。 n = 2时，卡特兰数 Cn = (2 2)!/3!/2! = 4!/(3!2!) = 2

答案A，n + 1 = 3个结点的二叉树有五种不同的形态。故A错。

1-8-1.png

答案B，2对括号的合法序列有两种： （）（）和（（）） 但这只能说明n = 2时是对的。

答案C，元素A先入栈，B后入栈，有两种出栈方式。 A入栈，A出栈，B入栈，B出栈。这种情况下，出栈顺序为A B A入栈，B入栈，B出栈，A出栈。这种情况下，出栈顺序为B A 但这只能说明n = 2时是对的。

答案D，四边形分成三角形的方法数有两种：

1-8-2.png

9 D 本题等价于另一个模型：某地区重男轻女，生了女孩就继续生直到生了男孩为止，这样并不会使人口性别失衡。 假如这个国家有n对夫妇，因为生男生女概率是一样的，第一轮生时，一半的夫妇生男孩，停止生育；另一半的夫妇生女孩，会继续生育。如下图所示：

1-9.png

男孩和女孩的总数都是n/2 + n/4 + n/8 + …… 从这个图可以看出来，生男孩和生女孩的比例是一样的。 如果策略可以改变概率结果，那么早就没有女人了，男人也紧接着消失，人类就灭亡了。哈哈。

这会引出另一个问题： 中国很多地方尤其是农村和边远山区，也重男轻女。既然策略不能改变男女比例，为何中国男女比例失衡（男多女少）？ 好吧，这个问题过于阴暗，这里就不深究了。

10 B 这种题如果不会做，每个答案可以举三个数来枚举。 这些数要有独特的特征，既要考虑特殊性，也要考虑一般性。 第一个数里面全是1，比如“111”。 第二个数里只有最高位是1，其他位都是0，比如“100”。 第三个数里1和0各个一半，比如“1010”。

A答案，x >>= 1，是表示x右移1位，即变为原来的一半。

例1：111

第一次循环，ret = 1, x = 11 第二次循环，ret = 2, x = 1 第三次循环，ret = 3, x = 0，循环结束

例2：100

第一次循环，ret = 1, x = 10 第二次循环，ret = 2, x = 1 到这里可以看出A答案肯定是错的。

B答案，x &= x - 1，表示x与x - 1取与后，把结果赋给x

例1：111

第一次循环，ret = 1, x = 110 第二次循环，ret = 2, x = 010 第三次循环，ret = 3, x = 0

例2：100

第一次循环，ret = 1, x = 0，循环结束

例3：1010

第一次循环，ret = 1, x = 1000 第二次循环，ret = 2, x = 0循环结束 三个例子都是对的，是正确答案的概率很大。但也不能断定，因为只要能找到一个反例，就说明这个答案不对。所以要看剩下的两个答案。

C答案： x |= x >> 1，表示把x与x的一半求或运算的结果赋值给x

例1：111

第一次循环，ret = 1, x = 111，出现死循环

D 答案：x << 1表示x变为原来的两倍，肯定不对。此时确定答案为B。