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

第 1 题 下面关于C++中形参、实参和定义域的说法中，正确的一项是( ) {{ select(1) }}

• 形参是函数定义时所指定的变量，它只在函数内部有效
• 在函数内部，可以修改传入的形参的值，即使该形参是一个常量引用
• 实参和形参的类型必须完全一致，否则会导致编译错误
• 使用指针作为形参时，形参是指向实参的地址，因此对该指针赋值会影响实参

第 2 题 已知三个序列：(s1={3,1,8,2,5,6,7,4})、(s2={1,5,1,8,6,4,7,5,6})、(s3={1,8,3,5,7,6,2,4})。以下哪个序列是它们的最长公共子序列( ) {{ select(2) }}

• {1, 8, 5, 6}
• {1, 5, 6, 7}
• {1, 8, 6}
• {1, 5, 7, 4}

第 3 题 现有一个地址区间为 0~10 的哈希表，当出现冲突情况，会往后找第一个空的地址存储（到10冲突了就从0开始往后），现在要依次存储 1、5、7、11、13，哈希函数为 (h(x)=(x^2 + x) \bmod 11)。其中13存储在哈希表哪个地址中( ) {{ select(3) }}

• 3
• 4
• 6
• 8

第 4 题 在0/1背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为W，物品的数量为n，其中第i个物品的重量为(w_i)，价值为(v_i)。以下关于0/1背包问题的描述，正确的是( ) {{ select(4) }}

• 在解决0/1背包问题时，使用贪心算法可以保证找到最优解，因为物品只能放入一次
• 0/1背包是P问题（多项式时间可解问题），它可以在 (O(nW)) 的时间复杂度内解决
• 0/1背包问题中，动态规划解法的空间复杂度为 (O(nW))，但可以通过滚动数组技巧将空间复杂度优化到 (O(W))
• 0/1背包问题中，每个物品只能选择一次，并且子问题之间是独立的，无法重用计算结果

第 5 题 一棵深度为6（根节点深度为1）的完全二叉树，节点总数最少有( ) {{ select(5) }}

• 31
• 32
• 63
• 64

第 6 题 对于如下二叉树（根节点为A，左子树为B，右子树为C；B的左子树为D，右子树为E；C的左子树为F，右子树为G；F的右子树为H；G的左子树为I，右子树为J），下面关于访问的顺序说法错误的是( ) {{ select(6) }}

• D E B F H J I G C A 是它的后序遍历序列
• A B C D E F G H I J 是它的广度优先遍历序列
• A B D E C F G H I J 是它的先序遍历序列
• D B E A F C H G J I 是它的中序遍历序列

第 7 题 下面程序的运行结果为( )

#include <iostream>
using namespace std;
int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (l == n) return -1;
    return l;
}
int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
    std::cout << query(n, num, x) << "\n";
    return 0;
}

{{ select(7) }}

• 2
• 3
• 4
• 5

第 8 题 下面程序中，函数 query 的时间复杂度是 ( )

#include <iostream>
using namespace std;
int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if (l == n) return -1;
    return l;
}
int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
    std::cout << query(n, num, x) << "\n";
    return 0;
}

{{ select(8) }}

• O(1)
• O(logn)
• O(n)
• O(nlogn)

第 9 题 有 5 个字符，它们出现的次数分别为 2 次、2 次、3 次、3 次、5 次。现在要用哈夫曼编码的方式来为这些字符进行编码，最小加权路径长度 WPL（每个字符的出现次数乘以它的编码长度，再把每个字符结果加起来）的值为 ( )

{{ select (9) }}

• 30
• 34
• 43
• 47

第 10 题 下面程序的运行结果为 ( )

#include <iostream>
using namespace std;
int f(int n) {
    if (n <= 2) return n * 2; // 修正递归终止条件顺序
    return f(n - 1) + f(n - 2);
}
int main() {
    cout << f(5) << endl;
    return 0;
}

{{ select(10) }}

• 10
• 16
• 26
• 30

第 11 题 一个简单无向图有 36 条边，且每个顶点的度数都为 4，则图的顶点个数为 ( )

{{ select (11) }}

• 9
• 12
• 18
• 36

第 12 题 下面关于二叉树的说法正确的是 ( )

{{ select (12) }}

• 任意二叉树的中序遍历与后序遍历必定不相同
• 对任意二叉树，若已知先序遍历与后序遍历，则该二叉树唯一确定
• 若二叉树有 n 个结点，根节点高度为 1，则其高度满足：⌈log2(n+1)⌉≤h≤n
• 在二叉树的先序遍历中，根后紧跟的结点一定是根的左孩子

第 13 题 假设一个算法时间复杂度的递推式是 T(n)=8T(4n)+nn（n 为正整数），且 T(0)=1，那么这个算法的时间复杂度是 ( )

{{ select (13) }}

• O(nn)
• O(nnlogn)
• O(n2)
• O(n2logn)

第 14 题 下面哪一个可能是下图（顶点 1 连接 5、2；5 连接 6、8；6 连接 3；8 连接 9、7；9 连接 4；7 连接 4）的深度优先遍历序列 ( )

{{ select (14) }}

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

第 15 题 下面这个有向图（顶点 1→2，2→3，3→2，3→4，4→5，5→4，5→6）的强连通分量的个数是 ( )

{{ select (15) }}

• 3
• 4
• 5
• 6

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

第 1 题 C++ 语言中，表达式 3 ^ 2 的结果类型为 int，值为 9。

{{select (16) }}

• 正确
• 错误

第 2 题 使用 cmath 头文件中的正弦函数，表达式 sin (90) 的结果类型为 double，值约为 1.0。

{{ select (17) }}

• 正确
• 错误

第 3 题 使用 strcmp ("10", "9") 比较两个字符串，返回值大于 0，说明 "10" 比 "9" 大。

{{ select (18) }}

• 正确
• 错误

第 4 题 选择排序是一种不稳定的排序算法，而冒泡排序是一种稳定的排序算法。

{{select (19) }}

• 正确
• 错误

第 5 题 求两个长度为 n 序列的最长公共子序列（LCS）长度时，可以使用滚动数组将空间复杂度从 O(n2) 优化到 O(n)。

{{ select(20) }}

• 正确
• 错误

第 6 题 在无向图中，所有顶点的度数之和等于边数的两倍。

{{select (21) }}

• 正确
• 错误

第 7 题 使用邻接矩阵存储一个有 V 个顶点、E 条边的图，对该图进行一次完整的 BFS 遍历，时间复杂度为 O(V+E)。

{{ select(22) }}

• 正确
• 错误

第 8 题 在图像处理或游戏开发中，泛洪（flood fill）算法既可以用 BFS 实现，也可以用 DFS 实现。

{{select (23) }}

• 正确
• 错误

第 9 题 使用链地址法处理冲突的哈希表，当所有元素都映射到同一个槽位时，查找操作的最坏时间复杂度为 O(n)，其中 n 为元素个数。

{{select (24) }}

• 正确
• 错误

第 10 题 一个包含 V 个顶点的连通无向图，其任何一棵生成树都恰好包含 V−1 条边。

{{select (25) }}

• 正确
• 错误