单选题

1. ⼀间的机房要安排 $6$ 名同学进⾏上机考试，座位共 $2$ ⾏ $3$ 列。考虑到在座位上很容易看到同⼀⾏的左右两侧的屏幕，安排中间⼀列的同学做 $A$ 卷，左右两列的同学做 $B$ 卷。请问共有多少种排座位的⽅案？{{ select(1) }}

• 720
• 90
• 48
• 15

2. ⼜到了毕业季，学长学姐们都在开⼼地拍毕业照。现在有 $3$ 位学长、$3$ 位学姐希望排成⼀排拍照，要求男⽣不相邻、⼥⽣不相邻。请问共有多少种拍照⽅案？ {{ select(2) }}

• 720
• 72
• 36
• 2

3. 下列关于 C++ 类和对象的说法，错误的是{{ select(3) }}

• 通过语句 const int x = 5; 定义了⼀个对象 $x$。
• 通过语句 std::string t = "12345"; 定义了⼀个对象 $t$。
• 通过语句 void (*fp)() = NULL; 定义了⼀个对象 $fp$
• 通过语句 class MyClass; 定义了⼀个类 MyClass。

4. 关于⽣成树的说法，错误的是 {{ select(4) }}

• ⼀个⽆向连通图，⼀定有⽣成树。
• $n$ 个顶点的⽆向图，其⽣成树要么不存在，要么⼀定包含 $n-1$ 条边。
• $n$ 个顶点、$n-1$ 条边的⽆向图，不可能有多颗⽣成树。
• $n$ 个顶点、$n-1$ 条边的⽆向图，它本⾝就是⾃⼰的⽣成树。

5. ⼀对夫妻⽣男⽣⼥的概率相同。这对夫妻希望⼉⼥双全。请问这对夫妻⽣下两个孩⼦时，实现⼉⼥双全的概率是多少？ {{ select(5) }}

• $\frac{2}{3}$
• $\frac{1}{3}$
• $\frac{1}{2}$
• $\frac{1}{4}$

6. 已定义变量 double a, b;，下列哪个表达式可以⽤来判断⼀元⼆次⽅程 $x^2+ax+b=0$ 是否有实根{{ select(6) }}

• 4 * b - a * a < 0
• 4 * b <= a * a
• a * a - 4 * b
• b * 4 - a * a

7. $n$ 个结点的⼆叉树，执⾏⼴度优先搜索的平均时间复杂度是 {{ select(7) }}

• $\frac{2}{3}$
• $\frac{2}{3}$
• $\frac{2}{3}$
• $\frac{2}{3}$

8. 以下关于动态规划的说法中，错误的是{{ select(8) }}

• 动态规划⽅法通常能够列出递推公式。
• 动态规划⽅法的时间复杂度通常为状态的个数。
• 动态规划⽅法有递推和递归两种实现形式。
• 对很多问题，递推实现和递归实现动态规划⽅法的时间复杂度相当。

9. 下⾯的 sum_digit 函数试图求出从 $1$ 到 $n$（包含 $1$ 和 $n$）的数中，包含数字 $d$ 的个数。该函数的时间复杂度为。

   #include <string>
   int count_digit(int n, char d) {
       int cnt = 0;
       std::string s = std::to_string(n);
       for (int i = 0; i < s.length(); i++)
           if (s[i] == d)
       cnt++;
       return cnt;
   }
   int sum_digit(int n, char d) {
       int sum = 0;
       for (int i = 1; i <= n; i++)
       sum += count_digit(i, d);
       return sum;
   }
   

{{ select(9) }}

• $O(nlogn)$
• $O(n)$
• $O(logn)$
• $O(n^2)$

10. 下⾯程序的输出为

    #include <iostream>
    const int N = 10;
    int ch[N][N][N];
    int main() {
        for (int x = 0; x < N; x++)
            for (int y = 0; y < N; y++)
                for (int z = 0; z < N; z++)
                    if (x == 0 && y == 0 && z == 0)
                        ch[x][y][z] = 1;
                    else {
                        if (x > 0)
                            ch[x][y][z] += ch[x - 1][y][z];
                        if (y > 0)
                            ch[x][y][z] += ch[x][y - 1][z];
                        if (z > 0)
                            ch[x][y][z] += ch[x][y][z - 1];
                    }
        std::cout << ch[1][2][3] << std::endl;
        return 0;
    }
    

{{ select(10) }}

• $60$
• $20$
• $15$
• $10$

