一.单选题(每题2分，共30分)

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 x (v-1)
• v x v
• 2 x 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 代表选中 选中0 , 3, 4三个数。 3, 4, 5 三个数， 0b011001 代表 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. 下列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. 假设图graph中顶点数v、边数e，上题程序的时间复杂度为

{{ select(13) }}

• $O(e)$
• $O(v^2)$
• $O(vlogv+e)$
• $O((v+e)logv)$

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(nlogn)$

二.判断题(每题2分，共20分)

16. 表达式'3' + '5'的结果为'8'，类型为char。

{{ select(16) }}

• 正确
• 错误

17. 在C++语⾔中，可以在函数内定义结构体，但该结构体类型只能在该函数内使⽤。

{{ select(17) }}

• 正确
• 错误

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

    {{ select(18) }}

• 正确
• 错误

19. ⼆维数组的最后⼀维在内存中⼀定是连续的，但第⼀维在内存中可能不连续。

{{ select(19) }}

• 正确
• 错误

20. 使⽤math.h或cmath头⽂件中的函数，表达式log(1000)的结果类型为double、值约为3。

    {{ select(20) }}

• 正确

• 错误

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

    {{ select(21) }}

• 正确
• 错误

22. 使⽤哈希函数f(x) = x % p建⽴键值为int类型的哈希表，只要p取⼩于等于哈希表⼤⼩的素数，可保 证不发⽣碰撞。

{{ select(22) }}

• 正确
• 错误

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

    {{ select(23) }}

• 正确
• 错误

24. 判断图是否连通，可以通过⼴度优先搜索实现。

{{ select(24) }}

• 正确
• 错误

25. 要求解⼀元⼆次⽅程$x^2+ax+b=0$，需要先判断表达式$a ^ 2 - b * 4 >= 0$是否为真。

{{ select(25) }}

• 正确

• 错误