NOIP 2013初赛普及组C/C++答案详解

深碍√TFBOYSˉ_ 2022-05-09 07:03 211阅读 0赞

试题和答案：  
https://wenku.baidu.com/view/aa2bc10b5022aaea988f0f77.html?re=view

# 一、单选题 #

1 A

2 A  
整数部分：1 \* 21 \+ 1 \* 20 = 3  
小数部分：0 \* 2\-1 \+ 1 \* 2\-2 = 0.25  
所以是答案是3.25

若是十制小数转化为二进制，以0.125为例

0.125 * 2 = 0.25   整数部分为0
    0.25 * 2 = 0.5     整部分为0
    0.5 * 2 = 1        整数部分为1

转化为二进制，要把上面整数部分按顺序显示在二进制的小数中。  
所以十制的0.125 = 二进制的0.001

3 B

4 C  
本题中，向下箭头表示逻辑或 ||，向上箭头表示逻辑与 &&，剩下一个符号表示逻辑非 !

A中，  
若A为true，A || B = true，!A = false，true && false = false，结果一定为假  
若A为false，A || B的值取决于B，!A = true。A || B && true，结果由B决定

B中，  
若B为true，A || B = true, !B = false, (A | B) & (!B) = true && false = false，结果一定为假  
若B为false，A || B = ?（取决于A），!B = true, (A || B) && (!B) = ? && true = ?，结果取决于A

C中，  
若A为false，(A && B) || (!A && B) = (false && B) || (true && B) = false || B = B  
若A为true，(A && B) || (!A && B) = (true && B) || (false && B) = B || false = B  
可见A不管是真是假，其结果都取决于B。所以是正确答案。

D中，  
若A为false, (A || B) & !A && B = B & true && B = B，结果取决于B  
若A为true, (A || B) && !A && B = true && false && B = false，结果一定为假

5 D  
A中，6 mod 11 = 17 mod 1 = 6，所以6和17会冲突。  
B中，x2分别等于4，36，100，289，对11取模的结果为4, 3, 1, 3。冲突。  
C中，2x分别为4， 12， 20， 34，对11取模的结果为4， 1， 9，1。冲突。  
D中，x求根号并向下取整后，分别为1， 2，3，4，对11取模的结果为1， 2， 3，4

6 B

7 B

8 C

9 A  
当二叉树为满二叉树时，有最多的结点拥有两个子节点。从图中可以看出来，有4个节点拥有两个子节点。

![1-9.png][]

10 C

![1-10.png][]

11 A

12 A  
深度遍历的话，A1和A3必然是先后遍历的，A2不可能插在A1和A3之间。  
本题有四种深度遍历顺序：  
A0->A1->A3->A2  
A0->A2->A1->A3  
A0->A2->A3->A1  
A0->A3->A1->A2

13 D  
IPv4和IPv6中的4和6代表版本号，不代表字节数。  
IPv6是128位，IPv4是32位，这个要记忆。

14 A  
关于时间复杂度，请先精读《大话数据结构》第二章。  
冒泡排序的平均时间复杂度是n \* (n - 1) / 2，即O(n)，具体请精读《大话数据结构》第九章9.1~9.3  
插入排序有两种，一种是直接插入排序，平均时间复杂度是O(n2)。还有一种改良的插入排序，叫希尔排序，平均时间复杂度为O(nlog2n)~O(n2)，这个只能估算。具体请精读《大话数据结构》第九章9.5，9.6和P429  
快速排序的平均时间复杂度是O(n\*log2n)，具体请精读《大话数据结构》第九章9.9  
基数排序

15 C

16 C

17 A

18 D  
浮点数不是精确存诸，所以64位变32位后，变大变小不变都有可能。  
被切掉的是右边的32位。正负号由最左边的那位数决定，所以不可能改变符号。

19 A

20 B

# 二、问题求解 #

1  
思路：任选两个人的组合数 - 两个人挨在一起的组合数

>信息学学习、算法答疑请加微信307591841

[1-9.png]: /images/20220509/595dabbcee054f9eba25dd89f08fedf0.png
[1-10.png]: /images/20220509/98a6d8244d0747e2a3ce7559ec12cb23.png