11. 下⾯ count_triple 函数的时间复杂度为

    int gcd(int a, int b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
    int count_triple(int n) {
        int cnt = 0;
        for (int v = 1; v * v * 4 <= n; v++)
            for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
                if (gcd(u, v) == 1) {
                    int a = u * u - v * v;
                    int b = u * v * 2;
                    int c = u * u + v * v;
                    cnt += n / (a + b + c);
                }
        return cnt;
    }
    

{{ select(11) }}

• $O(n)$
• $O(n^2)$
• $O(nlogn)$
• $O(n^2logn)$

12. 下⾯ quick_sort 函数试图实现快速排序算法，两处横线处分别应该填⼊的是

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

{{ select(12) }}

• swap(a[l], a[i])
  i
  

• swap(a[l], a[j])
  i
  

• swap(a[l], a[i])
  j
  

• swap(a[l], a[j])
  j
  

13. 下⾯ LIS 函数试图求出最长上升⼦序列的长度，横线处应该填⼊的是

    int max(int a, int b) {
        return (a > b) ? a : b;
    }
    int LIS(vector<int> & nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        vector<int> dp(n, 1);
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++)
                if (nums[j] < nums[i])
                    ________;  // 在此处填入选项
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
    

{{ select(13) }}

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

14. 下⾯ LIS 函数试图求出最长上升⼦序列的长度，其时间复杂度为

    #define INT_MIN (-1000)
    int LIS(vector<int> & nums) {
        int n = nums.size();
        vector<int> tail;
        tail.push_back(INT_MIN);
        for (int i = 0; i < n; i++) {
            int x = nums[i], l = 0, r = tail.size();
            while (l < r) {
                int mid = (l + r) / 2;
                if (tail[mid] < x)
                    l = mid + 1;
                else
                    r = mid;
            }
            if (r == tail.size())
                tail.push_back(x);
            else
                tail[r] = x;
        }
        return tail.size() - 1;
    }
    

{{ select(14) }}

• $O(logn)$
• $O(n)$
• $O(nlogn)$
• $O(n^2)$

15. 下⾯的程序使⽤邻接矩阵表达的带权⽆向图，则从顶点0到顶点3的最短距离为

    int weight[4][4] = {
     { 0,  5,  8, 10},
     { 5,  0,  1,  7},
     { 8,  1,  0,  3},
     {10,  7,  3,  0}};
    

{{ select(15) }}

• $9$
• $10$
• $11$
• $12$

判断题

1. C++ 语⾔中，表达式 9|12 的结果类型为 int，值为 $13$。{{ select(16) }}

• 对
• 错

2. C++语⾔中，访问数据发⽣下标越界时，总是会产⽣运⾏时错误，从⽽使程序异常退出。{{ select(17) }}

• 对
• 错

3. 对 $n$ 个元素的数组进⾏归并排序，最差情况的时间复杂度为 $O(nlogn)$。{{ select(18) }}

• 对
• 错

4. $5$ 个相同的红球和 $4$ 个相同的蓝球排成⼀排，要求每个蓝球的两侧都必须⾄少有⼀个红球，则⼀共有15种排列⽅案。{{ select(19) }}

• 对
• 错

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

• 对
• 错

6. C++ 是⼀种⾯向对象编程语⾔，C 则不是。继承是⾯向对象三⼤特性之⼀，因此，使⽤ C 语⾔⽆法实现继承。{{ select(21) }}

• 对
• 错

7. $n$ 个顶点的⽆向完全图，有 $n^{n-2}$ 棵生成树。{{ select(22) }}

• 对
• 错

8. 已知三个 double 类型的变量 $a,b$ 和 $\theta$ 分别表⽰⼀个三角形的两条边长及⼆者的夹角（弧度），则三角形的周长可以通过表达式 $\sqrt{a * a + b * b - 2 * a * b * cos(\theta)}$ 求得。 {{ select(23) }}

• 对
• 错

9. 有 $V$ 个顶点、$E$ 条边的图的深度优先搜索遍历时间复杂度为 $O(V+E)$。{{ select(24) }}

• 对
• 错

10. 从 $32$ 名学⽣中选出 $4$ ⼈分别担任班长、副班长、学习委员和组织委员，⽼师要求班级综合成绩排名最后的 $4$ 名学⽣不得参选班长或学习委员（仍可以参选副班长和组织委员），则共有 $P(30,4)$ 种不同的选法。{{ select(25) }}

• 对
• 错