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

1. 定义变量 double x，如果下面代码输入为 $100$，输出最接近（ ）。

   #include <iostream>
   #include <string>
   #include <cmath>
   #include <vector>
   
   using namespace std;
   
   int main() {
   	double x;
   
   	cin >> x;
   	cout << log10(x) - log2(x) << endl;
   
   	return 0;
   }
   

{{ select(1) }}

• $0$
• $-5$
• $-8$
• $8$

2. 对于下面动态规划方法实现的函数，以下选项中最适合表达其状态转移函数的为（ ）。

   int s[MAX_N], f[MAX_N][MAX_N];
   int stone_merge(int n, int a[]) {
   	for (int i = 1; i <= n; i++)
   		s[i] = s[i - 1] + a[i];
   
   	for (int i = 1; i <= n; i++)
   		for (int j = 1; j <= n; j++)
   			if (i == j)
   				f[i][j] = 0;
   			else 
   				f[i][j] = MAX_F;
   
   	for (int l = 1; l < n; l++)
   		for (int i = 1; i <= n - l; i++) {
   			int j = i + l;
   			for (int k = i; k < j; k++)
   				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
   		}
   
   	return f[1][n];
   }
   

{{ select(2) }}

• $f(i, j) = \min_{i \le k < j}(f(i,j), f(i,k)+f(k+1,j) + s(j) - s(i-1))$
• $f(i, j) = \min_{i \le k < j}(f(i,j), f(i,k)+f(k+1,j) + \sum_{k=i}^j a(k))$
• $f(i, j) = \min_{i \le k \le j}(f(i,k)+f(k+1,j) + \sum_{k=i}^{j+1} a(k))$
• $f(i, j) = \min_{i \le k < j}(f(i,k)+f(k+1,j)) + \sum_{k=i}^j a(k)$

3. 下面代码可以用来求最长上升子序列（$\tt LIS$）的长度，如果输入是：$5\ \ 1\ \ 7\ \ 3\ \ 5\ \ 9$，则输出是（ ）。

   int a[2023], f[2023];
   int main() {
   	int n, i, j, ans = -1;
   
   	cin >> n;
   	for (i = 1; i <= n; i++) {
   		cin >> a[i];
   		f[i] = 1;
   	}
   
   	for (i = 1; i <= n; i++)
   		for (j = 1; j < i; j++)
   			if (a[j] < a[i])
   				f[i] = max(f[i], f[j] + 1);
   
   	for (i = 1; i <= n; i++) {
   		ans = max(ans, f[i]);
   		cout << f[i] << " ";
   	}
   
   	cout << ans << endl;
   
   	return 0;
   }
   

{{ select(3) }}

• $9\ \ 7\ \ 5\ \ 1\ \ 1\ \ 9$
• $1\ \ 2\ \ 2\ \ 3\ \ 4\ \ 4$
• $1\ \ 3\ \ 5\ \ 7\ \ 9\ \ 9$
• $1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1$

4. $\tt C$++ 语言中，下列关于关键字 $\tt static$ 的描述不正确的是（ ）。

{{ select(4) }}

• 可以修饰类的成员函数
• 常量静态成员可以在类外进行初始化
• 若 $a$ 是类 $\tt A$ 常量静态成员，则 $a$ 的地址都可以访问且唯一
• 静态全局对象一定在 $\tt main$ 函数调用前完成初始化，执行完 $\tt main$ 函数后被析构

5. $\tt G$ 是一个非连通无向图，共有 $28$ 条边，则该图至少有（ ）个顶点。

{{ select(5) }}

• $6$
• $7$
• $8$
• $9$

6. 哈希表长 $31$，按照下面的程序依次输入 $4\ \ 17\ \ 28\ \ 30\ \ 4$，则最后的 $4$ 存入哪个位置？（ ）

   #include <iostream>
   #include <string>
   #include <cmath>
   #include <vector>
   
   using namespace std;
   
   const int N = 31;
   int htab[N], flag[N];
   
   int main() {
   	int n, x, i, j, k;
   
   	cin >> n;
   	for (i = 0; i < n; i++) {
   		cin >> x;
   		k = x % 13;
   		while (flag[k]) k = (k + 1) % 13;
   		htab[k] = x;
   		flag[k] = 1;
   	}
   
   	for (i = 0; i < N; i++)
   		cout << htab[i] << " ";
   	
   	return 0;
   }
   

