You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项

1. 下列不属于操作系统的是：( ) {{ select(1) }}

• Android
• BSD
• Sublime
• Linux

2. 计算机直接识别和执行的语言是：( ) {{ select(2) }}

• 汇编语言
• 机器语言
• 高级语言
• 自然语言

3. 质数是有且仅有两个因子的数。以下哪个进制数是质数：( ) {{ select(3) }}

• $(93)10$
• $(73)16$
• $(1011011)2$
• $(141)8$

4. 在 $TCP/IP$ 协议分层模型中，$5G$ 即第五代移动通信技术属于：( ) {{ select(4) }}

• 链路层
• 网络层
• 传输层
• 应用层

5. $5G$ 最大下载速度可以达到 $800MB/s$，以该速度1s内能下载最多( )张完整的分辨率为$1600×1600、256$ 位色的位图。 {{ select(5) }}

• $9$
• $10$
• $39$
• $40$

6. 某算法的计算时间满足递推关系式 $T(n) = T(n/2) + \sqrt(n), T(1) = 1$。则该算法的时间复杂度为：( ) {{ select(6) }}

• $O(\sqrt {n})$
• $O(\sqrt {nlogn})$
• $O(\sqrt{n} logn)$
• $O(n)$

7. 盒子中有 6 种颜色的球各一个，每次等概率取出一个球并放回，期望( )次后取遍所有的颜色。 {{ select(7) }}

• $12$
• $12.3$
• $14.7$
• $15$

8. 一列列车由若干车厢连接组成。平时我们听到的“列车入库”其实就是列车经过入口驶入所在站点库存的过程。下一次使用时，该列车会从出口驶出，原先作为车头的车厢成为了车尾。“列车入库”的结构与( )相仿。 {{ select(8) }}

• 队列
• 栈
• 链表
• 堆

9. 一棵二叉树如下图所示 若采用二叉树链表存储该二叉树（各个结点包括结点的数据、左孩子指针、右孩子指针）。如果没有左孩子或者右孩子，则对应的为空指针。那么该链表中空指针的数目为（ ）。 {{ select(9) }}

• $6$
• $12$
• $7$
• $14$

10. 一棵完全二叉树有 n 个结点，哪个代码表达式可以计算出其叶子结点数：( )。{{ select(10) }}

• $n / 2$
• $(n + 1) / 2 - 1$
• $(int)(n / 2.0)$
• $(int)(n / 2.0 + 0.5)$

11. 图中 $9×9$ 网格部分格为雷，其余格为数字，表示周围一圈八个格子雷的总数。浅色部分已显示，深色部分尚未知是雷或数字。多少问号处必定为雷？( ) {{ select(11) }}

• $1$
• $2$
• $3$
• $4$

12. 如图所示，从 $A$ 点出发，每次沿网格线向上或向右行走一格，不允许穿过红线或走出网格外，到达 $B$ 点。有多少种不同的走法？（图中已画出一种走法）( ) {{ select(12) }}

• $715$
• $495$
• $455$
• $429$

13. 下列哪个算法不是用来求最小生成树的：( ) {{ select(13) }}

• $Kruscal$算法
• $Boruvka$ 算法
• $Prim$ 算法
• $Tarjan$ 算法

14. 以下关于最小生成树的性质，错误的是：( ) {{ select(14) }}

• 最小生成树的边权和是所有生成树中最小的
• 最小生成树的边权最大值是所有生成树中最小的
• 任取两点，其最小生成树上唯一路径边权和是所有生成树中最小的
• 任取两点，其最小生成树上唯一路径边权最大值是所有生成树中最小的

15. 在有 $n$ 个子叶节点的哈夫曼树中，其节点总数为（ ） {{ select(15) }}

• $2^n-1$
• $2n+1$
• $2n-1$
• $2n$