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

1. 小杨家响应国家以旧换新政策，将自家的汽油车置换为新能源汽车，正在准备自编车牌。自编车牌包括 $5$ 位数字或英文字母，要求第 $5$ 位必须是数字，前 $4$ 位中可以有最多 $1$ 位英文字母。英文字母必须是大写，而且不能是 $\tt O$ 或 $\tt I$（因为容易与数字 $0$ 或 $1$ 混淆）。请问自编车牌共有多少种可能性？（ ）

{{ select(1) }}

• $100,000$
• $1,060,000$
• $1,360,000$
• $1,460,000$

2. 新年到，四家人在一起聚会。其中两家有三口人，另外两家有两口人。现在要安排大家在一张十人圆桌坐下，要求一家人必须相邻就座。由于有主座的习俗，每个座位都被认为是不同的。请问共有多少种就座方案？（ ）

{{ select(2) }}

• $8640$
• $6912$
• $144$
• $60$

3. 下面关于 $\tt C$++ 类继承的说法，错误的是（ ）。

{{ select(3) }}

• 一个类可以继承多个类
• 一个类可以被多个类继承
• 一个类可以继承另一个类的子类
• 抽象类必须被至少一个类继承，否则会编译错误

4. 使用邻接表表达一个简单有向图，图中包含 $v$ 个顶点、$e$ 条边，则该出边表中边节点的个数为（ ）。

{{ select(4) }}

• $v\times (v-1)$
• $v\times v$
• $2\times e$
• $e$

5. 以下将二维数组作为参数的函数声明，哪个是符合语法的？（ ）

{{ select(5) }}

• void Bubble(int a[10][], int m);
• void Bubble(int a[][], int n, int m);
• void Bubble(int (*a)[20], int n);
• void Bubble(int * a[20], int n);

6. 已知两个点 $A$、$B$ 在平面直角坐标系下的坐标分别为和，并分别定义变量 double xa, ya, xb, yb; 存储坐标。假设直线 $AB$ 的斜率存在，下列哪个表达式可以用来表达它？（ ）

{{ select(6) }}

• (xa - xb) / (ya - yb)
• (xa - xb) / (yb - ya)
• (ya - yb) / (xa - xb)
• (ya - yb) / (xb - xa)

7. 二项式 $(x+y)^6$ 的展开式中 $x^3y^3$ 项的系数是（ ）。

{{ select(7) }}

• $6$
• $15$
• $20$
• $120$

8. 以下关于动态规划的说法中，错误的是（ ）。

{{ select(8) }}

• 动态规划方法有递推和递归两种实现形式
• 递归实现动态规划方法的时间复杂度总是不低于递推实现
• 动态规划方法将原问题分解为一个或多个相似的子问题
• 动态规划方法通常能够列出递推公式

9. 在下面的程序中，使用整数表示一种组合。整数二进制表示的某一位为 $1$，表示该位对应的数被选中，反之为 $0$ 表示未选中。例如，从 $0 \sim 5$ 这 $6$ 个数中选出 $3$ 个，则 $0b111000$ 代表选中 $3, 4, 5$ 三个数，$0b011001$ 代表选中 $0, 3, 4$ 三个数。$\tt zuhe\_next$ 函数按组合对应的整数由大到小的顺序，求出组合 $c$ 的下一个组合。横线处可以填入的是（ ）。

   int intlow2(int c) {
       return ________; // 在此处填入选项
   }
   int zuhe_next_incur(int c, int n, int l) {
       if (n == 1) return c;
       if ((c & (1 << l)) == 0) {
           int d = intlow2(c);
           c = (c & ~d);
           c = (c | (d >> 1));
       } else {
           c = (c & ~(1 << l));
           c = zuhe_next_incur(c, n - 1, l + 1);
           int d = intlow2(c);
           c = (c | (d >> 1));
       }
       return c;
   }
   // 从n个数中选m个，当前组合为c
   int zuhe_next(int c, int n, int m) {
       return zuhe_next_incur(c, n, 0);
   }
   

{{ select(9) }}

• ((c - 1) ^ c)
• (((c - 1) ^ c) + 1)
• (((c - 1) ^ c) >> 1)
• ((((c - 1) ^ c) + 1) >> 1)

10. 下面程序的输出为（ ）。

    #include <iostream>
    using namespace std;
    int main() {
        int N = 15, cnt = 0;
        for (int x = 0; x + x + x <= N; x++)
            for (int y = x; x + y + y <= N; y++)
                for (int z = y; x + y + z <= N; z++)
                    cnt++;
        cout << cnt << endl;
        return 0;
    }
    

{{ select(10) }}

• $174$
• $447$
• $816$
• $4096$

11. 下面最长公共子序列程序中，横线处应该填入的是（ ）。

    #define MAX(A, B) (((A) > (B)) ? (A) : (B))
    #define MIN(A, B) (((A) < (B)) ? (A) : (B))
    int dp[MAX_L + 1][MAX_L + 1];
    int LCS(char str1[], char str2[]) {
        int len1 = strlen(str1);
        int len2 = strlen(str2);
        for (int i = 0; i < len1; i++)
            for(int j = 0; j < len2; j++)
                if (str1[i] == str2[j])
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                else
                    ________; // 在此处填入选项
        return dp[len1][len2];
    }
    

{{ select(11) }}

• dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]
• dp[i + 1][j + 1] = MIN(dp[i][j + 1], dp[i + 1][j])
• dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j])
• dp[i + 1][j + 1] = MAX(dp[i][j + 1], dp[i + 1][j]) + 1

