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

1. 已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是：

{{ select(1) }}

• b
• c
• 98
• 99

2. 已知 a 为 int 类型变量，下列表达式 不符合语法 的是： {{ select(2) }}

• &a + 3
• +a & 3
• a - - 4
• a++3

3. 下列关于 C++ 语言中指针的叙述，不正确 的是： {{ select(3) }}

• 指针变量中存储的是内存地址。
• 指针变量指向的内存地址不一定能够合法访问。
• 结构类型中的指针成员不能指向该结构类型。
• 定义指针变量时必须指定其指向的类型。

4. 下列关于 C++ 类的说法，错误 的是： {{ select(4) }}

• 将 C++ 类对象通过值传递给函数参数时，会自动调用复制构造函数。
• 将一个类的对象赋值给该类的另一个对象时，不会自动调用构造函数。
• 定义 C++ 类对象时，一定会调用默认构造函数。
• 构造派生类的对象时，一定会调用基类的构造函数。

5. 某二叉树 T 的先序序列为 {A B D C E G H F}，中序序列为 {D B A H G E C F}，下列说法中正确的是： {{ select(5) }}

• T 的高为 5
• T 有 4 个叶节点
• T 是平衡树
• 以上说法都不对

6. 一棵完全二叉树有 431 个结点，则叶结点有多少个？ {{ select(6) }}

• 176
• 215
• 216
• 255

7. 下列关于树的说法，错误 的是： {{ select(7) }}

• 二叉树的中序遍历与其深度优先遍历总是相同的。
• 所有树都可以构造一棵二叉树与之一一对应。
• 如果树的一个叶结点有两个不同的祖先结点，那么其中一个一定是另一个的祖先结点。
• 树的结点不能有两个父结点。

8. 一个简单无向图有 10 个结点、30 条边，再增加多少条边可以成为完全图？ {{ select(8) }}

• 10
• 15
• 51
• 60

9. 以下哪个方案可以合理解决或缓解哈希表冲突： {{ select(9) }}

• 丢弃发生冲突的新元素
• 用新元素覆盖发生冲突的元素
• 用新元素覆盖在冲突位置的下一个位置
• 将新元素放置在冲突位置之后的第一个空位

10. 一个迷宫，已知从起点不经过重复结点到达终点的路径有且仅有一条，下列说法错误的是： {{ select(10) }}

• 可以使用深度优先搜索找到这条路径
• 可以使用广度优先搜索找到这条路径
• 该迷宫内与起点连通的结点，一定也与终点连通
• 该迷宫内与起点连通的结点及它们之间的路径可以抽象为无向无环图

11. 下列程序的输出是：

{{ select(11) }}

• 2
• 3
• 8
• 无法通过编译

12. 下列程序的输出是：

{{ select(12) }}

• 84
• 495
• 1012
• 结果是随机的

13. 上题程序的时间复杂度是： {{ select(13) }}

• $O(1)$
• $O(N)$
• $O(NlogN)$
• $O(N^2)$

14. 下列 fib 函数的时间复杂度是：

{{ select(14) }}

• $O(n)$
• $O(\phi^{n})$, $\phi=\dfrac{\sqrt{5}-1}{2}$
• $O(2^{n})$
• 无法正常结束。

15. 下列选项中，哪个可能是图的广度优先遍历序列： {{ select(15) }}

• 1 3 5 7 4 2 6 8 9
• 9 4 2 1 3 7 5 6 8
• 1 3 5 7 6 8 9 4 2
• 9 4 7 2 1 3 5 6 8

二、判断题（共 10 题，每题 2 分，共计 20 分）

16. 表达式 'a' << 1 的结果为 'a '。 {{ select(16) }}

• 正确
• 错误

17. 在 C++ 语言中，函数可以定义在另一个函数定义之内。 {{ select(17) }}

• 正确
• 错误

18. 选择排序一般是不稳定的。 {{ select(18) }}

• 正确
• 错误

19. 埃氏筛法和欧拉筛法都是生成素数表的筛法算法，欧拉筛法的时间复杂度更低。 {{ select(19) }}

• 正确
• 错误

20. 使用 math.h 或 cmath 头文件中的正弦函数，表达式 sin(30) 的返回类型是 double，值约为 0.5。 {{ select(20) }}

• 正确
• 错误

21. 一颗 层的完全二叉树，一定有 个结点。 {{ select(21) }}

• 正确
• 错误

22. 一个图，不管是否连通，都可以使用深度优先搜索遍历。 {{ select(22) }}

• 正确
• 错误

23. 某个哈希表键值 x 为整数，$H(x)=x % p$ 是常用哈希函数之一，选择素数 p 可以完全避免冲突。 {{ select(23) }}

• 正确
• 错误

24. 使用单链表实现队列时，链表头结点作为队首比链表头结点作为队尾更便于操作。 {{ select(24) }}

• 正确
• 错误

25. 一个图中，每个结点代表一个人，连接两个结点的边表示两人互相认识，则该图可以用来表示社交网络。 {{ select(25) }}

• 正确
• 错误