一.单选题(每题2分，共30分)

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

{{ select(1) }}

 #include <iostream>
 using namespace std;
 int main() {
 	char a = 'b';
 	cout << a + 1;
 	return 0;
 }

• b
• c
• 98
• 99

2. 已知a为int类型变量，p为int * 类型变量，下列赋值语句不符合语法的是

{{ select(2) }}

• +a = *p;
• *p = +a;
• a = *(p + a);
• *(p + a) = a;

3. 已知数组a的定义 int a[10] = {0}; ，下列说法不正确的是

{{ select(3) }}

• 语句a[-1] = 0; 会产⽣编译错误。
• 数组a 的所有元素均被初始化为0。
• 数组a ⾄少占⽤10个 int ⼤⼩的内存，⼀般为40个字节。
• 语句a[13] = 0; 不会产⽣编译错误，但会导致难以预测的运⾏结果。

4. 下列关于C++类的说法，错误的是（ ）。

{{ select(4) }}

• 构造函数不能声明为虚函数，但析构函数可以。
• 函数参数如声明为类的引⽤类型，调⽤时不会调⽤该类的复制构造函数。
• 静态⽅法属于类、不属于对象，因此不能使⽤ 对象.方法(...) 的形式调⽤静态⽅法。
• 析构派⽣类的对象时，⼀定会调⽤基类的析构函数。

5. 下列关于有向图的说法，错误的是

{{ select(5) }}

• n个顶点的弱连通有向图，最少有n-1条边。
• n个顶点的强连通有向图，最少有n条边。
• n个顶点的有向图，最多有n x (n-1)条边。
• n个顶点的有向完全图，有n x (n-1)条边。

6. ⼀棵⼆叉树的每个结点均满⾜：结点的左⼦树和右⼦树，要么同时存在，要么同时不存在。该树有197个结 点，则其叶结点有多少个？

{{ select(6) }}

• 98
• 99
• 不存在这样的树
• ⽆法确定叶结点数量

7. 下列关于⼆叉树的说法，错误的是

{{ select(7) }}

• ⼆叉排序树的中序遍历顺序与元素排序的顺序是相同的。

• n个元素的⼆叉排序树，其⾼⼀定为$floor(log_2n)$。

• ⾃平衡⼆叉查找树（AVL树）是⼀种⼆叉排序树。

• 任意的森林，都可以映射为⼀颗⼆叉树进⾏表达和存储。

8. ⼀个简单⽆向图有10个结点、6条边。在最差情况，⾄少增加多少条边可以使其连通？

{{ select(8) }}

• $3$
• $4$
• $6$
• $9$

9. ⼀个哈希表，包括n个位置（分别编号0~(n-1)），每个位置最多仅能存储⼀个元素。该哈希表只有插⼊元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。

{{ select(9) }}

• 如果哈希函数取值范围为0 ~ (n-1)，且当发⽣哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为O(n) 。（“循环向后”指：0向后⼀位为1，1向后⼀位为2，……，(n-2)向后⼀位为(n-1)，(n-1)向后⼀位为0）
• 如果哈希函数取值范围为0 ~ (n-1)，且当发⽣哈希函数碰撞时仅循环向后⼀个位置寻找空位，则查询操作的最 差时间复杂度为O(1) 。
• 如果哈希函数取值范围为0 ~ (m-1)（m < n），且当发⽣哈希函数碰撞时仅在m ~ (n-1)的范围内寻找空位，则 查询操作的最差时间复杂度为O(n-m)。
• 查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。

10. 以下关于动态规划的说法中，错误的是 （ ）。

{{ select(10) }}

• 动态规划⽅法将原问题分解为⼀个或多个相似的⼦问题。
• 动态规划⽅法通常能够列出递推公式。
• 动态规划⽅法有递推和递归两种实现形式。
• 递推实现动态规划⽅法的时间复杂度总是不低于递归实现。

11. 下⾯程序的输出为

     #include <iostream>
     #include <cmath>
     using namespace std;
     int main() {
     	cout << (int)exp(2) << endl;
     	return 0;
     }
    

{{ select(11) }}

• $4$
• $7$
• $100$
• ⽆法通过编译。

12. 下⾯程序的输出为（ ）。

```cpp
 #include <iostream>
 #define N 10
 using namespace std;
 int h[N];
 int main() {
 h[0] = h[1] = 1;
 for (int n = 2; n < N; n++)
 for (int j = 0; j < n; j++)
 h[n] += h[j] * h[n - j - 1];
 cout << h[6] << endl;
 return 0;
 }
```

{{ select(12) }}

• $132$
• $1430$
• $16796$
• 结果是随机的。

13. 上题中程序的时间复杂度为（ ）。

{{ select(13) }}

• $O(N)$
• $O(NlogN)$
• $O(N^{3/2})$
• $O(N^2)$

14. 下⾯ init_sieve 函数的时间复杂度为( )。

     int sieve[MAX_N];
     void init_sieve(int n) {
    	 for (int i = 1; i <= n; i++)
    		 sieve[i] = i;
    	 for (int i = 2; i <= n; i++)
    		 for (int j = i; j <= n; j += i)
    			 sieve[j]--;
     }
    

{{ select(14) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• ⽆法正常结束

15. 下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。

    

{{ select(15) }}

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

二.判断题(每题2分，共20分)

16. 表达式 5 ^ 3的结果为125 。

{{ select(16) }}

• 正确
• 错误

17. 在C++语⾔中，函数定义和函数调⽤可以不在同⼀个⽂件内。

{{ select(17) }}

• 正确
• 错误

18. 在n个元素中进⾏⼆分查找，平均时间复杂度是O(logn)，但须要事先进⾏排序。

    {{ select(18) }}

• 正确
• 错误

19. unsigned long long 类型是C++语⾔中表达范围最⼤的⾮负整数类型之⼀，其表达范围是[0,$2^{64}-1$]。超 出该范围的⾮负整数运算，将⽆法使⽤C++语⾔进⾏计算。

{{ select(19) }}

• 正确
• 错误

20. 使⽤ math.h 或 cmath 头⽂件中的函数，表达式 log2(32) 的结果为5、类型为 int 。

    {{ select(20) }}

• 正确

• 错误

21. C++是⼀种⾯向对象编程语⾔，C则不是。继承是⾯向对象三⼤特性之⼀。因此，使⽤C语⾔⽆法实现继承。

    {{ select(21) }}

• 正确
• 错误

22. 邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判 断两个顶点之间是否有边时，时间复杂度更低。

{{ select(22) }}

• 正确
• 错误

23. MD5是⼀种常见的哈希函数，可以由任意长度的数据⽣成128位的哈希值，曾⼴泛应⽤于数据完整性校验。 中国科学家的系列⼯作⾸次发现了可实⽤的MD5破解⽅法。之后，MD5逐渐被其他哈希函数所取代。

    {{ select(23) }}

• 正确
• 错误

24. 递归调⽤在运⾏时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这⼀问题

{{ select(24) }}

• 正确
• 错误

25. ⼀个图中，每个顶点表达⼀个城市，连接两个顶点的边表达从⼀个城市到达另⼀个城市的⼀种交通⽅式。 这个图可以⽤来表达交通⽹络，且是简单有向图。

{{ select(25) }}

• 正确

• 错误