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

1. 下列C++代码的输出结果是

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

   Copy

A. $0$ B. $1$ C. $0.5$ D. $0.7071$

2. 对于如下图的二叉树，说法正确的是 （ ）。

   

A. 先序遍历是 $132$ 。 B. 中序遍历是 $123$ 。 C. 后序遍历是 $312$ 。 D. 先序遍历和后序遍历正好是相反的。

3. 已知两个序列 s1= {1,3,4,5,6,7,7,8,1} 、s2= {3,5,7,4,8,2,9,5,1} ，则它们的最长公共子序列是

A. {3,5,7,8,1} B. {3,4,5,7,8} C. {5,7,8} D. {3,5,7,9,1}

4. 关于序列 {2,7,1,5,6,4,3,8,9} ，以下说法错误的是

A. {2,5,6,8,9} 是它的最长上升子序列 B. {1,5,6,8,9} 是它的最长上升子序列 C. {7,5,4,3} 是它的最长下降子序列 D. {1,5,6,8,9} 是它的唯一最长上升子序列

5. 关于图的深度优先搜索和广度优先搜索，下列说法错误的是

A. 二叉树是也是一种图。 B. 二叉树的前序遍历和后序遍历都是深度优先搜索的一种。 C. 深度优先搜索可以从任意根节点开始。 D. 二叉树的后序遍历也是广度优先搜索的一种。

6. 对于如下二叉树，下面访问顺序说法错误的是（ ）。

下面有关说法，错误的是

A. HDEBFIGCA不是它的后序遍历序列 B. ABCDEFGHI是它的广度优先遍历序列 C. ABDHECFGI是它的深度优先遍历序列 D. ABDHECFGI是它的先序遍历序列

7. 以下哪个方案不能合理解决或缓解哈希表冲突（ ）。

A. 丢弃发生冲突的新元素。 B. 在每个哈希表项处，使用不同的哈希函数再建立一个哈希表，管理该表项的冲突元素。 C. 在每个哈希表项处，建立二叉排序树，管理该表项的冲突元素。 D. 使用不同的哈希函数建立额外的哈希表，用来管理所有发生冲突的元素。

8. 在C++中，关于运算符&，下面说法正确的是

A. 2 & 3 的结果是 true B. 011 & 111 的结果是 3 C. 3 & 6 的结果是 2 D. 110 & 101 的结果是 4

9. 下面关于图的说法正确的是

A. 在无向图中，环是指至少包含三个不同顶点，并且第一个顶点和最后一个顶点是相同的路径。 B. 在有向图中，环是指一个顶点经过至少另一个顶点到自身的路径。 C. 在有向图中，如果任意两个顶点之间都存在一条边，则这个图一定是强连通图。 D. 在有向图中，所有顶点的入度和出度的总和就是图的边数的两倍。

10. 图的存储和遍历算法，下面说法错误的是

A. 图的深度优先搜索和广度优先搜索对有向图和无向图都适用。 B. 图的深度优先搜索和二叉树的先序遍历道理是不一样的。 C. 图的深度优先搜索需要借助栈来完成。 D. 邻接表中，顶点vi对应链表中的边结点数目正好是顶点vi的度。

11. 如下图所示的邻接表结构，表示的是下列哪个选项中的图？。

    

A. B. C. D.

12. 如下图所示的邻接矩阵（inf 表示无穷大），表示的是下列哪个选项中的图？

![4](./503/file/4.PNG)

A. B. C. D.

13. 下面程序的输出为

```cpp
#include <iostream>
using namespace std;
int fib(int n) {
	if (n <= 1)
	return n;
	return fib(n - 1) + fib(n - 2);
}
int main() {
	cout << fib(6) << endl;
	return 0;
}

A. $5$ B. $8$ C. $13$ D. 无法正常结束。

14. 下面 count_triple 函数的时间复杂度为

int count_triple(int n) {
	int cnt = 0;
	for (int a = 1; a <= n; a++)
		for (int b = a; a + b <= n; b++) {
			int c = sqrt(a * a + b * b);
			if (a + b + c > n)
				break;
			if (a * a + b * b == c * c)
				cnt++;
	}
	return cnt;
}

A. $O(n)$ B. $O(n^{2})$ C. $O(n^{3})$ D. $O(n^{4})$

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

    

A. 1, 3, 7, 5, 4, 2, 6, 8, 9 B. 9, 4, 2, 1, 3, 5, 7, 6, 8 C. 1, 3, 4, 2, 7, 6, 8, 9, 5 D. 9, 7, 6, 8, 4, 2, 1, 5, 3

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

16. C++语⾔中， 表达式 6 & 5 的结果类型为 int 、 值为 1

A. 正确 B. 错误

17. 冒泡排序是稳定的排序算法。

A. 正确 B. 错误

18. 唯⼀分解定理（算术基本定理） 指出， 每个⼤于1的自然数都可以唯⼀地分解成若⼲个素数的乘积。 因此，我们可以很容易的对给定的自然数 n 进⾏质因数分解， 时间复杂度仅为O(log(n))。

A. 正确 B. 错误

19. C++语⾔中， 可以为同⼀个类定义多个构造函数。

A. 正确 B. 错误

20. 使⽤ math.h 或 cmath 头⽂件中的对数函数， 表达式 log(128) 的结果类型为 double 、 值约为 7.0 。

A. 正确 B. 错误

21. ⼀颗 N 层的⼆叉树， ⾄少有$2^{N-1}$个节点。

A. 正确 B. 错误

22. 非连通图不能使⽤⼴度优先搜索算法进⾏遍历。

A. 正确 B. 错误

23. 现使⽤有 N 个表项的哈希表， 从 M 个元素中进⾏查找。 该哈希表为解决哈希函数冲突， 为每个表项处建⽴单 链表存储冲突元素。 其查找操作的最坏情况时间复杂度为O(M)。

A. 正确 B. 错误

24. 动态规划有递推实现和递归实现， 对于很多问题， 通过记录⼦问题的解， 两种实现的时间复杂度是相同的。

A. 正确 B. 错误

25. 泛洪算法的递归⽅法容易造成溢出， 因此⼤的⼆维地图算法中， ⼀般不⽤递归⽅法。

A. 正确 B. 错误