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

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

{{ select(1) }}

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

• 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. 下⾯程序的输出为 （ ）。

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

{{ select(11) }}

• $2$
• $3$
• $8$
• ⽆法通过编译。

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

```cpp
#include <iostream>
#define N 10
using namespace std;
int path[N][N];
int main() {
	for (int i = 1; i < N; i++)
		path[i][0] = i;
	for (int j = 1; j < N; j++)
		path[0][j] = j;
	for (int i = 1; i < N; i++)
		for (int j = 1; j < N; j++)
			path[i][j] = path[i - 1][j] + path[i][j - 1];
	cout << path[8][4] << endl;
	return 0;
}
```

{{ select(12) }}

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

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

{{ select(13) }}

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

14. 下⾯ fib 函数的时间复杂度为

    int fib_rcd[MAX_N];
    int fib(int n) {
    	if (n <= 1)
    		return 1;
    	if (fib_rcd[n] > 0)
    		return fib_rcd[n];
    	return fib(n - 1) + fib(n - 2);
    }
    

{{ select(14) }}

• $O(n$
• O($\emptyset$^n),$\emptyset$=$\frac{\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

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

16. 表达式 'a' << 1 的结果为 'a ' 。

{{ select(16) }}

• 正确
• 错误

17. 在C++语⾔中， 函数可以定义在另⼀个函数定义之内。

{{ select(17) }}

• 正确
• 错误

18. 在C++语⾔中， 函数可以定义在另⼀个函数定义之内。

    {{ select(18) }}

• 正确
• 错误

19. 埃⽒筛法和欧拉筛法都是使⽤筛法思想⽣成素数表的算法， 欧拉筛法的时间复杂度更低。

{{ select(19) }}

• 正确
• 错误

20. 使⽤ math.h 或 cmath 头⽂件中的正弦函数， 表达式 sin(30) 的结果类型为 double 、 值约为 0.5 。

    {{ select(20) }}

• 正确

• 错误

21. ⼀颗N层的完全⼆叉树， ⼀定有$2^N-1$个结点。

    {{ select(21) }}

• 正确
• 错误

22. ⼀个图， 不管是否连通， 都可以使⽤深度优先搜索算法进⾏遍历。

{{ select(22) }}

• 正确
• 错误

23. 某个哈希表键值 x 为整数， H(x) = x % p 是常⽤的哈希函数之⼀， 要求 p 选择素数是因为这样不会产⽣冲突。

    {{ select(23) }}

• 正确
• 错误

24. 使⽤单链表实现队列时， 链表头结点作为队⾸⽐链表头结点作为队尾更便于操作。

{{ select(24) }}

• 正确
• 错误

25. ⼀个图中， 每个结点表达⼀个⼈， 连接两个结点的边表达两个结点对应的⼈相互认识， 则这个图可以⽤来 表达社交⽹络。

{{ select(25) }}

• 正确

• 错误