一、单项选择题

1 D
打印机是把电脑里的资料打印到纸上，所以是输出设备。
扫描仪、键盘和鼠标都是往电脑里输入东西，是输入设备。

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

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

3 D
1 Byte = 8 bit
1 KB = 1024 B
1 MB = 1024 KB = 1024 * 1024 B
1 GB = 1024 MB = 1024 * 1024 * 1024 B

4 B
LAN: Local Area Network，局域网
WAN: Wide Area Network，广域网
MAN: 非计算机行业专有名词
LNA: 非计算机行业专有名词

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

6 A
跟周期有关。输出顺序为
ASDFasdfASDFasdf……
周期为8，所以第81个字符与第1个字符一样。

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

7.jpg

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

8 A
冒泡排序要两两比较关键字。
堆排序每一次交换后都要重新比较关键字，形成新的大顶堆。
插入排序也要比较后才知道插入的位置。
与其他排序方法不一样的是，基数排序不涉及数的比较和交换，只是纯粹的排序而已。

冒泡、堆、插入排序可参考《大话数据结构》第9章。
基数排序可参考 https://www.jianshu.com/p/7c9d8a1b7f5d

9 A
（1）思路：
同时取出最大最小值，可以将元素按对来处理，先比较每一对的大小，再把大的和最大值比较，小的和最小值比较。
分奇偶：
奇数个：把最大和最小值都先设为第一个值。
偶数个：把最大和最小分别设为前两个数。
实际上就是要保证剩下来比较的是偶数个。

（2）代码：

public void getMax_Min(int a[])
{
        int len=a.length;
        int max=0,min=0;
        int i=0,j=len-1;
        if(len%2==0)
        {
            if(a[0]>a[1])   //比较
            {   max=a[0];
                min=a[1];
            }
            else
            {
                max=a[1];
                min=a[0];
            }
            i=2;//索引从2开始
        }
        else
        {
            max=a[0];
            min=a[0];
            i=1;//索引从1开始
        }

        while(i<j)
        {
            if(a[i]<a[j])   //比较
            {
                max=a[j]>max?a[j]:max;  //比较
                min=a[i]<min?a[i]:min;  //比较
            }
            else
            {
                max=a[i]>max?a[i]:max;  //比较
                min=a[j]<min?a[j]:min;  //比较
            }
            i++;
            j--;
        }
    }
}

（3）举例
例1： 5 4 3 2 1 6 7
共7个元素。设max = min = a[0] = 5, i = 1
第一次比较a[1] = 4 < a[6] = 7, 第二次比较a[6] > max成立，max = a[6] = 7，第三次比较a[1] < min成立，min = a[1] = 4
第四次比较，a[2] = 3 < a[5] = 6, 第五次比较a[5] > max不成立，第六次比较a[2] < min成立，min = a[2] = 3
第七次比较，a[3] = 2 > a[4] = 1，第八次比较a[3] > max不成立，第九次比较a[4] < min成立，min = a[4] = 1。
总共比较了9次，9 = 向上取整（3 * 7）/ 2 - 2 = 11 - 2
例2： 1 2 3 4 5 6
共6个元素。第一次比较a[0] < a[1], min = a[0] = 1, max = a[1] = 2, i = 2
第二次比较a[2] = 3 < a[5] = 6, 第三次比较a[5] > max成立，max = a[5] = 6，第四次比较a[1] < min成立，min = a[1] = 4
第五次比较，a[3] = 4 < a[4] = 5, 第六次比较a[4] > max不成立，第七次比较a[3] < min不成立。
总共比较了7次，7 = 向上取整（3 * 6）/ 2 - 2

10 B
故事包含故事。函数调用函数。

11 A
连通图：每两个点之间，都有路径可以到达
简单图：没对顶点之间只能存在一条边，且不包含环。

11.png

上面六个图符合题意，下面三个图不符合题意，因为包含了环。

12 B
10个元素的全部子集数为
C(10, 0) + C(10, 1) + C(10, 2) + C(10, 3) + C(10, 4) + C(10, 5) + C(10, 6) + C(10, 7) + C(10, 8) + C(10, 9) + C(10, 10)
= 2[C(10, 0) + C(10, 1) + C(10, 2) + C(10, 3) + C(10, 4)] + C(10, 5)
= 1024
这里C(10, 0)表示空子集，空子集是任意非空集合的子集。C(10, 10)表示集合本身，集合本身也是集合的子集。
从10个元素里取7个，有C(10, 7) = C(10, 3) = 120种方法。
120 / 1024 = 15 / 128

注，利用牛顿二项式定理，可以快速计算出C(10, 0) + C(10, 1) + ...... + C(10, 10)
牛顿二项式定理:
(a + b)¹⁰ = C(10, 0)a^10-0b⁰ + C(10, 1)a^10-1b¹ + C(10, 2)a^10-2b² + ... + C(10,10)a^10-10b¹⁰
令a = b = 1，则有
2¹⁰ = C(10, 0) + C(10, 1) + C(10, 2) + ...... + C(10, 10)

13 B
偶数都不能与10000互质。1~10000中的偶数有5000个。
能被5整除的数也不能与10000互质。1~10000中能被5整除的数有2000个，但是这2000个中有一半也能被10整除，能被10整除就能被2整除，已经减过了，不能重复减。
所以10000 - 5000 - 2000/2 = 4000

14 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。

15 B
栈的特点是先入后出，后入先出。

二、问题求解

欲购完整答案请加微信307591841
了解小朋友学编程请加QQ群581357582
关注公众号请扫描二维码

qrcode_for_kidscode_258.jpg