一、单选题（每题 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,3,5,7,9)$,哈希函数为 $h(x)=(x^{2}+x) \bmod 11$ ｡其中$9$存储在哈希表哪个地址中 ( )｡

{{ select(3) }}

• 1
• 2
• 3
• 4

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

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

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

• 31
• 32
• 63
• 64

第 6 题 对于如下二叉树,下面关于访问的顺序说法错误的是( )｡

{{ 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>
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>
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(\log n)$
• $O(n)$
• $O(n \log n)$

第 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 题 一个简单无向图G有36条边,且每个顶点的度数都为4,则图G的顶点个数为( )｡ {{ select(11) }}

• 9
• 12
• 18
• 36

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

• 任意二叉树的中序遍历与后序遍历必定不相同｡
• 对任意二叉树,若已知先序遍历与后序遍历,则该二叉树唯一确定｡
• 若二叉树有 n 个结点,根节点高度为1,则其高度满足: $\left\lceil\log_{2}(n+1)\right\rceil ≤h ≤n$
• 在二叉树的先序遍历中,根后紧跟的结点一定是根的左孩子｡

第 13 题 假设一个算法时间复杂度的递推式是 $T(n)=8 T(\frac{n}{4})+n \sqrt{n}$ (n为正整数),和 $T(0)=1$ ,那么这个算法的时间复杂度是( )｡ {{ select(13) }}

• $O(n \sqrt{n})$
• $O(n \sqrt{n} log n)$
• $O\left(n^{2}\right)$
• $O\left(n^{2} log n\right)$

第 14 题 下面哪一个可能是下图的深度优先遍历序列( )｡

{{ 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 题 下面这个有向图的强连通分量的个数是( )｡

{{ select(15) }}

• 3
• 4
• 5
• 6