{{ select(6) }}

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

7. 某二叉树 $\tt T$ 的先序遍历序列为：$\{A\ B\ D\ F\ C\ E\ G\ H\}$，中序遍历序列为：$\{B\ F\ D\ A\ G\ E\ H\ C\}$，则下列说法中正确的是（ ）。

{{ select(7) }}

• $\tt T$ 的度为 $1$
• $\tt T$ 的高为 $4$
• $\tt T$ 有 $4$ 个叶节点
• 以上说法都不对

8. 下面代码段可以求两个字符串 $s_1$ 和 $s_2$ 的最长公共子串（$\tt LCS$），下列相关描述不正确的是（ ）。

   while (cin >> s1 >> s2) {
   	memset(dp, 0, sizeof(dp));
   	
   	int n1 = strlen(s1), n2 = strlen(s2);
   	for (int i = 1; i <= n1; ++i)
   		for (int j = 1; j <= n2; ++j)
   			if (s1[i - 1] == s2[j - 1])
   				dp[i][j] = dp[i - 1][j - 1] + 1;
   			else 
   				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
   
   	cout << dp[n1][n2] << endl;
   }
   

{{ select(8) }}

• 代码的时间复杂度为 $O(n^2)$
• 代码的空间复杂度为 $O(n^2)$
• 空间复杂度已经最优
• 采用了动态规划求解

9. 图的广度优先搜索中既要维护一个标志数组标志已访问的图的结点，还需哪种结构存放结点以实现遍历？（ ）

{{ select(9) }}

• 双向栈
• 队列
• 哈希表
• 堆

10. 对关键字序列 $\{44,\ 36,\ 23,\ 35,\ 52,\ 73,\ 90,\ 58\}$ 建立哈希表，哈希函数为 $h(k)=k\%7$，执行下面的 $\tt Insert$ 函数，则等概率情况下的平均成功查找长度（即查找成功时的关键字比较次数的均值）为（ ）。

    #include <iostream>
    #include <string>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    
    typedef struct Node {
    	int data;
    	struct Node *next;
    }Node;
    
    Node* hTab[7];
    int key[] = {44, 36, 23, 35, 52, 73, 90, 58, 0};
    
    void Insert() {
    	int i, j;
    	Node *x;
    
    	for (i = 0; key[i]; i++) {
    		j = key[i] % 7;
    		x = new Node;
    		x->data = key[i];
    		x->next = hTab[j];
    		hTab[j] = x;
    	}
    
    	return ;
    }
    

{{ select(10) }}

• $7/8$
• $1$
• $1.5$
• $2$

11. 学生在读期间所上的某些课程中需要先上其他的课程，所有课程和课程间的先修关系构成一个有向图 $G$，有向边 $\tt <U, V>$ 表示课程 $\tt U$ 是课程 $\tt V$ 的先修课，则要找到某门课程 $\tt C$ 的全部先修课下面哪种方法不可行？（ ）

{{ select(11) }}

• $\tt BFS$ 搜索
• $\tt DFS$ 搜索
• $\tt DFS$ + $\tt BFS$
• 动态规划

12. 一棵完全二叉树有 $2023$ 个结点，则叶结点有多少个？（ ）

{{ select(12) }}

• $1024$
• $1013$
• $1012$
• $1011$

