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

{{ select(1) }}

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

---

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

{{ select(2) }}

• 8640
• 6912
• 144
• 60

---

第 3 题 下面关于C++类继承的说法，错误的是（ ）。

{{ select(3) }}

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

---

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

{{ select(4) }}

• $v×(v-1)$
• $v×v$
• $2×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 在平面直角坐标系下的坐标分别为 (xa,ya) 和 (xb,yb) ，并分别定义变量 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^2y^3$ 项的系数是（ ）。

{{ select(7) }}

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

---

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

{{ select(8) }}

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

---

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

 1 int intlow2(int c) {
 2     return ________; // 在此处填入选项
 3 }
 4 int zuhe_next_incur(int c, int n, int l) {
 5     if (n == 1) return c;
 6     if ((c & (1 << l)) == 0) {
 7         int d = intlow2(c);
 8         c = (c & ~d);
 9         c = (c | (d >> 1));
10     } else {
11         c = (c & ~(1 << l));
12         c = zuhe_next_incur(c, n - 1, l + 1);
13         int d = intlow2(c);
14         c = (c | (d >> 1));
15     }
16     return c;
17 }
18 // 从n个数中选m个，当前组合为c
19 int zuhe_next(int c, int n, int m) {
20     return zuhe_next_incur(c, n, 0);
21 } 

{{ select(9) }}

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

---

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

 1 #include <iostream>
 2 using namespace std;
 3 int main() {
 4     int N = 15, cnt = 0;
 5     for (int x = 0; x + x + x <= N; x++)
 6         for (int y = x; x + y + y <= N; y++)
 7             for (int z = y; x + y + z <= N; z++)
 8                 cnt++;
 9     cout << cnt << endl;
10     return 0;
11 } 

{{ select(10) }}

• 174
• 447
• 816
• 4096

---

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

 1 #define MAX(A, B) (((A) > (B)) ? (A) : (B))
 2 #define MIN(A, B) (((A) < (B)) ? (A) : (B))
 3 int dp[MAX_L + 1][MAX_L + 1];
 4 int LCS(char str1[], char str2[]) {
 5     int len1 = strlen(str1);
 6     int len2 = strlen(str2);
 7     for (int i = 0; i < len1; i++)
 8         for(int j = 0; j < len2; j++)
 9             if (str1[i] == str2[j])
10                 dp[i + 1][j + 1] = dp[i][j] + 1;
11             else
12                 ________; // 在此处填入选项
13     return dp[len1][len2];
14 } 

{{ 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 题 下列Dijkstra算法中，横线处应该填入的是（ ）。

 1 typedef struct Edge {
 2     int in, out; // 从下标in顶点到下标out顶点的边
 3     int len; // 边长度
 4     struct Edge * next;
 5 } Edge;
 6 // v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离
 7 void dijkstra(int v, Edge * graph[], int start, int * dis) {
 8     const int MAX_DIS = 0x7fffff;
 9     for (int i = 0; i < v; i++)
10         dis[i] = MAX_DIS;
11     dis[start] = 0;
12     int * visited = new int[v];
13     for (int i = 0; i < v; i++)
14         visited[i] = 0;
15     visited[start] = 1;
16     for (int t = 0; ; t++) {
17         int min = MAX_DIS, minv = -1;
18         for (int i = 0; i < v; i++) {
19             if (visited[i] == 0 && min > dis[i]) {
20                 min = dis[i];
21                 minv = i;
22             }
23         }
24         if (minv < 0)
25             break;
26         visited[minv] = 1;
27         for (Edge * e = graph[minv]; e != NULL; e = e->next) {
28             ________; // 在此处填入选项
29         }
30     }
31     delete[] visited;
32 } 

{{ 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 题 假设图 graph 中顶点数 v、边数 e，上题程序的时间复杂度为（ ）。

{{ select(13) }}

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

---

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

 1 void quick_sort(int a[], int n) {
 2     if (n <= 1)
 3         return;
 4     int pivot = 0, l = 0, r = n - 1;
 5     while (________) { // 在此处填入选项
 6         while (r > pivot && a[r] >= a[pivot])
 7             r--;
 8         if (r > pivot) {
 9             int temp = a[pivot];
10             a[pivot] = a[r];
11             a[r] = temp;
12             pivot = r;
13         }
14         while (l < pivot && a[l] <= a[pivot])
15             l++;
16         if (l < pivot) {
17             int temp = a[pivot];
18             a[pivot] = a[l];
19             a[l] = temp;
20             pivot = l;
21         }
22     }
23     quick_sort(a, pivot);
24     quick_sort(________); // 在此处填入选项
25 } 

{{ 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)$

---