12. 下列 $\tt Dijkstra$ 算法中，横线处应该填入的是（ ）。

    typedef struct Edge {
        int in, out; // 从下标in顶点到下标out顶点的边
        int len; // 边长度
        struct Edge * next;
    } Edge;
    // v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离
    void dijkstra(int v, Edge * graph[], int start, int * dis) {
        const int MAX_DIS = 0x7fffff;
        for (int i = 0; i < v; i++)
            dis[i] = MAX_DIS;
        dis[start] = 0;
        int * visited = new int[v];
        for (int i = 0; i < v; i++)
            visited[i] = 0;
        visited[start] = 1;
        for (int t = 0; ; t++) {
            int min = MAX_DIS, minv = -1;
            for (int i = 0; i < v; i++) {
                if (visited[i] == 0 && min > dis[i]) {
                    min = dis[i];
                    minv = i;
                }
            }
            if (minv < 0)
                break;
            visited[minv] = 1;
            for (Edge * e = graph[minv]; e != NULL; e = e->next) {
                ________; // 在此处填入选项
            }
        }
        delete[] visited;
    }
    

{{ select(12) }}

• if (dis[e->out] > e->len)
      dis[e->out] = e->len;
  

• if (dis[e->out] > min + e->len)
      dis[e->out] = min + e->len;
  

• if (dis[e->in] > e->len)
      dis[e->in] = e->len;
  

• if (dis[e->in] > min + e->len)
      dis[e->in] = min + e->len;
  

13. 假设图 $\tt graph$ 中顶点数 $v$、边数 $e$，上题程序的时间复杂度为（ ）。

{{ select(13) }}

• $O(e)$
• $O(v^2)$
• $O(v\log v + e)$
• $O((v+e)\log v)$

14. 下面的快速排序程序中，两处横线处分别应填入的是（ ）。

    void quick_sort(int a[], int n) {
        if (n <= 1)
            return;
        int pivot = 0, l = 0, r = n - 1;
        while (________) { // 在此处填入选项
            while (r > pivot && a[r] >= a[pivot])
                r--;
            if (r > pivot) {
                int temp = a[pivot];
                a[pivot] = a[r];
                a[r] = temp;
                pivot = r;
            }
            while (l < pivot && a[l] <= a[pivot])
                l++;
            if (l < pivot) {
                int temp = a[pivot];
                a[pivot] = a[l];
                a[l] = temp;
                pivot = l;
            }
        }
        quick_sort(a, pivot);
        quick_sort(________); // 在此处填入选项
    }
    

{{ select(14) }}

• l < r
  a + pivot + 1, n - pivot - 1
  

• l < r
  a + pivot + 1, n - pivot
  

• l <= r
  a + pivot + 1, n - pivot - 1
  

• l <= r
  a + pivot + 1, n - pivot
  

15. 上题程序的时间复杂度为（ ）。

{{ select(15) }}

• $O(n)$
• $O(n^2)$
• $O(2^n)$
• $O(n\log n)$

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

1. 表达式 '3' + '5' 的结果为 '8'，类型为 $\tt char$。（ ）

{{ select(16) }}

• 正确
• 错误

2. 在 $\tt C$++ 语言中，可以在函数内定义结构体，但该结构体类型只能在该函数内使用。（ ）

{{ select(17) }}

• 正确
• 错误

3. 对 $n$ 个元素的数组进行排序，快速排序和归并排序的平均时间复杂度都为 $O(n\log n)$。但快速排序存在退化情况，使得时间复杂度升高至 $O(n^2)$；归并排序需要额外的空间开销。（ ）

{{ select(18) }}

• 正确
• 错误

4. 二维数组的最后一维在内存中一定是连续的，但第一维在内存中可能不连续。（ ）

{{ select(19) }}

• 正确
• 错误

5. 使用 math.h 或 cmath 头文件中的函数，表达式 log(1000) 的结果类型为 double、值约为 $3$。（ ）

{{ select(20) }}

• 正确
• 错误

6. 你有三种硬币，分别面值 $2$ 元、$5$ 元和 $7$ 元，每种硬币都有足够多。买一本书需要 $27$ 元，则有 $8$ 种硬币组合（组合与顺序无关，“$1$ 个 $2$ 元 $+1$ 个 $5$ 元 $+1$ 个 $2$ 元” 与 “$1$ 个 $5$ 元 $+2$ 个 $2$ 元” 认为是同样的组合）可以正好付清，且不需要对方找钱。（ ）

{{ select(21) }}

• 正确
• 错误

7. 使用哈希函数 $f(x) = x \% p$ 建立键值为 $\tt int$ 类型的哈希表，只要 $p$ 取小于等于哈希表大小的素数，可保证不发生碰撞。（ ）

{{ select(22) }}

• 正确
• 错误

8. 杨辉三角中的第 $n$ 行、第 $m$ 项，即为将二项式 $(a+b)^n$ 展开后 $a^{n-m}b^m$ 项的系数。（ ）

{{ select(23) }}

• 正确
• 错误

9. 判断图是否连通，可以通过广度优先搜索实现。（ ）

{{ select(24) }}

• 正确
• 错误

10. 要求解一元二次方程 $x^2 + ax + b = 0$，需要先判断表达式 a ^ 2 - b * 4 >= 0 是否为真。（ ）

{{ select(25) }}

• 正确
• 错误