13. 用下面的邻接表结构保存一个有向图 $\tt G$，$\tt InfoType$ 和 $\tt VertexType$ 是定义好的类。设 $\tt G$ 有 $n$ 个顶点、$e$ 条弧，则求图 $\tt G$ 中某个顶点 $u$（其顶点序号为 $k$）的度的算法复杂度是（ ）。

    typedef struct ArcNode {
    	int adjvex;					// 该弧所指向的顶点的位置
    	struct ArcNode *nextarc;	// 指向下一条弧的指针
    	InfoType *info;				// 该弧相关信息的指针
    } ArcNode;
    
    typedef struct VNode {
    	VertexType data;			// 顶点信息
    	ArcNode *firstarc;			// 指向第一条依附该顶点的弧
    } VNode, AdjList[MAX_VERTEX_NUM];
    
    typedef struct {
    	AdjList vertices;
    	int vexnum, arcnum;
    	int kind;					// 图的种类标志
    } ALGraph;
    

{{ select(13) }}

• $O(n)$
• $O(e)$
• $O(n+e)$
• $O(n + 2e)$

14. 给定一个简单有向图 $\tt G$，判断其中是否存在环路的下列说法哪个最准确？（ ）

{{ select(14) }}

• $\tt BFS$ 更快
• $\tt DFS$ 更快
• $\tt BFS$ 和 $\tt DFS$ 一样快
• 不确定

15. 从顶点 $v_1$ 开始遍历下图 $\tt G$ 得到顶点访问序列，在下面所给的 $4$ 个序列中符合广度优先的序列有几个？（ ）

    

    • $\{v_1,\ v_2,\ v_3,\ v_4,\ v_5\}$
    • $\{v_1,\ v_2,\ v_4,\ v_3,\ v_5\}$
    • $\{v_1,\ v_4,\ v_2,\ v_3,\ v_5\}$
    • $\{v_1,\ v_2,\ v_4,\ v_5,\ v_3\}$

{{ select(15) }}

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

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

1. 小杨这学期准备参加 $\tt GESP$ 的 $7$ 级考试，其中有关于三角函数的内容，他能够通过下面的代码找到结束循环的角度值。（ ）

   int main() {
   	double x;
   
   	do {
   		cin >> x;
   		x = x / 180 * 3.14;
   	} while (int(sin(x) * sin(x) + cos(x) * cos(x)) == 1);
   
   	cout << "//" << sin(x) << " " << cos(x) << endl;
   
   	return 0;
   }
   

{{ select(16) }}

• 正确
• 错误

2. 小杨在开发画笔刷小程序（$\tt applet$），操作之一是选中黄颜色，然后在下面的左图的中间区域双击后，就变成了右图。这个操作可以用图的泛洪算法来实现。（ ）

   

{{ select(17) }}

• 正确
• 错误

3. 假设一棵完全二叉树共有 $N$ 个节点，则树的深度为 $\log N + 1$。（ ）

{{ select(18) }}

• 正确
• 错误

4. 给定一个数字序列 $A_1$，$A_2$，$A_3$，$...$，$A_n$，要求 $i$ 和 $j$（$1\le i\le j\le n$），使 $A_i+…+A_j$ 最大，可以使用动态规划方法来求解。（ ）

{{ select(19) }}

• 正确
• 错误

5. 若变量 $x$ 为 $\tt double$ 类型正数，则 log(exp(x)) > log10(x)。（ ）

{{ select(20) }}

• 正确
• 错误

6. 简单有向图有 $n$ 个顶点和 $e$ 条弧，可以用邻接矩阵或邻接表来存储，二者求节点 $u$ 的度的时间复杂度一样。（ ）

{{ select(21) }}

• 正确
• 错误

7. 某个哈希表键值 $x$ 为整数，为其定义哈希函数 $H(x)=x\%p$，则 $p$ 选择素数时不会产生冲突。（ ）

{{ select(22) }}

• 正确
• 错误

8. 动态规划只要推导出状态转移方程，就可以写出递归程序来求出最优解。（ ）

{{ select(23) }}

• 正确
• 错误

9. 广度优先搜索（$\tt BFS$）能够判断图是否连通。（ ）

{{ select(24) }}

• 正确
• 错误

10. 在 $\tt C$++ 中，如果定义了构造函数，则创建对象时先执行完缺省的构造函数，再执行这个定义的构造函数。（ ）

{{ select(25) }}

• 正确
• 错误