一、单选题（每题 2 分，共 30 分）

1. 如果下面代码输入整数为 $10$，输出是 $1$，则横线处填写（ ）。

   #include <iostream>
   #include <string>
   #include <cmath>
   
   using namespace std;
   
   int main() {
   	int x;
   	cin >> x;
   	cout << ________ << endl;
   
   	return 0;
   }
   

{{ select(1) }}

• log10(x)
• sin(x)
• exp(x)
• pow(x, 10)

2. 下面定义的函数用来求斐波那契数列的 $F(n)$，其中 $n \le 10$，描述正确的是（ ）。

   int fab(int n) {
   	int f[n + 1];
   
   	f[0] = 0, f[1] = 1;
   	for (int i = 2; i <= n; i++)
   		f[i] = f[i - 1] + f[i - 2];
   
   	return f[n];
   }
   

{{ select(2) }}

• $f[0]$ 和 $f[1]$ 是递归终止条件
• 数组 $f$ 保存算法执行过程的状态
• 使用倍增法来求解
• 算法不能正常结束

3. 下列关于 $\tt C$++ 语言中函数的叙述，正确的是（ ）。

{{ select(3) }}

• 函数定义前必须声明
• 函数调用前必须定义
• 函数调用时必须提供足够的实际参数
• 函数声明只能写在函数调用前

4. $4$ 个结点的简单有向图，最多可以有多少条边？（ ）

{{ select(4) }}

• $4$
• $6$
• $8$
• $12$

5. 哈希表上可以执行的操作不包括（ ）。

{{ select(5) }}

• 插入
• 排序
• 查找
• 删除

6. 将关键码集合 $\{100,300,500,700,800,900\}$ 逐一保存在一个长度为 $100$ 的哈希表中，选取哈希函数为 $Hash(key)=key/100$，则 $800$ 保存在表中的位置应该是（ ）。

{{ select(6) }}

• $5$
• $6$
• $7$
• $8$

7. 定义 double 型常量 pi = 3.14 和变量 x，x 代表等边三角形边长，则该三角形的面积是（ ）。

{{ select(7) }}

• x * x * sin(pi/3)
• x * x * sin(pi/3) / 2
• x * x * cos(pi/3)
• x * x * cos(pi/3) / 2

8. 动态规划将一个问题分解为一系列子问题后来求解。下面关于子问题的描述正确的是（ ）。

{{ select(8) }}

• 具有重叠子问题的性质
• 和分治法的子问题类似
• 不具有最优子结构的性质
• 问题的最优解可以由部分子问题的非最优解推导出来

9. 有关下面 $\tt C$++ 代码的说法，正确的是（ ）。

   #include <iostream>
   #include <cstring>
   #include <cmath>
   
   using namespace std;
   
   int visited[100], k = 0;
   
   void dfs(int graph[][100], int start, int vexnum) {
   	visited[start] = ++k;
   	cout << start << " ";
   
   	for (int i = 0; i < vexnum; i++) {
   		if ((start != i) && !visited[i]) {
   			dfs(graph, i, vexnum);
   		}
   	}
   }
   

{{ select(9) }}

• 实现遍历过程
• 以广度优先的方式记录图中的顶点
• 存储深搜时节点的访问顺序
• 能够记录最短路径

10. 下面函数尝试使用动态规划方法求出如下递推公式的函数，则横线处填写下列哪段代码可以完成预期功能？（ ）

    $$C(n, m) = \begin{cases} 1, & 当 n = 0 或 m = 0 \\ C(n-1, m-1) + C(n-1, m), & 当 n > 0 且 m > 0 \end{cases} $$

    int rec_C[MAXN][MAXM];
    int C(int n, int m) {
    	for (int i = 0; i <= n; i++)
    		rec_C[i][0] = 1;
    	for (int j = 0; j <= m; j++)
    		rec_C[0][j] = 1;
    
    	__________ // 在此处填入代码
    		rec_C[i][j] = rec_C[i - 1][j - 1] + rec_C[i - 1][j];
    
    	return rec_C[n][m];
    }
    

{{ select(10) }}

• for (int i = n; i >= 1; i--) for (int j = 1; j <= m; j++)
• for (int i = 1; i <= n; i++) for (int j = m; j >= 1; j--)
• for (int j = 1; j <= m; j++) for (int i = 1; i <= n; i++)
• for (int j = 1; j <= m; j++) for (int i = n; i >= 1; i--)

11. 深度为 $4$ 的完全二叉树，结点总数最少有多少个？（ ）

{{ select(11) }}

• $5$
• $6$
• $7$
• $8$

12. 下面有向图中的数字表示顶点序号，则从 $1$ 号顶点出发的 $\tt BFS$ 遍历的输出顶点序列可能是（ ）。

    

{{ select(12) }}

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

13. 一个简单有向图有 $20$ 个结点，假设图中已经存在 $300$ 条边，请问增加多少条边可以成为完全图？（ ）

{{ select(13) }}

• $77$
• $78$
• $79$
• $80$

14. 在下面的有向图中，强连通分量有多少个？（ ）

    

{{ select(14) }}

• $3$
• $4$
• $5$
• $6$

15. 下⾯有关格雷码的说法，错误的是（ ）。

{{ select(15) }}

• 在格雷码中，任意两个相邻的代码只有一位二进制数不同
• 格雷码是一种唯一性编码
• 在格雷码中，最大数和最小数只有一位二进制数不同
• 格雷码是一种可靠性编码

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

1. 定义变量 double x=exp(-1)，则 x<0 为真。（ ）

{{ select(16) }}

• 正确
• 错误

2. 假设 $x$ 和 $y$ 都是 double 型正数，如果说 $x$ 比 $y$ 大一个数量级，log(x/y) 等于 $10$。（ ）

{{ select(17) }}

• 正确
• 错误

3. 如果 double 型变量 $x$ 代表锐角对应的弧度角，则可以编程来确定 $\sin(x)>\cos(x)$ 的近似区间。（ ）

{{ select(18) }}

• 正确
• 错误

4. pow(1,2) 返回的结果是浮点数。（ ）

{{ select(19) }}

• 正确
• 错误

5. 如果哈希表足够大，哈希函数确定后，不会产生冲突。（ ）

{{ select(20) }}

• 正确
• 错误

6. 动态规划最终要推导出状态转移方程才能求解。（ ）

{{ select(21) }}

• 正确
• 错误

7. 简单有向图的深搜结果和广搜结果一样。（ ）

{{ select(22) }}

• 正确
• 错误

8. 判断图是否连通可以用深搜实现。（ ）

{{ select(23) }}

• 正确
• 错误

9. 在 $\tt C$++ 中，可以使⽤二分法查找链表中的元素。（ ）

{{ select(24) }}

• 正确
• 错误

10. 有些算法或数据结构在 $\tt C/C$++ 语⾔中使⽤指针实现，一个典型的例⼦就是链表。因此，链表这一数据结构在 $\tt C/C$++ 语⾔中只能使⽤指针来实现。（ ）

{{ select(25) }}

• 正确
• 错误